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:
- 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.
- 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").
- 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."
- 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
Hitchcockdatabase over the generalRandomMoviesdatabase. - 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
KellyGrantdatabase, 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