1

私は小規模で複雑なデータベースを持っています (数百万のレコードが非常に少ない数千のテーブルに分割されています)。レコードは、ビジネス ルールと考えることができます。既存のルール (他のユーザー定義ルールを含む) に関して、ユーザーが独自のルールを定義するための規定があります。これらのルールは、時には複雑なパスを介して、他のルールに依存しています。依存関係は、階層ではなく拡張ネットワークを形成します。

新しく定義されたルール (または一連のルール) で、新しいルール自体が循環的であるかどうか、または既存のルールと組み合わせたときに循環を作成するかどうかを判断するアルゴリズムを探しています。

次の状況で効率的なアルゴリズムが必要です。

  1. アルゴリズムの結果は、ブール値 (サイクルがある場合は true、そうでない場合は false) である必要があります。
  2. 既存のデータベースはサイクル フリーであると見なすことができます。
  3. サイクルが見つかるとすぐに処理を停止できます。通常のケース (95% ??) では、サイクルはありません。残念ながら、これはまさに、サイクルがないと判断するために、提案された新しいルールのすべての可能なパスを処理が完了しなければならない (と私は思う) 場合です。
  4. このアルゴリズムは、データベースに入力された新しいユーザー定義ルールを検証するために使用されます。通常のケースでは、できるだけ迅速に行う必要があります。この検証が作成プロセスのボトルネックになることは望ましくありません。
  5. データの取得には比較的コストがかかります。通常は 1 つ以上のクエリが必要で、その中には非常に複雑なものもあります。新しく定義されたルール セットは、メモリ内で完全に使用できるように制約することができます。新しいルールの入力に課すことができる他の制約がある場合、それはこのチェックの効率を助けますが、それらが何であるかはわかりません。

編集

私はニックの答えを受け入れています.1つの修正があります. 依存関係の保存は、データベースへの非常に簡単な変更です。直接または間接に関係なく、すべての依存関係ではなく、直接の依存関係のみを保存します。依存関係 C、D、F、G および X、Y、Z (ニックの回答) の 2 つのセットをツリー構造として表示し、単一レベルの依存関係テーブルから階層構造を導出するためのさまざまな手法の 1 つを使用できます。このコストは、このコンテキストでは許容できると思います。

編集

4

1 に答える 1

1

あなたの問題を正しく理解できたと思います:

A depends on C,D,F,Gルール A をデータベースに追加し、 や などの依存情報も追加するとしX,Y,Z depend on Aます。

構造全体を実際に見ずに挿入時にサイクルを検出する方法はないと思いますが、これは許可されていません。

したがって、私の考えは、すべてを事前に計算して保存することです。つまり、各ルールについて、R はそれが依存する他のすべてのルールを (直接だけでなく間接的にも) 保存します。ルール A を挿入すると、単純にすべての依存関係を取得しC, D, F, G、含まれX,Y,Z or Aていない場合はサイクルがなく、ルールセットに A を安全に追加し、すべての依存関係を A の依存関係として保存できC, D, F, GますC, D, F, G

もちろん、これにはデータベースの再構築 (および再構築) が必要です。

于 2012-08-19T10:54:13.677 に答える