Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!
Description Logics are knowledge representation formalisms that provide, for example, the logical underpinning of the W3C OWL standards. Conjunctive queries, the standard query language in databases, have recently gained significant attention as an expressive formalism for querying Description Logic knowledge bases. Several different techniques for deciding conjunctive query entailment are available for a wide range of DLs. Nevertheless, the combination of nominals, inverse roles, and number restrictions in OWL 1 and OWL 2 DL causes unsolvable problems for the techniques hitherto available. We tackle this problem and present a decidability result for entailment of unions of conjunctive queries in the DL ALCHOIQb that contains all three problematic constructors simultaneously. Provided that queries contain only simple roles, our result also shows decidability of entailment of (unions of) conjunctive queries in the logic that underpins OWL 1 DL and we believe that the presented results will pave the way for further progress towards conjunctive query entailment decision procedures for the Description Logics underlying the OWL standards.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard
In logic-based knowledge representation, query answering has essentially replaced mere satisfiability checking as the inferencing problem of primary interest. For knowledge bases in the basic description logic ALC, the c…
On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles
We study the description logic SQ with number restrictions applicable to transitive roles, extended with either nominals or inverse roles. We show tight 2EXPTIME upper bounds for unrestricted entailment of regular path q…
Introducing Nominals to the Combined Query Answering Approaches for EL
So-called combined approaches answer a conjunctive query over a description logic ontology in three steps: first, they materialise certain consequences of the ontology and the data; second, they evaluate the query over t…
Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability
Counting the number of answers to conjunctive queries is a fundamental problem in databases that, under standard assumptions, does not have an efficient solution. The issue is inherently #P-hard, extending even to classe…
First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics
We study FO-rewritability of conjunctive queries in the presence of ontologies formulated in a description logic between EL and Horn-SHIF, along with related query containment problems. Apart from providing characterizat…