Navigational Plans for Data Integration

AAAI 1999

TL;DR

This paper tackles the challenge of integrating data from "data webs" (like websites with linked pages) rather than traditional relational databases. They introduce a new language (GLAV) for describing these data webs and a method to generate "navigational plans" that guide data integration systems to query and traverse these web structures, making data integration more robust for the modern web.

What Problem Does This Paper Address?

Traditional data integration systems often model data sources as sets of relations. However, the rise of the World Wide Web has introduced a new paradigm: data sources are increasingly structured as interconnected "data webs," where information is linked across pages, and accessing specific data often requires navigating through a series of links or search forms. Existing approaches, which treat each page as an independent source or rely solely on relational models, are insufficient for capturing the navigational aspect and inter-page relationships inherent in these data webs. This paper aims to bridge this gap by providing a formal framework for modeling and querying such web-structured data sources within a data integration system.

Methods

The authors propose a novel approach with three main components:

  • Data Web Modeling: They introduce a "web schema" to formally represent data webs. This schema uses directed graphs where nodes represent sets of pages and edges represent links. Nodes are annotated with information about page content, parameters, entry points, and the nature of links (hyperlinks or search forms).
  • GLAV (Global-as-View Local-as-View) Source Descriptions: They introduce GLAV, a source description language that combines the expressive power of both GAV and LAV approaches. GLAV allows for flexible schema definitions and can handle recursive queries, which are crucial for navigating arbitrarily long paths in data webs. This language is designed to be expressive enough to model complex data webs while maintaining tractability for query answering.
  • Navigational Plans: To execute queries over data webs, they develop a two-step process. First, a user's query over a mediated schema is translated into a "logical plan" using GLAV source descriptions. Second, this logical plan is augmented with "navigational instructions" to create a "navigational plan." This plan specifies how to locate and access the desired data by traversing paths and interacting with search forms within the data webs.

Datasets

Not discussed in the paper. The paper focuses on a formal framework and algorithms, using a hypothetical university domain for illustrative examples rather than specific datasets.

Key Insights and Ideas

  • Data Webs Require New Formalisms: The paper highlights that the linked nature and navigational requirements of data webs necessitate moving beyond traditional relational models for data integration.
  • GLAV's Expressive Power: GLAV is presented as a powerful language that balances expressiveness for complex data web modeling with tractability for query answering, pushing the boundaries of what's possible in data integration.
  • Navigational Plans are Key: The concept of "navigational plans" is a core contribution, bridging the gap between logical query plans and the practical execution of queries on web-structured data by explicitly incorporating traversal instructions.
  • Tractability Limits: The paper demonstrates that while GLAV is powerful, even minor extensions to its expressive power could render query answering co-NP-hard, establishing a practical limit for such systems.

Key Results

  • Sound and Complete Algorithms: The paper presents algorithms for reformulating user queries into logical plans (GlavInverse) and then into navigational plans (Navigational Plan), proving their soundness and completeness.
  • Tractable Query Answering: They show that for conjunctive queries with GLAV source descriptions, both query complexity and data complexity are polynomial, meaning that querying these web-structured sources is computationally feasible.
  • Complexity Boundaries: The paper establishes that GLAV's expressive power is near the limit for tractable query answering, with certain constraints (like X ≠ Y) leading to co-NP-hard data complexity, even for simpler LAV descriptions.

Limitations and Future Work

  • Practical Execution: While the paper outlines how to generate navigational plans, the actual optimization and execution of these plans are acknowledged as beyond the scope of this work, referencing other research for details.
  • Wrapper Construction: The paper assumes the existence of mechanisms (wrappers) to extract structured data from HTML pages, noting that this is a separate research area.
  • Extension with Description Logics: The authors suggest future work in extending their query answering algorithm and complexity results to incorporate additional constraints on mediated schemas using description logics.

Summary updated

BibTeX
@inproceedings{1999navigational,
  title = {{Navigational Plans for Data Integration}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure