Modeling the Data Provenance of Relational Databases Supporting Full-Featured SQL and Procedural Languages
Source abstract
Abstract
Data provenance is information about where data come from (provenance data) and how they transform (provenance transformation). Data provenance is widely used to evaluate data quality, trace errors, audit data, and understand references among data. Current studies on data provenance in relational database management systems (RDBMS) still have limitations in supporting full-featured SQL or procedural languages. With these challenges in mind, we present a formal definition of provenance data and provenance transformation for relational data. Then, we propose a solution to support data provenance in relational databases, including provenance graphs and provenance routes. Our method not only solves the complicated problem of modeling provenance in DBMS but also is capable of extending procedural languages in SQL. We also present ProvPg, a PostgreSQL-based prototype database system supporting data provenance in multiple granularities. ProvPg implements extraction, calculation, query, and visualization of provenance. We perform TPC-H tests for ProvPg and PostgreSQL, respectively. Experimental results show that ProvPg addresses the vision of supporting data provenance with little extra computation overhead for the execution engine, which indicates that our model is applicable to lineage tracing applications.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Scientific Computing and Data Management · Distributed and Parallel Computing Systems · Research Data Management Practices
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Software Engineering, South China University of Technology, Guangzhou 510006, China
China Electronic Product Reliability and Environmental Testing Research Institute, Guangzhou 510610, China
Funding
the Key Laboratory of Industrial Equipment Quality Big Data, MIIT
References (47)
Show source-provided references
1. Al-Mamun, A., Yan, F., and Zhao, D.F. (2021, January 19–22). IEEE SciChain: Blockchain-enabled Lightweight and Efficient Data Provenance for Reproducible Scientific Computing. Proceedings of the 2021 IEEE 37th International Conference on Data Engineering (ICDE 2021), Chania, Greece.10.1109/ICDE51399.2021.00166 ↗
2. Developing a Provenance Warehouse for the Systematic Brain10.1142/S0219622015500418 ↗
3. Benabdelkader, A., Santcroos, M., Madougou, S., Kampen, A.H.C.V., and Olabarriaga, S.D. (2011, January 5–8). A Provenance Approach to Trace Scientific Experiments on a Grid Infrastructure. Proceedings of the 2011 IEEE Seventh International Conference on eScience, Stockholm, Sweden.10.1109/eScience.2011.27 ↗
4. Curated databases
5. A provenance model for control-flow driven scientific workflows10.1016/j.datak.2021.101877 ↗
6. MFC-Prov: Media forensics challenge image provenance evaluation and data analysis on large-scale datasets10.1016/j.neucom.2021.10.042 ↗
7. Automatic capture and efficient storage of e-Science experiment provenance10.1002/cpe.1235 ↗
8. Chacko, A.M., Fairooz, M., and Kumar, S.D.M. (2016, January 21–24). Provenance-Aware NoSQL Databases. Proceedings of the Security in Computing and Communications, SSCC 2016, Jaipur, India.10.1007/978-981-10-2738-3_13 ↗
9. Enhancing Web-based Analytics Applications through Provenance10.1109/TVCG.2018.2865039 ↗
10. Managing rapidly evolving scientific workflows10.1007/11890850_2 ↗
11. CF-PROV: A Content-Rich and Fine-Grained Scientific Workflow Provenance Model10.1109/ACCESS.2019.2900738 ↗
12. On the Expressiveness of Implicit Provenance in Query and Update Languages10.1145/1412331.1412340 ↗
13. Bose, R., and Frew, J. (2004, January 23–23). Composing lineage metadata with XML for custom satellite-derived data products. Proceedings of the 16th International Conference on Scientific and Statistical Database Management, Santorini, Greece.
14. Chiticariu, L., Tan, W.-C., and Vijayvargiya, G. (2005, January 14–16). DBNotes: A post-it system for relational databases based on provenance. Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, Baltimore, MD, USA.10.1145/1066157.1066296 ↗
15. Widom, J. (2005, January 4–7). Trio: A system for integrated management of data, accuracy, and lineage. Proceedings of the 2005 CIDR Conference, Asilomar, CA, USA.
16. An annotation management system for relational databases10.1007/s00778-005-0156-6 ↗
17. Karvounarakis, G., Ives, Z.G., and Tannen, V. (2010, January 6–10). Querying data provenance. Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, Indianapolis, IN, USA.10.1145/1807167.1807269 ↗
18. ProvSQL: Provenance and Probability Management in PostgreSQL10.14778/3229863.3236253 ↗
19. Lineage tracing for general data warehouse transformations10.1007/s00778-002-0083-8 ↗
20. Cui, Y., and Widom, J. (2000, January 5–6). Storing auxiliary data for efficient maintenance and lineage tracing of complex views. Proceedings of the 2nd International Workshop on Design and Management of Data Warehouses (DMDW), Stockholm, Sweden.
21. Buneman, P., Khanna, S., and Wang-Chiew, T. (2001, January 4–6). Why and where: A characterization of data provenance. Proceedings of the International Conference on Database Theory, London, UK.10.1007/3-540-44503-X_20 ↗
22. Green, T.J., Karvounarakis, G., and Tannen, V. (2007, January 11–13). Provenance semirings. Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Beijing, China.10.1145/1265530.1265535 ↗
23. Glavic, B. (2010). Perm: Efficient Provenance Support for Relational Databases. [Ph.D. Thesis, University of Zurich].
24. Glavic, B., and Alonso, G. (April, January 29). Perm: Processing provenance and data on the same data model through query rewriting. Proceedings of the 2009 IEEE 25th International Conference on Data Engineering, Shanghai, China.10.1109/ICDE.2009.15 ↗
25. Wang, Y.R., and Madnick, S.E. (1990, January 13–16). A polygen model for heterogeneous database systems: The source tagging perspective. Proceedings of the 16th International Conference on Very Large Data Bases, Brisbane, Australia.
26. Hachem, N.I., Qiu, K., Gennert, M., and Ward, M. (1993, January 24–27). Managing derived data in the Gaea scientific DBMS. Proceedings of the 19th International Conference on Very Large Data Bases, Dublin, Ireland.
27. Faloutsos, C., Jagadish, H., and Sidiropoulos, N.D. (1997, January 26–29). Recovering information from summary data. Proceedings of the 23rd International Conference on Very Large Data Bases, Athens, Greece.
28. Woodruff, A., and Stonebraker, M. (1997, January 7–11). Supporting fine-grained data lineage in a database visualization environment. Proceedings of the 13th International Conference on Data Engineering, Birmingham, UK.
29. Amsterdamer, Y., Deutch, D., and Tannen, V. (2011, January 12–16). Provenance for aggregate queries. Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Athens, Greece.10.1145/1989284.1989302 ↗
30. The ORCHESTRA collaborative data sharing system10.1145/1462571.1462577 ↗
31. Chiticariu, L., and Tan, W.-C. (2006, January 12–15). Debugging schema mappings with routes. Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea.
32. Alvaro, P., Rosen, J., and Hellerstein, J.M. (June, January 31). Lineage-driven fault injection. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Australia.10.1145/2723372.2723711 ↗
33. Distributed time-aware provenance10.14778/2535568.2448939 ↗
34. Titian: Data provenance support in spark10.14778/2850583.2850595 ↗
35. Zhou, W., Fei, Q., Sun, S., Tao, T., Haeberlen, A., Ives, Z., Loo, B.T., and Sherr, M. (2011, January 12–16). NetTrails: A declarative platform for maintaining and querying provenance in distributed systems. Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, Athens, Greece.10.1145/1989323.1989488 ↗
36. Ikeda, R., Park, H., and Widom, J. (2011, January 9–12). Provenance for generalized map and reduce workflows. Proceedings of the Fifth Biennial Conference on Innovative Data Systems Research, CIDR 2011, Asilomar, CA, USA.
37. Ainy, E., Bourhis, P., Davidson, S.B., Deutch, D., and Milo, T. (2015, January 19–23). Approximated summarization of data provenance. Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, Melbourne, Australia.10.1145/2806416.2806429 ↗
38. Ainy, E., Bourhis, P., Davidson, S.B., Deutch, D., and Milo, T. (2016). PROX: Approximated Summarization of Data Provenance. Advances in Database Technology: Proceedings of the International Conference on Extending Database Technology, Bordeaux, France, 15–18 March 2016, OpenProceedings.org.10.1145/2806416.2806429 ↗
39. Deutch, D., Gilad, A., and Moskovitch, Y. (2015, January 13–17). selp: Selective tracking and presentation of data provenance. Proceedings of the 2015 IEEE 31st International Conference on Data Engineering, Seoul, Korea.10.1109/ICDE.2015.7113407 ↗
40. Selective provenance for datalog programs using top-k queries10.14778/2824032.2824039 ↗
41. Deutch, D., Milo, T., Roy, S., and Tannen, V. (2014, January 24–28). Circuits for Datalog Provenance. Proceedings of the ICDT, Athens, Greece.
42. Nlprov: Natural language provenance10.14778/3007263.3007303 ↗
43. Huq, M.R., Apers, P.M., and Wombacher, A. (2013, January 18–22). ProvenanceCurious: A tool to infer data provenance from scripts. Proceedings of the 16th International Conference on Extending Database Technology, Genoa, Italy.10.1145/2452376.2452475 ↗
44. Provenance for SQL through abstract interpretation: Value-less, but worthwhile10.14778/2824032.2824089 ↗
45. Dietrich, B., Müller, T., and Grust, T. (2016, January 15–16). The Best Bang for Your Bu (ck) g. Proceedings of the EDBT, Bordeaux, France.
46. Buneman, P., Khanna, S., and Tan, W.-C. (2002, January 3–5). On propagation of deletions and annotations through views. Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Madison, WI, USA.10.1145/543613.543633 ↗
47. (2022, October 19). Transaction Processing Performance Council (TPC). 2018. TPC Benchmark H(Decision Support) Standard Specification, Revision 2.18.0. Available online: https://www.tpc.org.