Mixing Open and Closed World Assumptionin Ontology-Based Data Access: Non-Uniform Data Complexity.
Carsten Lutz, İnanç Seylan, Frank Wolter · Description Logics · 2012
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 EL. 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 AC and CONP for TBoxes formulated in DL-Lite and a dichotomy between PTIME and CONP for EL-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.