Expressive 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 dependencies exactly capture the class of recursively enumerable ontologies in Ontology-based Conjunctive Query Answering (OCQA). Our expressive completeness result does not rely on any built-in linear order on the database. To establish the expressive completeness, we introduce a novel semantic definition for OCQA ontologies. We also show that neither the class of disjunctive tuple-generating dependencies nor the class of embedded dependencies is expressively complete for recursively enumerable OCQA ontologies.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
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 O…
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 IntegrationExistential Rule Languages with Finite Chase: Complexity and Expressiveness
Finite chase, or alternatively chase termination, is an important condition to ensure the decidability of existential rule languages. In the past few years, a number of rule languages with finite chase have been studied.…
Complexity of Arithmetic in Warded Datalog+-
Warded Datalog+- extends the logic-based language Datalog with existential quantifiers in rule heads. Existential rules are needed for advanced reasoning tasks, e.g., ontological reasoning. The theoretical efficiency gua…
DescriptiveKnowledge GraphsOpen-Ended Question AnsweringA Phenomenological Approach to Analyzing User Queries in IT Systems Using Heidegger's Fundamental Ontology
This paper presents a novel research analytical IT system grounded in Martin Heidegger's Fundamental Ontology, distinguishing between beings (das Seiende) and Being (das Sein). The system employs two modally distinct, de…