6

だから私はDatalogがどのように機能するかを理解しようとしています.DatalogとPrologの違いの1つは、否定と再帰に階層化の制限があることです. ウィキペディアを引用するには：

述語 P が述語 Q から積極的に派生する場合 (つまり、P がルールの先頭であり、Q が同じルールの本体で積極的に発生する場合)、P の層化数は層化よりも大きいか等しくなければなりません。 Qの数

述語 P が述語 Q の否定から派生する場合 (つまり、P がルールの先頭であり、Q が同じルールの本体で否定的に発生する場合)、P の層化数は Q の層化数よりも大きくなければなりません。 、

したがって、これにより、次の 2 つの述語は単純に同じ成層番号を割り当てることができるため、成層エラーにはなりません。したがって、循環定義にもかかわらず、これらの述語は問題ありません。

  1. A(x) :- B(x)
  2. B(x) :- A(x)

しかし、否定が含まれる定義がある場合に何が起こるかとは対照的です（〜は否定です）

  1. A(x) :- ~ B(x)
  2. B(x) :- ~ A(x)

ここでは成層化は不可能です。A(x,y) は B(x,y) よりも大きい成層数を持たなければならず、B(x,y) は A(x,y) よりも大きな成層数を持たなければなりません。私の最初の考えでは、これは循環定義であるため、これは問題ありませんでしたが、述語が否定されない限り、階層化は循環性で問題ありません。しかし、なぜ？真の値は単純に 2 進数です。否定記号を持つ式をこのように異なる方法で処理することは、非常に恣意的に思えます。この層化は、最初のケースにはない 2 番目のケースで防止しようとしているものは何ですか?

4

1 に答える 1

7

私は問題があると思います：

A(x) :- \+ B(x)

B(x) :- \+ A(x)

...あいまいなセマンティクスがあるということです。このプログラムには、とという2 つの最小モデルがあり、したがって、不動点セマンティクス(不動点なし) またはモデル理論的セマンティクス(固有の最小モデルなし) の下では明確に定義されていません。{A(x)}{B(x)}

この問題に対処するために、Datalog の階層化されたセマンティクスは、Datalog プログラムの構文に制限を課します。プログラムに階層化が存在する場合、固定小数点とモデル理論の両方のセマンティクス (その逆もあると思います）。

Datalog の階層化セマンティクスの正確な詳細については、テキスト「Foundations of Databases by Serge Abiteboul、Richard Hull、Victor Vianu」を参照してください。これはたまたまオンラインで無料で入手でき、関連する詳細は第 15 章にあります。この優れたテキストは、モデル、固定小数点など、上で使用した他の用語のほとんどについても説明しています。

于 2012-09-18T05:25:35.240 に答える