论文标题

现有规则语言的模型理论特征

Model-theoretic Characterizations of Existential Rule Languages

论文作者

Zhang, Heng, Zhang, Yan, Jiang, Guifei

论文摘要

存在规则,又称数据库中的依赖性,以及最近的知识表示和推理中的dataLog +/-是一个重要的逻辑语言家族,广泛用于计算机科学和人工智能。在模型理论中对这些语言的深入了解,我们为许多存在的规则语言建立了模型理论特征,例如(分离)嵌入式依赖性,元组生成依赖性(TGD),(TGDS),(Frontier-)守护的TGD和线性TGD。所有这些特征都适用于任意结构,并且其中大多数也适用于有限结构的类别。作为这些特征的自然应用,还确定了上述语言重写的复杂性界限。

Existential rules, a.k.a. dependencies in databases, and Datalog+/- in knowledge representation and reasoning recently, are a family of important logical languages widely used in computer science and artificial intelligence. Towards a deep understanding of these languages in model theory, we establish model-theoretic characterizations for a number of existential rule languages such as (disjunctive) embedded dependencies, tuple-generating dependencies (TGDs), (frontier-)guarded TGDs and linear TGDs. All these characterizations hold for arbitrary structures, and most of them also work on the class of finite structures. As a natural application of these characterizations, complexity bounds for the rewritability of above languages are also identified.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源