Total and Partial Well-Founded Datalog Coincide
Total and Partial Well-Founded Datalog Coincide
复制标题
全部和部分有根据的数据记录一致
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Bertram Ludäscher
中科院分区：
文献类型：
--
作者：
J. Flum;Max Kubierschky;Bertram Ludäscher
我们证明，当限制于总程序时，有根据的 Datalog 的表达能力不会降低（已知在无限 Herbrand 结构上从 Π 1 1 降低到 Δ 1 1），从而肯定地回答了 Abiteboul、Hull 和 Vianu 提出的开放性问题 [AHV95]。特别是，我们表明，对于每个有充分依据的数据记录程序，都存在一个等效的总程序，其唯一的递归规则为 win(X) ← move(X,Y), Ø win(Y) 的形式，其中 move 可以由无量词的一阶公式定义。这为有根据的数据记录产生了一个很好的新范式，并且意味着考虑无绘制游戏就足以在有根据的语义下评估任意数据记录程序。
We show that the expressive power of well-founded Datalog does not decrease when restricted to total programs (it is known to decrease from Π 1 1 to Δ 1 1 on infinite Herbrand structures) thereby affirmatively answering an open question posed by Abiteboul, Hull, and Vianu [AHV95]. In particular, we show that for every well-founded Datalog program there exists an equivalent total program whose only recursive rule is of the form win(¯X) ← move(¯X,¯Y), ¬ win(¯Y) where move is definable by a quantifier-free first-order formula. This yields a nice new normal form for well-founded Datalog and implies that it is sufficient to consider draw-free games in order to evaluate arbitrary Datalog programs under the well-founded semantics.