Conjunctive Query Containment and Answering under Description Logics Constraints

Details Conjunctive Query Containment and Answering under Description Logics Constraints Conjunctive Query Containment and Answering under Description Logics Constraints

2005-07-28

arxiv.org/abs/cs/0507067v1

Computer Science

Databases

Scientific paper

Query containment and query answering are two important computational tasks in databases. While query answering amounts to compute the result of a query over a database, query containment is the problem of checking whether for every database, the result of one query is a subset of the result of another query. In this paper, we deal with unions of conjunctive queries, and we address query containment and query answering under Description Logic constraints. Every such constraint is essentially an inclusion dependencies between concepts and relations, and their expressive power is due to the possibility of using complex expressions, e.g., intersection and difference of relations, special forms of quantification, regular expressions over binary relations, in the specification of the dependencies. These types of constraints capture a great variety of data models, including the relational, the entity-relationship, and the object-oriented model, all extended with various forms of constraints, and also the basic features of the ontology languages used in the context of the Semantic Web. We present the following results on both query containment and query answering. We provide a method for query containment under Description Logic constraints, thus showing that the problem is decidable, and analyze its computational complexity. We prove that query containment is undecidable in the case where we allow inequalities in the right-hand side query, even for very simple constraints and queries. We show that query answering under Description Logic constraints can be reduced to query containment, and illustrate how such a reduction provides upper bound results with respect to both combined and data complexity.

Affiliated with

Also associated with

No associations

Rating

Conjunctive Query Containment and Answering under Description Logics Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Conjunctive Query Containment and Answering under Description Logics Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conjunctive Query Containment and Answering under Description Logics Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-46514