资源论文Ontology-Based Data Access with Closed Predicates Is Inherently Intractable (Sometimes)

Ontology-Based Data Access with Closed Predicates Is Inherently Intractable (Sometimes)

2019-11-08 | |  47 |   46 |   0
Abstract When answering queries in the presence of ontologies, adopting the closed world assumption for some predicates easily results in intractability. We analyze this situation on the level of individual ontologies formulated in the description logics DLLite and EL and show that in all cases where answering conjunctive queries (CQs) with (open and) closed predicates is tractable, it coincides with answering CQs with all predicates assumed open. In this sense, CQ answering with closed predicates is inherently intractable. Our analysis also yields a dichotomy between AC0 and CO NP for CQ answering w.r.t. ontologies formulated in DL-Lite and a dichotomy between PT IME and CO NP for EL. Interestingly, the situation is less dramatic in the more expressive description logic ELI, where we find ontologies for which CQ answering is in PT IME, but does not coincide with CQ answering where all predicates are open.

上一篇:Action Language BC: Preliminary Report

下一篇:Cyclic Causal Models with Discrete Variables: Markov Chain Equilibrium Semantics and Sample Ordering

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...