Ontology-Mediated Querying with the Description Logic EL: Trichotomy and Linear Datalog Rewritability
Authors: Carsten Lutz, Leif Sabellek
IJCAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider ontology-mediated queries (OMQs) based on an EL ontology and an atomic query (AQ), provide an ultimately fine-grained analysis of data complexity and study rewritability into linear Datalog aiming to capture linear recursion in SQL. Our main results are that every such OMQ is in AC0, NL-complete or PTIME-complete, and that containment in NL coincides with rewritability into linear Datalog (whereas containment in AC0 coincides with rewritability into first-order logic). We establish natural characterizations of the three cases, show that deciding linear Datalog rewritability (as well as the mentioned complexities) is EXPTIMEcomplete, give a way to construct linear Datalog rewritings when they exist, and prove that there is no constant bound on the arity of IDB relations in linear Datalog rewritings. |
| Researcher Affiliation | Academia | Carsten Lutz and Leif Sabellek University of Bremen, Germany {clu,sabellek}@informatik.uni-bremen.de |
| Pseudocode | Yes | The program ΠQ,k consists of five types of rules: Start rules: Pcl T (S)(x) S(x) for all S N and where S(x) abbreviates V A S A(x); Extension rules: Pt1,...,tm,cl T (S)(x1, . . . , xm, y) Pt1,...,tm(x1, . . . , xm) S(y) for all S N and T -types t1, . . . , tm; Step rules: Pt1,...,tm 1,t(x1, . . . , xm 1, y) Pt1,...,tm(x1, . . . , xm) r(y, xm) S(y) for all S N and T -types t1, . . . , tm where t = cl T (S { r.A | A tm}); Consolidation rules: Pt1,...,tm 2,t(x1, . . . , xm 1) Pt1,...,tm(x1, . . . , xm 1, xm 1) for all S N and T -types t1, . . . , tm, t where t = cl T (tm 1 tm); Goal rules: goal(x) Pt(x) for all T -types t with A0 t. |
| Open Source Code | No | Proof details are in the appendix, which is provided at http://www.cs.uni-bremen.de/tdki/research/papers.html. This link is for supplementary materials (proofs) and does not explicitly state that the source code for the methodology is available. |
| Open Datasets | No | The paper is theoretical and does not use or refer to publicly available datasets for training or evaluation in the context of empirical studies. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments with training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for its research or computations. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any specific experimental setup details such as hyperparameters or training configurations. |