Abstract
This paper explores the computational complexity of evaluating ontology-mediated queries (OMQs) over databases with bounded cliquewidth. While structural restrictions like bounded treewidth are well-studied for sparse data, cliquewidth offers a more general measure applicable to dense but regular datasets. The authors establish that while OMQ evaluation remains fixed-parameter linear (FPL) with respect to database size, moving from treewidth to cliquewidth incurs a significant "succinctness penalty," often elevating the complexity relative to the query and ontology from single to double exponential.
Introduction
In the field of Knowledge Representation, Ontology-Mediated Querying (OMQ) serves as a powerful paradigm that combines traditional database querying with logical rules (ontologies) to derive implicit information. However, this expressive power comes at a high computational cost, with query evaluation often reaching coNP-completeness even for relatively simple fragments.
To mitigate this, researchers frequently turn to structural restrictions on the database. The most common restriction is bounded treewidth, which characterizes databases that are "tree-like" and inherently sparse. Yet, many real-world datasets—such as social networks or complete relational structures—are dense and do not fit the treewidth model. This paper investigates cliquewidth, a more flexible structural measure that encompasses dense databases constructed through a limited set of operations (e.g., adding edges between all nodes sharing specific labels). The central inquiry is: how does the transition from sparse treewidth-bounded data to dense cliquewidth-bounded data affect the complexity of OMQ?
Methodology and Algorithmic Framework
The authors employ the lens of parameterized complexity, specifically seeking Fixed-Parameter Linear (FPL) algorithms. An algorithm is FPL if its running time is $f(\text{parameter}) \cdot |Database|$, where the parameter typically includes the query size, ontology size, and the cliquewidth $k$. This ensures that the algorithm scales linearly as the database grows, provided the structural complexity remains constant.
Key Techniques:
- Bottom-up Dynamic Programming: The authors design algorithms that operate on a "$k$-expression"—the sequence of operations used to build a database of cliquewidth $k$. By traversing this expression tree, the algorithm can compute query results incrementally.
- Input-Output Assignments (IOAs): To manage the interaction between the database and the ontology, the authors introduce IOAs. These are succinct mathematical summaries that track how different components of the database satisfy or propagate logical constraints defined by the ontology.
- Lower Bound Reductions: To prove the optimality of their upper bounds, the authors utilize the Exponential Time Hypothesis (ETH). They demonstrate that their double-exponential results are likely unavoidable; if faster algorithms existed, it would imply a sub-exponential solution for 3SAT, a scenario considered highly improbable in complexity theory.
The Succinctness Penalty
A primary contribution of this research is the identification of a "succinctness penalty." In the context of the guarded two-variable fragment ($GF_2$), OMQ evaluation is single-exponential on databases with bounded treewidth. However, on databases with bounded cliquewidth, the complexity jumps to double-exponential.
This phenomenon occurs because $GF_2$ can express complex constraints very efficiently. When these succinct constraints are applied to the denser structures permitted by cliquewidth, the state space required to track logical satisfiability during dynamic programming explodes. This highlights a fundamental trade-off: the extra generality provided by cliquewidth comes at a steep price for certain logic languages.
Summary of Complexity Results
The paper provides a detailed taxonomy of OMQ complexity across different logics and query types:
- $\mathcal{ALCI}$ with Atomic Queries (AQs): This represents a "best-case" scenario, achieving FPL with a single-exponential dependence on the parameter ($2^{O(|O| \cdot k)}$).
- $GF_2$ with Atomic Queries: Proved to be double-exponential on cliquewidth-bounded databases. The authors show that achieving a complexity of $2^{2^{o(|Q|)}}$ is impossible under ETH.
- $\mathcal{ALC}$ with Conjunctive Queries (CQs): Moving from simple AQs to more complex CQs triggers a jump to double-exponential complexity on databases with cliquewidth $\geq 3$.
- Treewidth Contrast: The authors provide new upper bounds for $GF_2$ on bounded treewidth, confirming it remains single-exponential and reinforcing that the double-exponential jump is a specific consequence of the density allowed by cliquewidth.
Discussion and Future Directions
While the theoretical results provide a clear map of complexity, several challenges remain for practical application. The "constant" factors in these FPL algorithms—the exponential parts—are mathematically large, necessitating further optimization before they can be implemented in production-ready software.
Furthermore, the authors identify the Unique Name Assumption (UNA) as a critical factor. For ontologies involving functional roles ($\mathcal{ALCF}$), the problem becomes coNP-hard if different names can refer to the same object. They conjecture that enforcing the UNA might restore efficiency.
Future work may also explore the complexity of $(GF_2, UCQ)$ on bounded cliquewidth, which remains an open question, and investigate hybrid querying methods that decompose databases into high-width and low-width components to balance expressivity and performance.
Summary updated