Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics

AI summary

Overview

Research area: Knowledge representation and reasoning, specifically ontology-mediated query answering (OMQA) over inconsistent weighted description logic (DL) knowledge bases, with a focus on computational complexity (data complexity).

Technical level: Advanced. The paper assumes familiarity with description logics, first-order logic, conjunctive queries, and complexity classes such as NP, coNP, Δ²ᵖ, and AC⁰.

Scope: The paper determines the precise data complexity of reasoning under cost-based semantics for weighted DL knowledge bases, covering DL-Lite dialects and expressive DLs up to ALCHIO.

What This Paper Is About

Standard query answering over a DL knowledge base trivializes when the knowledge base is inconsistent, because every tuple becomes a certain answer. Cost-based semantics addresses this by assigning weights to axioms and assertions, giving each interpretation a cost based on the weights of the axioms and assertions it violates. Queries are then evaluated over interpretations of optimal cost, or over all interpretations whose cost stays within a bound k. This paper asks how hard it is to answer queries under these semantics when the ABox (the data) grows large, extending the analysis to DLs with inverse roles and role inclusions and sharpening previously known bounds.

Key Contributions

1. A Δ²ᵖ upper bound for optimal-cost semantics. The paper proves that optimal-cost certain and possible conjunctive query answering for ALCHIO is in Δ²ᵖ (deterministic polynomial time with an NP oracle), using a quotient construction that yields a small interpretation property independent of the cost. This closes a question left open in prior work, where no non-trivial upper bound was known for optimal-cost certain answers.

2. Sharpened lower bounds for bounded-cost semantics. Existing hardness results, which held for cost bounds k ≥ 3, are strengthened to hold already for k = 1, and new lower bounds are established for DL-Lite_core.

3. A matching Δ²ᵖ lower bound for DL-Lite_core. Combined with the existing lower bound for EL_bot, this pins down the exact complexity of optimal-cost certain and possible semantics for these DLs.

4. A surprising tractability result. For DL-Lite_bool^H ontologies and a fixed cost bound, certain answers for instance queries and possible answers for conjunctive queries can be computed by first-order rewriting, placing them in AC⁰, the lowest possible data complexity. This stands in contrast to all prior cost-based results, which showed intractability.

Main Findings

• NP and coNP upper bounds for ALCHIO: CQA_p (bounded-cost possible conjunctive query entailment) for ALCHIO is in NP, and CQA_c (bounded-cost certain) is in coNP (Theorem 1).

• Optimal-cost semantics is in Δ²ᵖ: Both CQA^opt_p and CQA^opt_c for ALCHIO are in Δ²ᵖ (Theorem 2), obtained by identifying the optimal cost through binary search.

• Optimal-cost complexity is exact: The Δ²ᵖ upper bound matches an existing lower bound for EL_bot and a new lower bound shown for DL-Lite_core (Theorem 6), making the result a completeness result.

• Fixed-cost hardness at k = 1 in EL_bot: For every k ≥ 1, bounded-cost satisfiability (BCS_k), IQA^k_p, and CQA^k_p for EL_bot are NP-hard (Theorem 3), shown by reduction from 3-SAT. For every k ≥ 1, IQA^k_c and CQA^k_c for EL are coNP-hard (Theorem 4), and concept disjointness axioms are not needed for this result.

• New DL-Lite_core lower bounds: BCS, IQA_p, and CQA_p for DL-Lite_core are NP-hard, and IQA_c and CQA_c for DL-Lite_core are coNP-hard (Theorem 5), shown by reduction from 3-Col (graph 3-colorability).

• AC⁰ for DL-Lite_bool^H with fixed cost: For DL-Lite_bool^H ontologies and a fixed cost bound, certain answers for instance queries and possible answers for conjunctive queries can be computed via first-order rewriting and therefore lie in AC⁰ (Theorem 8).

• Lower bounds for connected acyclic queries: For CQA, the lower bounds already hold for connected acyclic Boolean conjunctive queries.

• Encoding caveat: Results hold for both binary and unary encoding of weights, except for Δ²ᵖ-hardness, which holds only for binary encoding.

• Small interpretation property: If an interpretation satisfies (or fails) a Boolean conjunctive query at cost at most k, then there is another interpretation with the same query behavior, cost at most k, and a domain of size polynomial in the ABox size — with the TBox and query treated as constants, and independently of k (Lemmas 4 and 5).

• Fixed-cost picture is complete: The case of fixed k = 0 coincides with the usual semantics of EL knowledge bases, so the complexity with respect to fixed cost is now well understood.

Methodology in Plain English

The authors reason about "cost" as a penalty model: every axiom and assertion gets a weight (possibly infinite, meaning it must be satisfied), and an interpretation pays for each violation, with TBox violations counted by how many domain elements violate them. Certain answers must hold in every interpretation within a cost budget; possible answers need only hold in one.

To derive upper bounds, the researchers show they can always replace a large interpretation with a much smaller one that behaves the same way with respect to the query and costs no more. For possible answers, this is a standard "filtration" collapse. For certain answers, the treatment is harder because the property to preserve is query non-satisfaction; the authors adapt an intricate quotient construction previously used for counting conjunctive queries over ALCHI knowledge bases. Their version takes an extra parameter — a subset V of the TBox whose axioms are violated exactly as in the original interpretation — and then builds a growing chain of such subsets V₀ ⊊ V₁ ⊊ … ⊊ Vₙ until the cost bound is met. The chain terminates in at most |T| steps, and the domain size stays polynomially bounded by the ABox size.

For lower bounds, the authors reduce from 3-SAT and 3-Col, encoding the search for a satisfying assignment or a 3-coloring as the search for a low-cost interpretation. For the AC⁰ result, they show the query answering problems can be rewritten into first-order queries over the ABox alone.

Why This Matters

Impact on research. The paper resolves a question left open by the original study of cost-based semantics — the data complexity of optimal-cost certain answers — and extends cost-based reasoning to the DL-Lite family, which is the most commonly used family in ontology-mediated query answering. It also overturns the pattern that all cost-based reasoning is intractable, showing a natural case (DL-Lite_bool^H, fixed cost bound) that drops to AC⁰ and is therefore amenable to first-order rewriting, the same technique that makes DL-Lite practical for standard query answering.

Real-world applications (the paper does not itself enumerate applications; these follow from the setting it formalizes):

• Querying over inconsistent data-integration scenarios, where sources disagree and some constraints should be treated as usually but not always true.
• Biomedical and clinical ontologies, where a small number of axioms may admit rare exceptions and a weighted model can rank which ones to relax.
• Data cleaning and repair, where weights encode confidence in assertions so that repairs can be ranked by cost.
• Robust query answering, where raising the cost bound k beyond the optimum identifies answers that hold even under near-optimal scenarios.

Industry relevance. First-order rewriting is what allows ontologies to be compiled into SQL and evaluated by ordinary relational engines. The AC⁰ result for DL-Lite_bool^H suggests that at least some inconsistency-tolerant, cost-based query answering can be pushed down to standard database systems rather than requiring specialized reasoners. The Δ²ᵖ and NP/coNP results, by contrast, delineate where such pushdown is not possible and where more expensive reasoning infrastructure is required.

Future Directions

• Extend the AC⁰ result. The tractability result covers certain answers for instance queries and possible answers for conjunctive queries; whether the remaining combinations (certain answers for conjunctive queries, possible answers for instance queries) also fall into AC⁰ for DL-Lite_bool^H is not settled by the stated results.

• Resolve the encoding gap. All results hold for both binary and unary encoding of weights except Δ²ᵖ-hardness, which is only shown for binary encoding, leaving the unary case unanswered.

• Push beyond ALCHIO. The upper bounds stop at ALCHIO; behaviour for more expressive DLs, and for richer query languages beyond conjunctive and instance queries, remains to be explored.

• Refine lower bounds further. Having improved fixed-cost hardness from k ≥ 3 to k ≥ 1, the boundary is tight at k = 0; extending the sharper analyses to further DL-Lite dialects and to the remaining decision problems in Table 1 would round out the picture.

Target Audience

Researchers in knowledge representation and reasoning, description logic, and database theory, particularly those working on ontology-mediated query answering, inconsistency-tolerant semantics, and the computational complexity of reasoning. The paper is also relevant to practitioners building ontology-based data access systems who need to know when inconsistency handling can be compiled into first-order or SQL queries and when it cannot.

Authors’ abstract

In this paper, we study the data complexity of querying inconsistent weighted description logic (DL) knowledge bases under recently-introduced cost-based semantics. In a nutshell, the idea is to assign each interpretation a cost based upon the weights of the violated axioms and assertions, and certain and possible query answers are determined by considering all (resp. some) interpretations having optimal or bounded cost. Whereas the initial study of cost-based semantics focused on DLs between $\mathcal{EL}_\bot$ and $\mathcal{ALCO}$, we consider DLs that may contain inverse roles and role inclusions, thus covering prominent DL-Lite dialects. Our data complexity analysis goes significantly beyond existing results by sharpening several lower bounds and pinpointing the precise complexity of optimal-cost certain answer semantics (no non-trivial upper bound was known). Moreover, while all existing results show the intractability of cost-based semantics, our most challenging and surprising result establishes that if we consider $\text{DL-Lite}^\mathcal{H}_\mathsf{bool}$ ontologies and a fixed cost bound, certain answers for instance queries and possible answers for conjunctive queries can be computed using first-order rewriting and thus enjoy the lowest possible data complexity ($\mathsf{TC}_0$).