Model-theoretic Characterizations of Existential Rule Languages

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. 1 Introduction Existential rule languages, a family of languages that extend Datalog by allowing existential quantifiers in the rule head, had been initially introduced in databases in 1970s to specify the semantics of data stored in a database [ Abiteboul et al., 1995] . Since then, existential rule languages such as tuple-generating dependencies (TGDs), embedded dependencies and equality-generating dependencies have been extensively studied. These language have been recently rediscovered as languages for data exchange [ Fagin et al., 2005 ], data integration [ Lenzerini, 2002 ] and ontology-mediated query answering [ Cal ı et al., 2010 ] .