Introduction
In the early 1990s, the field of Knowledge Representation (KR) faced a fundamental dilemma known as the expressivity-tractability trade-off. Concept languages—now more commonly referred to as Description Logics—were designed to represent and reason about structured knowledge. However, researchers found that as these languages became expressive enough to accurately describe complex real-world domains, the computational cost of reasoning (such as checking if one concept is a subset of another) often became intractable, reaching NP-hard or higher complexity. This paper, originally presented at AAAI-91, proposes a novel architectural shift to circumvent this "computational cliff": decoupling the language used for assertions from the language used for queries.
The Problem of Symmetry
Historically, KR systems utilized the same language for both defining facts in a Knowledge Base (KB) and for formulating questions. This symmetry meant that the system's overall complexity was dictated by the most powerful features allowed in either role. If a user required a sophisticated query feature, that feature typically had to be supported by the entire reasoning engine, often leading to exponential processing times. The authors of this paper ask a pivotal question: Do the languages for assertions and queries have to be identical? They investigate whether a system can maintain a simple, tractable language for the KB while allowing for a much richer, more expressive language for queries.
Methodological Framework: $\mathcal{AL}$ and $\mathcal{QL}$
To test this hypothesis, the authors define and analyze two distinct languages:
- $\mathcal{AL}$ (Attributive Language): This is used for the Knowledge Base. It supports basic concepts, intersections, universal quantification (e.g., "all children are students"), and a limited form of existential quantification.
- $\mathcal{QL}$ (Query Language): This is a significantly more powerful extension of $\mathcal{AL}$. It introduces qualified existential quantification (e.g., "find an individual who has a child who is a doctor," rather than just "someone who has a child"), role conjunctions, and the ability to reference specific collections of individuals.
The ASK Algorithm
The bridge between these two languages is the ASK algorithm. This algorithm employs a tableau-based constraint system to decompose complex $\mathcal{QL}$ queries into simpler, manageable checks against the $\mathcal{AL}$ KB. To ensure efficiency, the algorithm utilizes a memoization-like data structure that tracks (object, sub-concept) pairs, preventing redundant computations. This mechanism is the technical linchpin that allows the system to remain within polynomial time limits.
Key Insights and Theoretical Results
The paper’s most significant contribution is the demonstration of the Power of Asymmetry. The authors prove that while reasoning within the Query Language ($\mathcal{QL}$) alone is NP-hard, querying an $\mathcal{AL}$ knowledge base with $\mathcal{QL}$ remains strictly tractable.
Polynomial Querying
The authors provide formal proof (Theorem 4.2) that the ASK algorithm runs in polynomial time relative to the size of the KB and the query. This provides a theoretical backbone for building efficient query-answering systems that do not sacrifice the user's ability to ask complex questions.
Mapping the Computational Cliff
The research also identifies the specific logical boundaries where tractability fails. For instance, the authors show that adding disjunction (the "OR" operator) to the query language, or moving qualified existential quantification from the query language into the KB itself, immediately renders the system intractable (co-NP-hard or NP-hard). These hardness proofs effectively map the limits of what is computationally feasible for real-time AI systems.
Limitations and Future Work
While the paper establishes a robust theoretical foundation, it acknowledges several limitations:
- ABox vs. TBox: The current model focuses primarily on assertions about individuals (the ABox). It does not fully integrate a "TBox"—the set of complex terminological definitions that are standard in modern Description Logics.
- Implementation Optimizations: Although the algorithm is theoretically polynomial, the authors note that practical applications would require further optimization, potentially drawing from relational database query optimization techniques.
- Query Complexity: The study focuses on queries structured as single concepts. Future research is suggested to explore "conjunctive queries" (sets of assertions) and queries regarding intensional knowledge (the definitions themselves) rather than just the individuals within the KB.
Conclusion
"Concept Languages as Query Languages" remains a foundational text in KR because it challenged the assumption that expressivity must be uniform across a system. By proving that a powerful query language can coexist with a simple knowledge base, the authors provided a roadmap for creating AI systems that are both useful and computationally efficient.
Summary updated