Unions of Conjunctive Queries in SHOQ

Birte Glimm, Ian Horrocks, Ulrike Sattler

Conjunctive queries play an important role as an expressive query language in Description Logics (DLs). Decision procedures for expressive Description Logics are, however, only recently emerging and it is still an open question whether answering conjunctive queries is decidable for the DL SHOIQ that underlies the OWL DL standard. In fact, no decision procedure was known for expressive DLs that contain nominals. In this paper, we close this gap by providing a decision procedure for entailment of unions of conjunctive queries in SHOQ. Our algorithm runs in deterministic time single exponential in the size of the knowledge base and double exponential in the size of the query, which is the same as for SHIQ. Our procedure also shows that SHOQ knowledge base consistency is indeed ExpTime-complete, which was, to the best of our knowledge, always conjectured but never proved.

Subjects: 11.1 Description Logics; 9.2 Computational Complexity

Submitted: Jun 12, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.