Provenance for nested subqueries

ABSTRACT

Data provenance is essential in applications such as scientific computing, curated databases, and data warehouses. Several systems have been developed that provide provenance functionality for the relational data model. These systems support only a subset of SQL, a severe limitation in practice since most of the application domains that benefit from provenance information use complex queries. Such queries typically involve nested subqueries, aggregation and/or user defined functions. Without support for these constructs, a provenance management system is of limited use.

In this paper we address this limitation by exploring the problem of provenance derivation when complex queries are involved. More precisely, we demonstrate that the widely used definition of Why-provenance fails in the presence of nested subqueries, and show how the definition can be modified to produce meaningful results for nested subqueries. We further present query rewrite rules to transform an SQL query into a query propagating provenance. The solution introduced in this paper allows us to track provenance information for a far wider subset of SQL than any of the existing approaches. We have incorporated these ideas into the Perm provenance management system engine and used it to evaluate the feasibility and performance of our approach.

REFERENCES

• 1: M. O. Akinde et al. Efficient computation of subqueries in complex OLAP. ICDE '03, pages 163--174, 2003.
• 2: 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
• 3: Peter Buneman , James Cheney , Stijn Vansummeren, On the expressiveness of implicit provenance in query and update languages, ACM Transactions on Database Systems (TODS), v.33 n.4, p.1-47, November 2008 [doi>10.1145/1412331.1412340]
• 4: Bin Cao , Antonio Badia, SQL query optimization through nested relational algebra, ACM Transactions on Database Systems (TODS), v.32 n.3, p.18-es, August 2007 [doi>10.1145/1272743.1272748]
• 5: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 6: 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]
• 7: 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]
• 8: Umeshwar Dayal, Processing queries with quantifiers a horticultural approach, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588075]
• 9: Mostafa Elhemali , César A. Galindo-Legaria , Torsten Grabs , Milind M. Joshi, Execution strategies for SQL subqueries, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247598]
• 10: F. Geerts et al. MONDRIAN: Annotating and querying databases through colors and blocks. Technical Report EDIINFRR0243, The University of Edinburgh, 2005.
• 11: B. Glavic et al. Data provenance: A categorization of existing approaches. In BTW '07, pages 227--241, 2007.
• 12: B. Glavic et al. Perm: Processing provenance and data on the same data model through query rewriting. In ICDE '09, 2009.
• 13: 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]
• 14: Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982 [doi>10.1145/319732.319745]
• 15: Bruce Momjian, PostgreSQL: introduction and concepts, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 16: M. Muralikrishna, Improved Unnesting Algorithms for Join Aggregate SQL Queries, Proceedings of the 18th International Conference on Very Large Data Bases, p.91-102, August 23-27, 1992
• 17: M. Mutsuzaki et al. Trio-One: Layering uncertainty and lineage on a conventional DBMS. CIDR '07, pages 269--274, 2007.
• 18: 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]
• 19: W. Tan et al. Provenance in Databases: Past, Current, and Future. IEEE Data Eng. Bull., 30(4):3--12, 2007.
• 20: Transaction Processing Performance Council. TPC-H Benchmark Specification. http://www.tpc.org/hspec.html, 2008.