Published on Mon Apr 18 2016

Expressive Completeness of Existential Rule Languages for Ontology-based Query Answering

Heng Zhang, Yan Zhang, Jia-Huai You

Existential rules, also known as data dependencies in Databases, have been 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.

0
0
0
Abstract

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.

Thu Apr 19 2018
Artificial Intelligence
Loop Restricted Existential Rules and First-order Rewritability for Query Answering
In ontology-based data access (OBDA), the classical database is enhanced with logical assertions generating new intensional knowledge. A powerful form of such logical assertions is the tuple-generating dependencies (TGDs), also called existential rules. In this paper we introduce a new language called loop
0
0
0
Mon Dec 15 2014
Artificial Intelligence
Worst-case Optimal Query Answering for Greedy Sets of Existential Rules and Their Subclasses
The need for an ontological layer on top of data, associated with advanced reasoning mechanisms, has been acknowledged both in the database and knowledge representation communities. We focus in this paper on the ontological query answering problem, which consists of querying data while taking ontological knowledge into account.
0
0
0
Tue Apr 28 2015
Artificial Intelligence
Combining Existential Rules and Transitivity: Next Steps
Many classes of existential rules have beenhibited for which conjunctive query (CQ) entailment is decidable. Most of these classes cannot express transitivity of binary relations, a frequently used modelling construct. We show that transitivity can be safely added to linear rules.
0
0
0
Mon Oct 31 2011
Artificial Intelligence
Conjunctive Query Answering for the Description Logic SHIQ
Conjunctive queries play an important role as an expressive query language for Description Logics (DLs) Although modern DLs usually provide for transitive roles, conjunctive query answering over DL knowledge bases is only poorly understood if transitive roles are admitted in the query. In this paper,
0
0
0
Mon Oct 08 2012
Artificial Intelligence
Disjunctive Datalog with Existential Quantifiers: Semantics, Decidability, and Complexity Issues
Datalog is one of the best-known rule-based languages. extensions of it are used in a wide context of applications. We propose a natural extension of Disjunctive Datalog and Datalogex. We define syntax and semantics and provide a notion of instantiation.
0
0
0
Thu Jan 16 2014
Artificial Intelligence
Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!
Conjunctive queries have recently gained attention as an expressive formalism for querying Description Logic knowledge bases. The combination of nominals, inverse roles, and number restrictions in OWL 1 and OWL 2 DLs causes unsolvable problems for the techniques hitherto available.
0
0
0