Answering Queries Using Views over Description Logics Knowledge Bases

AAAI 2000

TL;DR

This paper tackles the challenge of answering queries against knowledge bases described by expressive Description Logics (DLs), where information is only available through a set of pre-defined "views." They establish the decidability of this problem and characterize its computational complexity under different assumptions about data completeness and view accuracy, finding it to be coNP-complete in data complexity for closed domains and 2EXPTIME for open domains.

What Problem Does This Paper Address?

Imagine you have a complex knowledge base, like a detailed database of medical information or a sophisticated ontology of biological entities. This knowledge base is described using a powerful logical language (Description Logic, or DL) that allows for intricate relationships and constraints. Now, suppose you can't directly query this entire knowledge base. Instead, you only have access to a set of "views," which are essentially pre-computed answers to specific, simpler queries. The problem this paper addresses is: how can we answer a complex query using only the information provided by these views, while still respecting the underlying rules and constraints of the original knowledge base? This is crucial for scenarios like data integration, where different data sources are combined, or for optimizing complex queries by leveraging pre-computed results. The paper specifically focuses on a DL that supports n-ary relations (relations with more than two arguments), which is more expressive than many standard DLs.

Methods

The authors tackle this problem by formalizing it within a specific Description Logic called DLR, which supports n-ary relations and qualified number restrictions. They then analyze the problem under different assumptions:

  • Domain Assumptions:
    • Closed Domain: The set of all objects in the knowledge base is exactly the set of objects explicitly mentioned.
  • Open Domain: The set of all objects might be larger than what's explicitly mentioned.
  • View Assumptions:
    • Sound: The view provides some correct answers, but might miss others.
  • Complete: The view provides all correct answers, but might also include some incorrect ones.
  • Exact: The view provides exactly the correct answers.

The core of their method involves reducing the problem of answering queries using views to other known computational problems in DLs. For the closed domain case, they leverage reductions from known NP-complete problems to establish coNP-completeness in data complexity. For the open domain case, they develop a novel encoding of view extensions and query negations into a single, complex DL concept. The satisfiability of this concept then directly corresponds to whether the query answer is derivable from the views. This encoding involves techniques like reification (representing n-ary relations as concepts with functional roles) and the use of object-names.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Decidability is Achieved: Despite the complexity of the DL and the view-based querying, the paper proves that answering queries using views is decidable in all considered scenarios. This is a fundamental result, ensuring that algorithms can, in principle, solve this problem.
  • Complexity Varies Dramatically with Domain Assumptions: The distinction between closed and open domains has a significant impact on computational complexity. While the problem is coNP-complete in data complexity for closed domains, it escalates to 2EXPTIME for open domains. This highlights the importance of understanding the completeness of your data.
  • Views Introduce "Incomplete Information" Challenges: The assumptions about views (sound, complete, exact) directly influence how the information from views is interpreted. This is akin to dealing with incomplete information in databases, but within the richer expressive power of DLs.
  • DLs as a Powerful Framework for Data Integration: The paper demonstrates how expressive DLs can formally capture conceptual data models and be used to reason about data integration scenarios involving views.

Key Results

  • Closed Domain Assumption:
    • Answering queries using views is coNP-complete in data complexity. This means that for a fixed query and knowledge base, the problem of checking if a tuple is not in the answer can be solved efficiently if the number of objects is small.
  • If queries and views are simple (single atoms), the problem remains coNP-complete, assuming fixed maximal arity of relations.
  • For the general case, the problem is in A (a complexity class related to polynomial time with oracles), assuming fixed maximal arity.
  • Open Domain Assumption:
    • The problem is EXPTIME-hard and solvable in 2EXPTIME. This is a significant increase in complexity compared to the closed domain case.
  • If queries and complete/exact views are simple, the problem becomes EXPTIME-complete.

Limitations and Future Work

  • Closing the Complexity Gap: The paper notes that for the closed domain assumption, there's a gap between the established upper bounds (A) and lower bounds (coNP-complete) for the general case. Closing this gap is identified as future work.
  • Perfect Rewritings in Declarative Languages: The authors mention that an algorithm for answering queries using views can be seen as a "perfect rewriting." However, finding such perfect rewritings expressed in more declarative query languages remains an open question.
  • Maximal Rewritings in Polynomial Data Complexity Languages: Another open direction is to find maximal rewritings that belong to languages with polynomial data complexity, especially considering that perfect rewritings might not be achievable in such languages due to the inherent coNP-hardness of data complexity in the closed domain case.
  • Empirical Evaluation: While the paper provides theoretical complexity results, empirical studies on the performance of algorithms for these problems are not discussed.

Summary updated

BibTeX
@inproceedings{2000answering,
  title = {{Answering Queries Using Views over Description Logics Knowledge Bases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2000},
}

Loading related content...

Figure