Mixing Open and Closed World Assumption in Ontology-Based Data Access: Non-Uniform Data Complexity

2012 International Workshop on Description Logics

Carsten Lutz ; Înanç Seylan ; Frank Wolter

Others  :  http://ceur-ws.org/Vol-846/paper_17.pdf

来源: CEUR

【 摘 要 】

When using ontologies to access instance data, it can be useful to make a closed world assumption (CWA) for some predicates and an open world assumption (OWA) for others. The main problem with such a setup is that conjunctive query (CQ) answering becomes intractable already for inexpressive description logics such as DL-Lite and εL. We take a closer look at this situation and carry out a fine-grained complexity analysis by considering the complexity of CQ answering w.r.t. individual TBoxes. Our main results are a dichotomy between AC0 and CONP for TBoxes formulated in DL-Lite and a dichotomy between PTIME and CONP for εL-TBoxes. In each tractable case, CQ answering coincides with CQ answering under pure OWA; the CWA might still be useful as it allows queries that are more expressive than CQs.