pith. sign in

arxiv: 2511.07933 · v2 · submitted 2025-11-11 · 💻 cs.LO

Revisiting Conjunctive Query Entailment for mathcal S

Yazm\'in Ib\'a\~nez-Garc\'ia , Jean Christoph Jung , Vincent Michielini , Filip Murlak This is my paper

Pith reviewed 2026-05-18 00:12 UTC · model grok-4.3

classification 💻 cs.LO
keywords description logicconjunctive query entailmentunions of conjunctive queriestransitive rolescomputational complexity2ExpTimecoNExpTimeS logic
0
0 comments X

The pith

Answering unions of conjunctive queries over S knowledge bases is 2ExpTime-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that conjunctive query entailment for the description logic S, which extends ALC with transitive roles, is 2ExpTime-complete. This corrects earlier partial results that had suggested a possibly lower complexity. The hardness already applies when there are only two transitive roles and when the queries are Boolean. The problem remains in coNExpTime if the query is rooted or if at most one role is transitive, even with many non-transitive roles. Clarifying this boundary matters because S is used to represent knowledge with transitive relations such as hierarchies, and query answering is a core reasoning task over such knowledge bases.

Core claim

We show that the problem of answering unions of conjunctive queries over knowledge bases formulated in the description logic S is in fact 2ExpTime-complete. Hardness already holds in the presence of two transitive roles and for Boolean conjunctive queries. We complement this result by showing that the problem remains in coNExpTime when the input query is rooted or is restricted to use at most one transitive role but may use arbitrarily many non-transitive roles.

What carries the argument

A hardness reduction from a 2ExpTime-complete problem to unions of conjunctive query entailment in S using two transitive roles, paired with an upper-bound algorithm that places the restricted cases in coNExpTime.

If this is right

  • Query answering systems for S must prepare for double-exponential time in the worst case when multiple transitive roles are present.
  • Earlier algorithms based on lower complexity assumptions for S require revision for the general case.
  • Rooted queries or single-transitive-role restrictions allow practical use of coNExpTime procedures.
  • Knowledge bases mixing many non-transitive roles with one transitive role stay within coNExpTime.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar complexity jumps may appear in other description logics when multiple roles receive transitive semantics.
  • Reasoners could gain efficiency by automatically classifying queries as rooted before applying a cheaper procedure.
  • Further syntactic restrictions on queries might produce additional complexity drops worth investigating.

Load-bearing premise

The standard semantics and definition of S as an extension of ALC with transitive roles, together with the standard notion of unions of conjunctive query entailment, are used without extra restrictions.

What would settle it

An explicit algorithm that solves Boolean conjunctive query entailment over S with two transitive roles in less than double-exponential time, or a concrete counterexample showing the reduction for 2ExpTime-hardness fails.

Figures

Figures reproduced from arXiv: 2511.07933 by Filip Murlak, Jean Christoph Jung, Vincent Michielini, Yazm\'in Ib\'a\~nez-Garc\'ia.

Figure 1
Figure 1. Figure 1: Encoding runs of alternating Turing machines. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Detecting copying errors. current using concept names Yσ and the previous one with Zσ where σ ranges over possible cell contents. Nodes u and v encode the number of the cell in binary using concept names B1, . . . , Bn. Each Bi is present in exactly one of the nodes u and v: in u if the ith bit is 0, and in v if it is 1. With a bit of effort one can define a TBox (using additional concept names to propagat… view at source ↗
Figure 3
Figure 3. Figure 3: Interpretation Ja in the two cases. invariant (1) as Ia. In consequence, defining J as J + a0 will complete the proof of Theorem 2. For a ∈ ∆I , the construction of Ja will be held by in￾duction over the set M = VCI t (a) ⊆ NC(T ): we suppose that we already constructed Jc for every c ∈ ∆I such that VCI t (c) ⊊ M. It is based on a dichotomy depending on the set αM =  b ∈ ∆Ia | VCI t (b) = M [PITH_FULL_IM… view at source ↗
Figure 4
Figure 4. Figure 4: (middle) shows a cluster tree for the query on the left. Intuitively, a cluster tree reflects which clusters must be matched below each other, when the query is matched in a transitive-tree interpretation. However, this intuition breaks down as soon as the entry variable of a child cluster is initial in the parent cluster (as for C1 and C4 in [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A naughty query using transitive roles s, t. Coming back to the example in [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Structure of Models configurations of the form w ′ qw′′ where |w ′w ′′| ≤ f(n). It is well-known that there is a fixed 2 n space-bounded ATM M whose word problem is 2EXPTIME-hard (Chandra, Kozen, and Stockmeyer 1981). It is helpful to view the behavior of an ATM on input w in terms of its computation tree, which is a tree of configurations whose root is labeled with the initial configuration q0w, every nod… view at source ↗
Figure 7
Figure 7. Figure 7: Queries qA and final query qw. x y t1 t1 t2 t2 t1 [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Query q ∗ . Now, assume that c and c ′ are B-conspicuous for every B ∈ B. As explained above, this means that valI(c) = valI(c ′ ). Now, as I is proper, the uh element in c and the up element in c ′ must satisfy the same Xq, for q ∈ Q ∪ {□}, and the same Ya, for a ∈ Γ. Then, by Item 2 (ii) of Definition 17, Zq,a is false at the uh element of c; and by Item 2 (iii), Zq,a is false at the vp element of c ′ . … view at source ↗
read the original abstract

We clarify the complexity of answering unions of conjunctive queries over knowledge bases formulated in the description logic $\mathcal S$, the extension of $\mathcal{ALC}$ with transitive roles. Contrary to what existing partial results suggested, we show that the problem is in fact 2ExpTime-complete; hardness already holds in the presence of two transitive roles and for Boolean conjunctive queries. We complement this result by showing that the problem remains in coNExpTime when the input query is rooted or is restricted to use at most one transitive role (but may use arbitrarily many non-transitive roles).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript revisits the complexity of unions of conjunctive query (UCQ) entailment over knowledge bases in the description logic S (ALC extended with transitive roles). It proves that the problem is 2ExpTime-complete in general, with hardness already holding for Boolean conjunctive queries (BCQs) over KBs using exactly two transitive roles. It further establishes coNExpTime membership for the restrictions to rooted queries and to KBs with at most one transitive role (while allowing arbitrarily many non-transitive roles), using automata-based decision procedures.

Significance. If the results hold, this supplies a definitive complexity classification for query entailment in S, correcting earlier partial results that had suggested lower complexity. The tight hardness result for BCQs with two transitive roles and the matching upper bound via automata that correctly handle transitivity are valuable contributions to description logic reasoning. The coNExpTime bounds for the rooted-query and single-transitive-role cases, obtained by bounding state spaces without extra exponential blow-up, provide useful practical distinctions.

minor comments (2)
  1. In the abstract and introduction, the precise definition of 'rooted' queries could be stated more explicitly to aid readers unfamiliar with the term in the DL context.
  2. Section 4 (or the automata construction section): a short remark on how the state-space bounding avoids the extra exponential factor present in the general case would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review of the manuscript and for recommending acceptance. We appreciate the recognition that the results provide a definitive complexity classification for UCQ entailment in S, including the tight 2ExpTime-hardness for Boolean queries with two transitive roles and the coNExpTime upper bounds for the restricted cases.

Circularity Check

0 steps flagged

No significant circularity in complexity classification

full rationale

The derivation of 2ExpTime-completeness for UCQ entailment in S proceeds via an explicit reduction establishing hardness already for BCQs over KBs with two transitive roles, paired with a matching automata-based decision procedure for the upper bound that incorporates transitivity without self-referential definitions. The coNExpTime results for rooted queries and single-transitive-role restrictions follow from direct state-space bounding arguments. These steps rely on standard reductions and automata constructions rather than fitted inputs renamed as predictions, self-citation chains, or ansatzes smuggled via prior work by the same authors. The paper is self-contained against external benchmarks in description logic complexity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard definition and semantics of description logic S and the standard definition of conjunctive query entailment from prior literature.

axioms (1)
  • domain assumption Standard semantics of description logic S as extension of ALC with transitive roles.
    The paper assumes the conventional definition of S from the description logic literature.

pith-pipeline@v0.9.0 · 5405 in / 1083 out tokens · 48307 ms · 2026-05-18T00:12:08.560566+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Partially Finite Model Reasoning in Description Logics Extended Version

    cs.LO 2026-04 unverdicted novelty 7.0

    Partially finite conjunctive query entailment in the description logic S is in 2-EXPTIME via infinite model surgery.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages · cited by 1 Pith paper

  1. [1]

    InPro- ceedings of the 23rd International Workshop on Description Logics (DL 2010), volume 573 ofCEUR Workshop Proceed- ings

    Query Answering in the Description Logic S. InPro- ceedings of the 23rd International Workshop on Description Logics (DL 2010), volume 573 ofCEUR Workshop Proceed- ings. CEUR-WS.org. Calvanese, D.; Eiter, T.; and Ortiz, M. 2014. Answering regular path queries in expressive Description Logics via alternating tree-automata.Inf. Comput., 237: 12–55. Chandra,...

    work page 2010

  2. [2]

    Hence, elements up and uh store the actual content of the tape cells of the previous and the current configuration, respectively

    the elements between up and vp and between uh and vh have (anonymous) t1-successors, and vp and vh have (anonymous)t 2-successors, as shown in Figure 6 (I). Hence, elements up and uh store the actual content of the tape cells of the previous and the current configuration, respectively. Elements vp, wp, vh, wh are needed for the syn- chronization later on....

    work page

  3. [3]

    for every j <2 n, d has an αn-successor ej that is a j-cell, referred to asthej-cell ofd

    work page

  4. [4]

    the uh-elements of the j-cells ej, j <2 n, describe a configuration compatible withq, a, i, that is, •theu h-element ofe i satisfiesX q andY a; •theu h-elements of alle j withj̸=isatisfyX □

    work page

  5. [5]

    The reader might have noticed that Definition 18 does not mention any tree structure, unlike the intuition given in the beginning of the proof

    if q̸=q 0, then the up-elements of the j-cells ej, j < 2n, describe a configuration (in the way specified above) such that the configuration stored in the uh-elements is a successor configuration of the one stored in the up- elements. The reader might have noticed that Definition 18 does not mention any tree structure, unlike the intuition given in the be...

    work page

  6. [6]

    the root d0 of I has an α-successor d that is a (q0, a,0) - configuration node whose i-cells describe the initial con- figuration for inputw; 3This is an analogue of Definition 2 in (Eiter et al. 2009a). Con- dition 3 is not part of the conference version, but is used in the technical report (Eiter et al. 2009b)

    work page

  7. [7]

    We call the computation tree I acceptingif q=q acc in each (q, a, i)-configuration node without successor configu- ration nodes

    for each (q, a, i)-configuration node d, if q∈Q ∃ (resp., q∈Q ∀), then for some (resp., for all) transitions (p,, ¯ ℓ)∈δ(q, a) there is an α2-successor e of d that is a(p, a ′, i+ℓ)-configuration node for somea ′ ∈Γ. We call the computation tree I acceptingif q=q acc in each (q, a, i)-configuration node without successor configu- ration nodes. Furthermore...

    work page

  8. [8]

    For any Boolean CQ q, we have I |=q iff I |=q ≈ for all I ∈T

    work page

  9. [9]

    For any unary CQ q(x), we have ⟨I, a⟩ |=q(x) iff ⟨I, a⟩ |=q ≈([x])for allI ∈T

    work page

  10. [10]

    only if” direction. Let us now prove the “if

    For any unary CQ q(x) such that ⟨I, a⟩ |=q(x) for some I ∈T with root a, no variable in q≈ is reachable from variables [y] and [y′] such that r([x],[y]), s([x],[y ′])∈ q≈ for somer̸=s. Proof. Items 1 and 2 follow from the fact that in every match δ of q in I for some I ∈T , we have δ(x) =δ(y) , for all x≈y . This can easily be proved by induction on the d...

    work page

  11. [11]

    (Note that, due to Condition (‡), there is at most one such x, and by Condition (ii) it is initial inC.)

    If there exists in q′ an atom of the shape r(y, x) with x∈ var(C) and r̸=t , then q′′ contains the atom r(y, xC 0 ). (Note that, due to Condition (‡), there is at most one such x, and by Condition (ii) it is initial inC.)

    work page

  12. [12]

    A(x)), with r̸=t and x∈ var(C) of level i≤ℓ , q′′ contains the atom r(xC i , y) (resp

    For each atom r(x, y) (resp. A(x)), with r̸=t and x∈ var(C) of level i≤ℓ , q′′ contains the atom r(xC i , y) (resp. A(xC i )). Let I be the query q′′ viewed as an interpretation in the stan- dard way. By construction, q′ has a match to the transitive closure of I. It remains to argue that q′′ (and hence I) is tree-shaped. Observe that each variable x in q...

    work page 2008

  13. [13]

    For each Boolean UCQQ with K ̸|=Q , there is anNI(A)- forest interpretationJsuch thatJ + ⊨KbutJ + ̸|=Q

    work page

  14. [14]

    We now develop query decompositions, with the intention of decomposing possible matches of a CQ to forest interpre- tations

    For each tuple ¯afrom NI(A) and each rooted UCQ Q(¯x) with K ̸|=Q(¯a), there is an NI(A)-forest interpretation Jsuch thatJ + ⊨Kbut⟨J +,¯a⟩ ̸|=Q(⃗ x). We now develop query decompositions, with the intention of decomposing possible matches of a CQ to forest interpre- tations. We need two auxiliary notions. Asubdivisionof a CQ q is any CQ that can be obtaine...

    work page

  15. [15]

    For every q∈Q , every subdivision p of q and every admissible Θ-split σ= (U a, Va)a∈Θ of p such that xi ∈ Uai for each i≤n and δΘ is a match ofcpσ in J , there is somea∈Θsuch thatU a ̸=∅andp a σ(xa)∈Q 1 a

    work page

  16. [16]

    For everya∈Θ, we have⟨T,tp(J, a)⟩ ̸|=Q 1 a. Moreover, in the “only if” direction, the family of rooted UCQs can be chosen so that the cardinality of each Q1 a is exponential in ∥Q∥, yet the size of CQ in Q1 a is polynomial (even linear) in∥Q∥. Proof. For the ”if”-direction, let us assume that there is a model J of A and {A⊑ ∀r.B|A⊑ ∀r.B∈ T } that interpre...

    work page

  17. [17]

    each TQ inQhas at mostnvariables. Proof. Let q(x) be a rooted unary CQ with n variables and mentioning concept namesCNand role namesRN. For the construction, we consider the class I of tree inter- pretations I with domain contained in {1, . . . , n}and root 1 that interpret only CN and RN as possibly non-empty. Each suchIcan be viewed as a TQq I(x1)as fol...

    work page

  18. [18]

    For every q∈Q and every admissible Θ-split σ= (Ua, Va)a∈Θ of a subdivision p of q such that δΘ is a match ofcpσ to J , there is some a∈Θ such that one of the following holds: •U a ̸=∅ and the connected component of pa σ(xa) con- tainingx a is inQ 1 a; or •V a ̸=∅and some Boolean subquery ofp a σ is inQ 0 a

    work page

  19. [19]

    For everya∈Θ, we have⟨T,tp(J, a)⟩ ̸|=Q 0 a ∨Q 1 a. Moreover, in the “only if” direction, the UPTQs can be cho- sen so that, for every a∈N I(A), the size of Q0 a is linear in ∥Q∥, the size of Q1 a is exponential in ∥Q∥, yet the number of subPTQs of PTQs inQ 1 a is polynomial in∥Q∥. Proof. For the ”if”-direction, let us assume that there is a model J of A a...

    work page