Efficient Ontology-Mediated Query Answering: Extending DL-liteR and Linear ELH
Authors: Mirko M. Dimartino, Peter T. Wood, Andrea Cali, Alexandra Poulovassilis
JAIR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We propose a novel rewriting technique for conjunctive queries (CQs) under our ontology language that makes use of nondeterministic finite state automata. We show that CQ answering in our setting is NLOGSPACE-complete with respect to data complexity and NP-complete for combined complexity; we also show that answering instance queries is NLOGSPACE-complete for data complexity and in PTIME for combined complexity. ... In terms of computational complexity, we have proved that CQ answering with respect to ELHIℓin h ontologies is in NLOGSPACE in terms of data complexity and in NP in terms of combined complexity; we have shown that these bounds are tight. ... Future work includes an empirical evaluation of our rewriting algorithms on real-world data sets. |
| Researcher Affiliation | Collaboration | Mirko M. Dimartino EMAIL Prima Assicurazioni, 71 73 Carter Lane, London, EC4V 5EQ. Peter T. Wood EMAIL Knowledge Lab, Birkbeck, University of London, Malet Street, London WC1E 7HX, UK. Andrea Cal ı EMAIL Dipartimento di Ingegneria Elettrica e delle Tecnologie dell Informazione, Universit a degli Studı di Napoli Federico II, Italy. Alexandra Poulovassilis EMAIL Knowledge Lab, Birkbeck, University of London, Malet Street, London WC1E 7HX, UK. |
| Pseudocode | Yes | Procedure Rewrite(q,T) input : Instance query q, TBox T. output: Set of conjunctive queries Q. 1 Q := {q}; 4 foreach qr Q do 5 foreach axiom I T do 6 if I is applicable to atom g in qr then 7 qr := replace g in qr by gr(g,I) ; 8 Q := Q {qr } 9 until Q = Q; 10 return Q |
| Open Source Code | No | Future work includes an empirical evaluation of our rewriting algorithms on real-world data sets, and investigation of other ontology languages that may lie within the scope of tractability of CQ answering. In particular, it would be interesting to investigate more general ways of introducing inverse roles into our language. |
| Open Datasets | No | Future work includes an empirical evaluation of our rewriting algorithms on real-world data sets, and investigation of other ontology languages that may lie within the scope of tractability of CQ answering. |
| Dataset Splits | No | The paper primarily presents theoretical work on ontology languages, query rewriting, and complexity analysis. There are no sections describing experimental evaluations on datasets, hence no information about dataset splits is provided. |
| Hardware Specification | No | The paper presents theoretical contributions related to ontology languages and query answering complexity. It does not describe any experiments that would require specific hardware, and thus no hardware specifications are provided. |
| Software Dependencies | No | The paper focuses on theoretical aspects of query answering in description logics and does not describe any implementation details or experiments that would necessitate listing specific software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical developments and complexity analysis, rather than empirical experimentation. Therefore, no experimental setup details, hyperparameters, or training configurations are provided. |