Conjunctive Query Answering for the Description Logic SHIQ

Details Conjunctive Query Answering for the Description Logic SHIQ Conjunctive Query Answering for the Description Logic SHIQ

2011-10-31

arxiv.org/abs/1111.0049v1

Journal Of Artificial Intelligence Research, Volume 31, pages 157-204, 2008

Computer Science

Artificial Intelligence

Scientific paper

10.1613/jair.2372

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, we consider unions of conjunctive queries over knowledge bases formulated in the prominent DL SHIQ and allow transitive roles in both the query and the knowledge base. We show decidability of query answering in this setting and establish two tight complexity bounds: regarding combined complexity, we prove that there is a deterministic algorithm for query answering that needs time single exponential in the size of the KB and double exponential in the size of the query, which is optimal. Regarding data complexity, we prove containment in co-NP.

Affiliated with

Also associated with

No associations

Rating

Conjunctive Query Answering for the Description Logic SHIQ 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 Answering for the Description Logic SHIQ, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conjunctive Query Answering for the Description Logic SHIQ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-466687