论文标题
现有规则语言的模型理论特征
Model-theoretic Characterizations of Existential Rule Languages
论文作者
论文摘要
存在规则,又称数据库中的依赖性,以及最近的知识表示和推理中的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.