On the provenance of non-answers to queries over extracted data

Jiansheng Huang, Ting Chen, AnHai Doan, Jeffrey F. NaughtonPVLDB 2008 · DOI

TL;DR

This paper introduces a novel approach to "provenance of non-answers" for information extraction (IE) systems. It provides explanations for why a query might not return a result, going beyond traditional provenance that only explains why something is in the result. This helps users and developers debug IE systems and build confidence in their outputs.

What Problem Does This Paper Address?

Information extraction (IE) systems aim to bridge the gap between unstructured text and structured data, allowing users to query information. However, IE is inherently imprecise, leading to errors in extracted data. While traditional "provenance" can explain why a specific data point is in a query result (e.g., "this fact came from document X"), it doesn't explain why something isn't in the result – the "non-answer." This is a critical gap, as users might be surprised by missing information (e.g., a person not appearing on a conference program committee). Understanding these non-answers is crucial for debugging IE systems and building user trust. The challenge is that the set of potential reasons for a non-answer can be vast or even infinite.

Methods

The core contribution is a framework for computing the "provenance of non-answers." The key idea is to define "potential answers" – non-answers that could become answers with specific, allowable modifications to the database (insertions or updates to untrusted data). The provenance of such a potential answer then describes the minimal set of modifications and original tuples required to make it appear in the query result.

To manage the potentially infinite space of non-answers, they introduce:

  • Proxy Tuples: These act as placeholders for potential new tuples that could be inserted into untrusted tables.
  • Trust and Constraints: Users can specify which tables or attributes are "trusted" (meaning they are assumed correct and complete). This significantly prunes the search space for potential modifications, focusing on untrusted parts of the data. Integrity constraints (like unique keys) are also leveraged.
  • SQL-based Computation: The provenance computation is designed to be executable using standard SQL queries, allowing it to leverage existing database management systems.

The algorithm involves augmenting the original query with predicates that represent potential updates and then executing a specialized "provenance query" to identify the necessary modifications and original data.

Datasets

The paper uses a running example involving CS PhD program rankings and job openings. For evaluation, they create a prototype IE system that extracts this information from web documents. They then scale up this prototype database by a factor of 100 to test performance and scalability. No new benchmark datasets are introduced.

Key Insights and Ideas

  • Provenance for "Absence": The most significant insight is extending the concept of provenance from explaining "presence" to explaining "absence." This is crucial for debugging and trust in data-driven systems.
  • "Potential Answers" as the Key: By focusing on non-answers that could become answers through specific, allowable changes, the problem becomes tractable.
  • Trust as a Pruning Mechanism: User-defined trust in data sources or attributes is a powerful tool to drastically reduce the complexity of provenance computation and make the results more focused and meaningful.
  • SQL for Provenance: Demonstrating that provenance queries can be expressed and executed in SQL is a practical advantage, enabling integration with existing database infrastructure.
  • Debugging Aid: The paper shows a real-world example where their provenance output helped identify and fix a bug in their IE prototype (a truncated document leading to a false non-answer).

Key Results

  • The proposed framework can generate provenance for potential answers, explaining what modifications are needed to turn a non-answer into an answer.
  • The system can distinguish between "potential answers" (which can become answers) and "never-answers" (which cannot).
  • Experiments show that incorporating trust and constraints significantly reduces the number of provenance tuples, making the output more manageable. For example, trusting the ranking table reduced provenance tuples for a specific non-answer from 109 to 1.
  • Performance studies indicate that while provenance queries can be slower than regular queries, especially without trust/constraints, they become comparable when trusted attributes are used for joins.
  • The system successfully identified all potential answers in their running example, demonstrating its utility beyond explaining a single non-answer.

Limitations and Future Work

  • SPJ Queries: The current techniques are primarily designed for Select-Project-Join (SPJ) queries. Extending them to handle more complex SQL features like aggregates and subqueries is noted as future work.
  • Deletions: The current framework focuses on insertions and updates. The impact of deletions on non-answers is not considered.
  • User Interface: While the output is designed to be helpful, the paper doesn't delve into the user interface aspects of presenting this provenance information effectively.
  • Alternative Definitions: The authors suggest exploring alternative definitions for non-answer provenance and different algorithms for computing it.
  • Broader Utility: Further studies are needed to assess the utility of this provenance information for users and developers in deployed IE applications.

Summary updated

BibTeX
@article{huang2008provenance,
  author = {Jiansheng Huang and Ting Chen and AnHai Doan and Jeffrey F. Naughton},
  title = {{On the provenance of non-answers to queries over extracted data}},
  journal = {Proc. VLDB Endow.},
  year = {2008},
  doi = {10.14778/1453856.1453936},
}

Loading related content...

Figure