The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases

Giorgo StefanoniGiorgo Stefanoni,  Boris MotikBoris Motik,  Markus KrötzschMarkus Krötzsch,  Sebastian RudolphSebastian Rudolph
Giorgo Stefanoni, Boris Motik, Markus Krötzsch, Sebastian Rudolph
The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases
Journal of Artificial Intelligence Research, 51:645-705, December 2014
  • KurzfassungAbstract
    OWL 2 EL is a popular ontology language that supports role inclusions---that is, axioms that capture compositional properties of roles. Role inclusions closely correspond to context-free grammars, which was used to show that answering conjunctive queries (CQs) over OWL 2 EL knowledge bases with unrestricted role inclusions is undecidable. However, OWL 2 EL inherits from OWL 2 DL the syntactic regularity restriction on role inclusions, which ensures that role chains implying a particular role can be described using a finite automaton (FA). This is sufficient to ensure decidability of CQ answering; however, the FAs can be worst-case exponential in size so the known approaches do not provide a tight upper complexity bound.


    In this paper, we solve this open problem and show that answering CQs over OWL 2 EL knowledge bases is PSPACE-complete in combined complexity (i.e., the complexity measured in the total size of the input). To this end, we use a novel encoding of regular role inclusions using bounded-stack pushdown automata---that is, FAs extended with a stack of bounded size. Apart from theoretical interest, our encoding can be used in practical tableau algorithms to avoid the exponential blowup due to role inclusions. In addition, we sharpen the lower complexity bound and show that the problem is PSPACE-hard even if we consider only role inclusions as part of the input (i.e., the query and all other parts of the knowledge base are fixed). Finally, we turn our attention to navigational queries over OWL 2 EL knowledge bases, and we show that answering positive, converse-free conjunctive graph XPath queries is PSPACE-complete as well; this is interesting since allowing the converse operator in queries is known to make the problem EXPTIME-hard. Thus, in this paper we present several important contributions to the landscape of the complexity of answering expressive queries over description logic knowledge bases.
  • Weitere Informationen unter:Further Information: Link
  • Projekt:Project: DIAMOND
  • Forschungsgruppe:Research Group: Computational LogicComputational LogicWissensbasierte SystemeKnowledge-Based Systems
@article{SMKR2014,
  author    = {Giorgo Stefanoni and Boris Motik and Markus Kr{\"{o}}tzsch and
               Sebastian Rudolph},
  title     = {The Complexity of Answering Conjunctive and Navigational Queries
               over {OWL} 2 {EL} Knowledge Bases},
  journal   = {Journal of Artificial Intelligence Research},
  volume    = {51},
  publisher = {AI Access Foundation},
  year      = {2014},
  month     = {December},
  pages     = {645-705},
  doi       = {10.1613/jair.4457}
}