On the expressive power of datalog: tools and a case study
On the expressive power of datalog: tools and a case study
复制标题
论数据记录的表达能力：工具和案例研究
DOI：
10.1145/298514.298542
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
Moshe Y. Vardi
中科院分区：
文献类型：
--
作者：
Phokion G. Kolaitis;Moshe Y. Vardi
我们在这里学习语言Datalog(≠)，它是通过允许规则主体中的相等和不等而从Datalog获得的查询语言。我们将Datalog(≠)看作是无限逻辑L的一个片段，并证明了L可以用某些二人鹅卵石对策来刻画。这一特征为我们研究数据记录(≠)的表达能力提供了工具。作为一个实例，我们对有向图上固定子图同胚查询的可表现性进行了分类。《财富》等人。[FHW80]通过建立两种二分法对这些查询的计算复杂性进行了分类，这两种二分法只有当P≠NP时才是适当的。在不使用任何复杂性理论假设的情况下，我们在这里证明了这两个二分法在数据日志(≠)的可表现性方面确实是适当的。
We study here the language Datalog(≠), which is the query language obtained from Datalog by allowing equalities and inequalities in the bodies of the rules. We view Datalog(≠) as a fragment of an infinitary logic L&ohgr; and show that L&ohgr; can be characterized in terms of certain two-person pebble games. This characterization provides us with tools for investigating the expressive power of Datalog(≠). As a case study, we classify the expressibility of fixed subgraph homeomorphism queries on directed graphs. Fortune et al. [FHW80] classified the computational complexity of these queries by establishing two dichotomies, which are proper only if P ≠ NP. Without using any complexity-theoretic assumptions, we show here that the two dichotomies are indeed proper in terms of expressibility in Datalog(≠).