Research map / Learning theory and algorithms / Combinatorial and search optimization
Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Complexity analysis of answering conjunctive queries with safe negation and inequality atoms over DL-Lite-with-disjointness (RDFS-style) ontologies, giving a Π2p upper bound for UCQs with both features and matching Π2p hardness for two negated atoms or two inequalities.
Problem
Query answering over RDFS-style DL-Lite ontologies with disjointness axioms for queries with safe negation and inequality atoms, whose combined complexity was previously open for fixed small numbers of negated or inequality atoms.
Approach
A nondeterministic algorithm that guesses a local interpretation (equivalence relation over constants plus extensions of predicates) and checks model membership and query falsity, yielding a Π2p upper bound; hardness reductions from ∀∃-CNF show Π2p-hardness already for two inequality atoms or two negated atoms, and NP for one negated atom via Datalog entailment.
Key results
- Answering UCQs with safe negation and inequalities over DL-Lite-RDFS-with-disjointness is in Π2p in combined complexity and coNP in data complexity.
- Answering CQs with two inequality atoms is Π2p-hard in combined complexity, confirming a conjecture from prior work.
- Answering CQs with at most one negated atom is NP-complete in combined complexity, while two negated atoms suffice for Π2p-hardness; cont(CQ≠1, CQ≠2) is Π2p-complete.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow at most two negated atoms instead of at most one | CQ safe-negation query answering over DL-Lite¬RDFS · Combined complexity | complexity class: NP-complete -> Πp2-complete | Hurt |
| Allow at most two inequality atoms instead of at most one | CQ inequality query answering over DL-Lite¬RDFS · Combined complexity | complexity class: NP-c -> Πp2-c | Hurt |
| Allow safe negation and inequalities together | UCQ query answering over DL-Lite¬RDFS · Combined complexity | complexity class: Πp2 upper bound | Hurt |
| Assume the Unique Name Assumption | UCQ inequality query answering over DL-Lite¬RDFS · Data complexity | complexity class: coNP -> AC0 | Helped |
| Assume the Unique Name Assumption | UCQ inequality query answering over DL-Lite¬RDFS · Combined complexity | complexity class: Πp2 -> NP-complete | Helped |
Surprising findings
- Answering CQs with at most one negated atom or one inequality atom is NP-complete, much lower than the general Π2p bound, despite the ontology language being RDFS-like.
Limitations
- Decidability of answering CQs with inequalities over DL-Lite_core is left open.
- Results are purely theoretical complexity bounds with no implementation or experiments.
Experimental setup
Builds on: DL-LiteRDFS Datalog reduction forall-exists-CNF (Stockmeyer 1976) Cima, Lenzerini, and Poggi 2020
Closest papers by meaning
- Answering Conjunctive Queries with Inequalities in DL-Liteℛ (AAAI 2020 · similarity 0.95)
- Answering Queries with Negation over Existential Rules (AAAI 2022 · similarity 0.90)
- Expressive Recursive Answers for Ontological Knowledge Bases (AAAI 2026 · similarity 0.90)
- Query Rewriting for Ontology-Mediated Conditional Answers (AAAI 2020 · similarity 0.89)
- Consistent Query Answering over Existential Rules with Open and Closed Predicates (AAAI 2025 · similarity 0.89)
- Spectra of Cardinality Queries over Description Logic Knowledge Bases (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.