On the expressiveness of implicit provenance in query and update languages

ABSTRACT

Information describing the origin of data, generally referred to as provenance, is important in scientific and curated databases where it is the basis for the trust one puts in their contents. Since such databases are constructed using operations of both query and update languages, it is of paramount importance to describe the effect of these languages on provenance.

In this article we study provenance for query and update languages that are closely related to SQL, and compare two ways in which they can manipulate provenance so that elements of the input are rearranged to elements of the output: implicit provenance, where a query or update only provides the rearranged output, and provenance is provided implicitly by a default provenance semantics; and explicit provenance, where a query or update provides both the output and the description of the provenance of each component of the output. Although explicit provenance is in general more expressive, we show that the classes of implicit provenance operations expressible by query and update languages correspond to natural semantic subclasses of the explicit provenance queries.

One of the consequences of this study is that provenance separates the expressive power of query and update languages. The model is also relevant to annotation propagation schemes in which annotations on the input to a query or update have to be transferred to the output or vice versa.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Catriel Beeri , Tova Milo , Paula Ta-Shma, On genericity and parametricity (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.104-116, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237689]
• 3: Catriel Beeri , Tova Milo , Paula Ta-Shma, Towards a Language for the Fully Generic Queries, Proceedings of the 6th International Workshop on Database Programming Languages, p.239-259, August 18-20, 1997
• 4: 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
• 5: Bhagwat, D., Chiticariu, L., Tan, W.-C., and Vijayvargiya, G. 2005. An annotation management system for relational databases. VLDB J. 14, 4, 373--396.
• 6: Rajendra Bose , James Frew, Lineage retrieval for scientific data processing: a survey, ACM Computing Surveys (CSUR), v.37 n.1, p.1-28, March 2005 [doi>10.1145/1057977.1057978]
• 7: Peter Buneman , Adriane Chapman , James Cheney, Provenance management in curated databases, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142534]
• 8: Buneman, P., Cheney, J., and Vansummeren, S. 2007. On the expressiveness of implicit provenance in query and update languages. In Proceedings of the 11th International Conference on Database Theory (ICDT), T. Schwentick and D. Suciu, Eds. Lecture Notes in Computer Science, vol. 4353. Springer, Berlin, Germany, 209--223.
• 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: Peter Buneman , Shamim Naqvi , Val Tannen , Limsoon Wong, Principles of programming with complex objects and collection types, Theoretical Computer Science, v.149 n.1, p.3-48, Sept. 18, 1995
• 11: Ashok K. Chandra, Programming primitives for database languages, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.50-62, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567537]
• 12: Cheney, J., Ahmed, A., and Acar, U. A. 2007. Provenance as dependency analysis. In Proceedings of the 11th International Symposium on Database Programming Languages (DBPL), Vienna, Austria, Lecture Notes in Computer Science, Vol. 4797, Springer, Berlin, Germany, 138--152.
• 13: Yingwei Cui , Jennifer Widom , Janet L. Wiener, Tracing the lineage of view data in a warehousing environment, ACM Transactions on Database Systems (TODS), v.25 n.2, p.179-227, June 2000 [doi>10.1145/357775.357777]
• 14: Foster, I. and Moreau, L., Eds. 2006. Proceedings of the International Provenance and Annotation Workshop (IPAW). Lecture Notes in Computer Science, Vol. 4145, Springer-Verlag, Berlin, Germany.
• 15: Galperin, M. Y. 2008. The molecular biology database collection: 2008 update. Nucl. Acids Res. 36, suppl_1, D2--4.
• 16: Floris Geerts , Anastasios Kementsietsidis , Diego Milano, MONDRIAN: Annotating and Querying Databases through Colors and Blocks, Proceedings of the 22nd International Conference on Data Engineering, p.82, April 03-07, 2006 [doi>10.1109/ICDE.2006.102]
• 17: Geerts, F. and Van den Bussche, J. 2007. Relational completeness of query languages for annotated databases. In Proceedings of the 11th International Symposium on Database Programming Languages (DBPL), Vienna, Austria, Lecture Notes in Computer Science, Vol. 4797, Springer, Berlin, Germany, 127--137.
• 18: 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]
• 19: Leonid Libkin , Limsoon Wong, Query languages for bags and aggregate functions, Journal of Computer and System Sciences, v.55 n.2, p.241-272, Oct. 1997 [doi>10.1006/jcss.1997.1523]
• 20: Hartmut Liefke , Susan B. Davidson, Specifying Updates in Biomedical Databases, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.44, July 28-30, 1999 [doi>10.1109/SSDM.1999.787620]
• 21: Jan Paredaens , Dirk Van Gucht, Converting nested algebra expressions into flat algebra expressions, ACM Transactions on Database Systems (TODS), v.17 n.1, p.65-93, March 1992 [doi>10.1145/128765.128768]
• 22: Yogesh L. Simmhan , Beth Plale , Dennis Gannon, A survey of data provenance in e-science, ACM SIGMOD Record, v.34 n.3, September 2005 [doi>10.1145/1084805.1084812]
• 23: Dan Suciu, Bounded fixpoints for complex objects, Theoretical Computer Science, v.176 n.1-2, p.283-328, April 20, 1997 [doi>10.1016/S0304-3975(96)00293-9]
• 24: Tan, W. 2003. Containment of relational queries with annotation propagation. In Proceedings of the 9th International Workshop on Database Programming Languages (DBPL). Lecture Notes in Computer Science, vol. 2921. Springer, Berlin, Germany, 37--53.
• 25: Tan, W. 2004. Research problems in data provenance. IEEE Data Eng. Bull. 27, 4, 45--52.
• 26: Jan Van den Bussche, Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions, Theoretical Computer Science, v.254 n.1-2, p.363-377, March 6, 2001 [doi>10.1016/S0304-3975(99)00301-1]
• 27: Y. Richard Wang , Stuart E. Madnick, A Polygen Model for Heterogeneous Database Systems: The Source Tagging Perspective, Proceedings of the 16th International Conference on Very Large Data Bases, p.519-538, August 13-16, 1990
• 28: Limsoon Wong , Peter Buneman, Querying nested collections, University of Pennsylvania, Philadelphia, PA, 1994
• 29: Limsoon Wong, Normal forms and conservative extension properties for query languages over collection types, Journal of Computer and System Sciences, v.52 n.3, p.495-505, June 1996 [doi>10.1006/jcss.1996.0037]
• 30: Limsoon Wong, Kleisli, a functional query system, Journal of Functional Programming, v.10 n.1, p.19-56, January 2000 [doi>10.1017/S0956796899003585]
• 31: 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.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs

General Terms:
Languages, Reliability, Theory

Keywords:
Provenance, conservativity, nested relational calculus, nested update language