A knowledge-based approach for selecting information sources

Thomas Eiter, Michael Fink, Hans Tompits

This paper, published in Theory and Practice of Logic Programming in 2006, presents a sophisticated way to solve the "where do I look?" problem in an era of exploding web data.

TL;DR

The authors propose a declarative, knowledge-based framework using Answer-Set Programming (ASP) to automatically select the best information source for a specific query. By combining qualitative rules (like source reliability) with quantitative optimization (like access cost), the system ensures users get the highest-utility answer from a sea of heterogeneous databases.

What Problem Does This Paper Address?

In the early 2000s, the "Information Manifold" was expanding rapidly. While search engines like Google were great for keywords, they struggled with structured data stored in various formats across different providers.

When a user asks a complex question—for example, "Which movies directed by Alfred Hitchcock were released in the 1950s?"—there might be dozens of potential databases to query. Some are highly specialized (a Hitchcock fan site), some are broad but unreliable (a generic movie wiki), and some are expensive or slow to access.

The challenge is Source Selection: How can an automated agent decide which single source is the "best" to answer a specific query? Traditional methods often tried to integrate all sources, which is computationally expensive and prone to data conflicts. This paper argues for a "smart selection" approach instead.

Methods

The authors use Extended Logic Programs (ELPs) under the Answer-Set Semantics—a powerful paradigm for knowledge representation. Their architecture consists of four main components:

  1. Query Analysis: The system parses a formal query (written in XML-QL) into a high-level logical representation. It identifies "Item Reference Paths" (IRPs) to understand exactly what data the user is looking for.
  2. Source Description: A set of facts describing the "meta-knowledge" of available sources, such as their accuracy, coverage of specific topics (e.g., "Source A is great for 1960s horror"), and technical specs (e.g., "Source B is currently down").
  3. Domain Theory: An ontology that provides background knowledge. For instance, it might know that "Alfred Hitchcock" is a "Director" and that "Personalia" is a synonym for "Person."
  4. Source-Selection Program: This is the "brain" of the system. It uses prioritized rules to decide which source fits the query best.

The "Secret Sauce": The authors introduce a novel way to handle Context. In structured data (like XML), the path to a piece of information matters. A rule specifically about a Director/LastName is more "specific" than a general rule about a Person/LastName. The system automatically prioritizes these more specific "contextual" rules to resolve conflicts without the user having to manually rank every single rule.

Datasets

The authors evaluated their approach using a suite of movie-related databases wrapped into XML format:

  • RandomMovies (RM) & RandomPersons (RP): Broad data sets wrapped from the Internet Movie Database (IMDb).
  • EachMovie (EM): A dataset from Compaq focusing on movie ratings.
  • Hitchcock (HC): A specialized subset of IMDb containing only Hitchcock-related data.
  • KellyGrant (KG): A specialized source for movies featuring Grace Kelly or Cary Grant.
  • Horror60 (H60): A collection of 1960s horror movies.

Key Insights and Ideas

  • Qualitative vs. Quantitative: The system uses a two-step selection process. First, it uses qualitative rules to find "eligible" candidates. Then, it uses "weak constraints" (a feature of the DLV system) to perform quantitative optimization—essentially penalizing sources that are slow or have low coverage to find the absolute "best" one.
  • Reasoning over the Unknown: Because it uses logic programming, the system can handle incomplete information. If it doesn't know a source's language, it can assume a default (like English) unless told otherwise.
  • Topic Inference: The system doesn't just look for keywords. Because of the Domain Theory, if you ask about a specific movie title, the system can infer the actors or directors involved and use that information to pick a specialized database.

Key Results

The prototype was implemented using the DLV system (a popular ASP solver).

  • Accuracy: In experimental tests with 18 natural queries, the system consistently selected the "best" source. For a Hitchcock query, it correctly prioritized the specialized Hitchcock database over the general RandomMovies database.
  • Inference Power: For a query about the movie Arsenic and Old Lace, the system used background knowledge to realize Cary Grant was the star and correctly queried the KellyGrant database, even though the user never mentioned Grant.
  • Performance: Selection took anywhere from a few seconds to tens of seconds. While not yet ready for the sub-millisecond requirements of modern web search, it proved that complex logical reasoning could be applied to source selection.

Limitations and Future Work

  • Scalability: The authors acknowledge that as the number of rules and sources grows, the "grounding" process (converting logic rules into a format the solver understands) can become a bottleneck.
  • Manual Effort: Currently, the source descriptions and domain ontologies must be created by an administrator. The authors suggest that future work could involve automatically generating these descriptions.
  • Single Source Focus: The paper primarily focuses on selecting the one best source. Extending this to decompose a query across multiple sources (query planning) is a suggested next step.
  • Integration with DL: The authors point toward future work coupling this logic-based approach with Description Logics (DL) to leverage even more powerful ontological reasoning.

Summary updated

Abstract

Through the Internet and the World-Wide Web, a vast number of information sources has become available, which offer information on various subjects by different providers, often in heterogeneous formats. This calls for tools and methods for building an advanced information-processing infrastructure. One issue in this area is the selection of suitable information sources in query answering. In this paper, we present a knowledge-based approach to this problem, in the setting where one among a set of information sources (prototypically, data repositories) should be selected for evaluating a user query. We use extended logic programs (ELPs) to represent rich descriptions of the information sources, an underlying domain theory, and user queries in a formal query language (here, XML-QL, but other languages can be handled as well). Moreover, we use ELPs for declarative query analysis and generation of a query description. Central to our approach are declarative source-selection programs, for which we define syntax and semantics. Due to the structured nature of the considered data items, the semantics of such programs must carefully respect implicit context information in source-selection rules, and furthermore combine it with possible user preferences. A prototype implementation of our approach has been realized exploiting the DLV KR system and its PLP front-end for prioritized ELPs. We describe a representative example involving specific movie databases, and report about experimental results.
BibTeX
@inproceedings{eiter2007knowledge,
  author = {Thomas Eiter and Michael Fink and Hans Tompits},
  title = {{A knowledge-based approach for selecting information sources}},
  booktitle = {Theory Pract. Log. Program},
  year = {2007},
  url = {https://openreview.net/forum?id=UjmUGQbmlu},
}
Figure