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.
翻译:为了在模型理论中深入理解这些语言,我们为一些存在规则语言建立了示范理论特征特征,如(分立的)内在依赖性、多产依赖性(TGDs)、(前沿的)保护性TGDs和线性TGDs。所有这些特征特征都包含任意性结构,其中多数还涉及有限结构类别。作为这些特征的自然应用,还确定了上述语言易改性的复杂性界限。