2017/02/10 by Meghyn Bienvenu, Bienvenu, Meghyn, Stanislav Kikot +9
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.1702.03358
openalex publication_date 2017/02/10 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
Our concern is the overhead of answering OWL 2 QL ontology-mediated queries\n(OMQs) in ontology-based data access compared to evaluating their underlying\ntree-shaped and bounded treewidth conjunctive queries (CQs). We show that OMQs\nwith bounded-depth ontologies have nonrecursive datalog (NDL) rewritings that\ncan be constructed and evaluated in LOGCFL for combined complexity, even in NL\nif their CQs are tree-shaped with a bounded number of leaves, and so incur no\noverhead in complexity-theoretic terms. For OMQs with arbitrary ontologies and\nbounded-leaf CQs, NDL-rewritings are constructed and evaluated in LOGCFL. We\nshow experimentally feasibility and scalability of our rewritings compared to\npreviously proposed NDL-rewritings. On the negative side, we prove that\nanswering OMQs with tree-shaped CQs is not fixed-parameter tractable if the\nontology depth or the number of leaves in the CQs is regarded as the parameter,\nand that answering OMQs with a fixed ontology (of infinite depth) is\nNP-complete for tree-shaped and LOGCFL for bounded-leaf CQs.\n