The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases
<p>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...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for the Advancement of Artificial Intelligence
2014
|
| Subjects: |
| _version_ | 1797074004058570752 |
|---|---|
| author | Stefanoni, G Motik, B Krötzsch, M Rudolph, S |
| author_facet | Stefanoni, G Motik, B Krötzsch, M Rudolph, S |
| author_sort | Stefanoni, G |
| collection | OXFORD |
| description | <p>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.</p> <p>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.</p> |
| first_indexed | 2024-03-06T23:30:04Z |
| format | Journal article |
| id | oxford-uuid:6bb8cd4a-edd0-422c-988f-87f45cfbad65 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T23:30:04Z |
| publishDate | 2014 |
| publisher | Association for the Advancement of Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:6bb8cd4a-edd0-422c-988f-87f45cfbad652022-03-26T19:06:00ZThe complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge basesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:6bb8cd4a-edd0-422c-988f-87f45cfbad65Artificial IntelligenceKnowledge Representation and ReasoningComputer science (mathematics)EnglishOxford University Research Archive - ValetAssociation for the Advancement of Artificial Intelligence2014Stefanoni, GMotik, BKrötzsch, MRudolph, S<p>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.</p> <p>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.</p> |
| spellingShingle | Artificial Intelligence Knowledge Representation and Reasoning Computer science (mathematics) Stefanoni, G Motik, B Krötzsch, M Rudolph, S The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases |
| title | The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases |
| title_full | The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases |
| title_fullStr | The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases |
| title_full_unstemmed | The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases |
| title_short | The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases |
| title_sort | complexity of answering conjunctive and navigational queries over owl 2 el knowledge bases |
| topic | Artificial Intelligence Knowledge Representation and Reasoning Computer science (mathematics) |
| work_keys_str_mv | AT stefanonig thecomplexityofansweringconjunctiveandnavigationalqueriesoverowl2elknowledgebases AT motikb thecomplexityofansweringconjunctiveandnavigationalqueriesoverowl2elknowledgebases AT krotzschm thecomplexityofansweringconjunctiveandnavigationalqueriesoverowl2elknowledgebases AT rudolphs thecomplexityofansweringconjunctiveandnavigationalqueriesoverowl2elknowledgebases AT stefanonig complexityofansweringconjunctiveandnavigationalqueriesoverowl2elknowledgebases AT motikb complexityofansweringconjunctiveandnavigationalqueriesoverowl2elknowledgebases AT krotzschm complexityofansweringconjunctiveandnavigationalqueriesoverowl2elknowledgebases AT rudolphs complexityofansweringconjunctiveandnavigationalqueriesoverowl2elknowledgebases |