私は小規模で複雑なデータベースを持っています (数百万のレコードが非常に少ない数千のテーブルに分割されています)。レコードは、ビジネス ルールと考えることができます。既存のルール (他のユーザー定義ルールを含む) に関して、ユーザーが独自のルールを定義するための規定があります。これらのルールは、時には複雑なパスを介して、他のルールに依存しています。依存関係は、階層ではなく拡張ネットワークを形成します。
新しく定義されたルール (または一連のルール) で、新しいルール自体が循環的であるかどうか、または既存のルールと組み合わせたときに循環を作成するかどうかを判断するアルゴリズムを探しています。
次の状況で効率的なアルゴリズムが必要です。
- アルゴリズムの結果は、ブール値 (サイクルがある場合は true、そうでない場合は false) である必要があります。
- 既存のデータベースはサイクル フリーであると見なすことができます。
- サイクルが見つかるとすぐに処理を停止できます。通常のケース (95% ??) では、サイクルはありません。残念ながら、これはまさに、サイクルがないと判断するために、提案された新しいルールのすべての可能なパスを処理が完了しなければならない (と私は思う) 場合です。
- このアルゴリズムは、データベースに入力された新しいユーザー定義ルールを検証するために使用されます。通常のケースでは、できるだけ迅速に行う必要があります。この検証が作成プロセスのボトルネックになることは望ましくありません。
- データの取得には比較的コストがかかります。通常は 1 つ以上のクエリが必要で、その中には非常に複雑なものもあります。新しく定義されたルール セットは、メモリ内で完全に使用できるように制約することができます。新しいルールの入力に課すことができる他の制約がある場合、それはこのチェックの効率を助けますが、それらが何であるかはわかりません。
編集
私はニックの答えを受け入れています.1つの修正があります. 依存関係の保存は、データベースへの非常に簡単な変更です。直接または間接に関係なく、すべての依存関係ではなく、直接の依存関係のみを保存します。依存関係 C、D、F、G および X、Y、Z (ニックの回答) の 2 つのセットをツリー構造として表示し、単一レベルの依存関係テーブルから階層構造を導出するためのさまざまな手法の 1 つを使用できます。このコストは、このコンテキストでは許容できると思います。
編集