Characterizing the Program Expressive Power of Existential Rule Languages
Existential rule languages are a family of ontology languages that have been widely used in ontology-mediated query answering (OMQA). However, for most of them, the expressive power of representing domain knowledge for OMQA, known as the program expressive power, is not well-understood yet. In this paper, we establish a number of novel characterizations for the program expressive power of several important existential rule languages, including tuple-generating dependencies (TGDs), linear TGDs, as well as disjunctive TGDs. The characterizations employ natural model-theoretic properties, and automata-theoretic properties sometimes, which thus provide powerful tools for identifying the definability of domain knowledge for OMQA in these languages.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Swift Markov Logic for Probabilistic Reasoning on Knowledge Graphs
We provide a framework for probabilistic reasoning in Vadalog-based Knowledge Graphs (KGs), satisfying the requirements of ontological reasoning: full recursion, powerful existential quantification, expression of inducti…
Knowledge GraphsManagementRelational ReasoningCharacterizing Boundedness in Chase Variants
Existential rules are a positive fragment of first-order logic that generalizes function-free Horn rules by allowing existentially quantified variables in rule heads. This family of languages has recently attracted signi…
Parallelisable Existential Rules: a Story of Pieces
In this paper, we consider existential rules, an expressive formalism well suited to the representation of ontological knowledge and data-to-ontology mappings in the context of ontology-based data integration. The chase …
Data IntegrationExpressive Completeness of Existential Rule Languages for Ontology-based Query Answering
Existential rules, also known as data dependencies in Databases, have been recently rediscovered as a promising family of languages for Ontology-based Query Answering. In this paper, we prove that disjunctive embedded de…
Derivation-Graph-Based Characterizations of Decidable Existential Rule Sets
This paper establishes alternative characterizations of very expressive classes of existential rule sets with decidable query entailment. We consider the notable class of greedy bounded-treewidth sets (gbts) and a new, g…