Datalog rewritability and data complexity of ALCHOIQ with closed predicates

DOI10.1016/J.ARTINT.2024.104099MaRDI QIDQ6566618zbMATH OpenFDO

Authors Sanja Lukumbuzya, Magdalena Ortiz, Mantas Šimkus

Publication date 3 July 2024

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.ARTINT.2024.104099

zbMATH Keywords

closed predicatesdatalogdescription logicsquery rewriting

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Recommendations

• Polynomial rewritings from expressive description logics with closed predicates to variants of Datalog
• The data complexity of ontology-mediated queries with closed predicates
• The data complexity of description logic ontologies
• A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
• Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity

Cites work

• An introduction to description logic
• Combining answer set programming with description logics for the semantic web
• Complexity of the two-variable fragment with counting quantifiers
• Data complexity of query answering in description logics
• Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies
• Description logics of minimal knowledge and negation as failure
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• scientific article; zbMATH DE number 1448975 (Why is no real title available?)
• Linking Data to Ontologies
• Nominals, inverses, counting, and conjunctive queries or: why infinity is your friend!
• On the complexity of integer programming
• On the relative expressiveness of description logics and predicate logics
• Ontology focusing: knowledge-enriched databases on demand
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• Polynomial rewritings from expressive description logics with closed predicates to variants of Datalog
• Query answering with DBoxes is hard
• Querying visible and invisible information
• Reasoning in description logics by a reduction to disjunctive datalog
• The complexity of circumscription in DLs
• The complexity of finite model reasoning in description logics
• The data complexity of ontology-mediated queries with closed predicates
• The price of query rewriting in ontology-based data access
• Tractable reasoning and efficient query answering in description logics: The DL-Lite family

Cited in

(1)

• Closed-world semantics for conjunctive queries with negation over \(\mathcal{ELH}_\bot\) ontologies

This page was built for publication: Datalog rewritability and data complexity of \(\mathcal{ALCHOIQ}\) with closed predicates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6566618)