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

ABSTRACT

In information extraction, uncertainty is ubiquitous. For this reason, it is useful to provide users querying extracted data with explanations for the answers they receive. Providing the provenance for tuples in a query result partially addresses this problem, in that provenance can explain why a tuple is in the result of a query. However, in some cases explaining why a tuple is not in the result may be just as helpful. In this work we focus on providing provenance-style explanations for non-answers and develop a mechanism for providing this new type of provenance. Our experience with an information extraction prototype suggests that our approach can provide effective provenance information that can help a user resolve their doubts over non-answers to a query.

REFERENCES

• 1: GATE. http://gate.ac.uk/ie/annie.html.
• 2: MALLET. http://mallet.cs.umass.edu.
• 3: Computer Research Association. http://www.cra.org/.
• 4: MinorThird. http://minorthird.sourceforge.net.
• 5: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 6: Deepavali Bhagwat , Laura Chiticariu , Wang-Chiew Tan , Gaurav Vijayvargiya, An annotation management system for relational databases, Proceedings of the Thirtieth international conference on Very large data bases, p.900-911, August 31-September 03, 2004, Toronto, Canada
• 7: C. Binnig, D. Kossmann, E. Lo. Reverse Query Processing. In ICDE, 2007.
• 8: Jihad Boulos , Nilesh Dalvi , Bhushan Mandhani , Shobhit Mathur , Chris Re , Dan Suciu, MYSTIQ: a system for finding more answers by using probabilities, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066277]
• 9: Peter Buneman , Sanjeev Khanna , Wang Chiew Tan, Why and Where: A Characterization of Data Provenance, Proceedings of the 8th International Conference on Database Theory, p.316-330, January 04-06, 2001
• 10: M. J. Cafarella, C. Re, D. Suciu, and O. Etzioni. Structured querying of web text data: A technical challenge. In CIDR, 2007.
• 11: Amit Chandel , P. C. Nagesh , Sunita Sarawagi, Efficient Batch Top-k Search for Dictionary-based Entity Recognition, Proceedings of the 22nd International Conference on Data Engineering, p.28, April 03-07, 2006 [doi>10.1109/ICDE.2006.55]
• 12: Laura Chiticariu , Wang-Chiew Tan , Gaurav Vijayvargiya, DBNotes: a post-it system for relational databases based on provenance, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066296]
• 13: J. Chomicki. Consistent Query Answering: Five Easy Pieces. In ICDT, 2007.
• 14: Eric Chu , Akanksha Baid , Ting Chen , AnHai Doan , Jeffrey Naughton, A relational approach to incrementally extracting and querying structure in unstructured data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 15: W. Cohen and A. McCallum. Information extraction from the web. In KDD, 2003.
• 16: Valter Crescenzi , Giansalvatore Mecca , Paolo Merialdo, RoadRunner: Towards Automatic Data Extraction from Large Web Sites, Proceedings of the 27th International Conference on Very Large Data Bases, p.109-118, September 11-14, 2001
• 17: Yingwei Cui , Jennifer Widom, Lineage Tracing for General Data Warehouse Transformations, Proceedings of the 27th International Conference on Very Large Data Bases, p.471-480, September 11-14, 2001
• 18: Umeshwar Dayal , Philip A. Bernstein, On the updatability of relational views, Proceedings of the fourth international conference on Very Large Data Bases, p.368-377, September 13-15, 1978, West Berlin, Germany
• 19: Pedro DeRose , Warren Shen , Fei Chen , AnHai Doan , Raghu Ramakrishnan, Building structured web community portals: a top-down, compositional, and incremental approach, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 20: AnHai Doan , Raghu Ramakrishnan , Shivakumar Vaithyanathan, Managing information extraction: state of the art and research directions, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142595]
• 21: M. Garofalakis and D. Suciu. Special issue on probabilistic data management. In IEEE Data Engineering Bulletin, 2006.
• 22: Todd J. Green , Grigoris Karvounarakis , Val Tannen, Provenance semirings, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265535]
• 23: M. Gubanov and P. A. Bernstein. Structural text search and comparison using automatically extracted schema. In WebDB, 2006.
• 24: A. Jain, A. Doan, L. Gravano Optimizing SQL Queries over Text Databases In ICDE, 2008.
• 25: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 26: Panagiotis G. Ipeirotis , Eugene Agichtein , Pranay Jain , Luis Gravano, To search or to crawl?: towards a query optimizer for text-centric tasks, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142504]
• 27: T. S. Jayram, R. Krishnamurthy, S. Raghavan, S. Vaithyanathan, and H. Zhu. Avatar information extraction system. IEEE Data Eng. Bull., 29(1), 2006.
• 28: S. Sarawagi. Automation in information extraction and data integration. In VLDB, 2002.
• 29: Warren Shen , Pedro DeRose , Robert McCann , AnHai Doan , Raghu Ramakrishnan, Toward best-effort information extraction, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376718]
• 30: Warren Shen , AnHai Doan , Jeffrey F. Naughton , Raghu Ramakrishnan, Declarative information extraction using datalog with embedded extraction predicates, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 31: D. Suciu. Managing imprecisions with probabilistic databases. In Twente Data Management, 2006.
• 32: W. C. Tan. Research problems in data provenance. IEEE Data Eng. Bull., 27(4), 2004.
• 33: D. Weld, F. Wu, E. Adar, S. Amershi, J. Fogarty, R. Hoffmann, K. Patel, M. Skinner Intelligence in Wikipedia In AAAI, 2008.
• 34: J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In CIDR, 2005.
• 35: Allison Woodruff , Michael Stonebraker, Supporting Fine-grained Data Lineage in a Database Visualization Environment, Proceedings of the Thirteenth International Conference on Data Engineering, p.91-102, April 07-11, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Answer/reason extraction

General Terms:
Algorithms, Design, Performance, Theory