research-article

Provenance for SQL through abstract interpretation: value-less, but worthwhile

Editors: Chen Li, Volker Markl Authors:

Tobias Müller,

Torsten GrustAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 8, Issue 12

Pages 1872 - 1875

https://doi.org/10.14778/2824032.2824089

Published: 01 August 2015 Publication History

Get Access

Abstract

We demonstrate the derivation of fine-grained where- and why-provenance for a rich dialect of SQL that includes recursion, (correlated) subqueries, windows, grouping/aggregation, and the RDBMS's library of built-in functions. The approach relies on ideas that originate in the programming language community---program slicing and abstract interpretation, in particular. A two-stage process first records a query's control flow decisions and locations of data access before it derives provenance without consultation of the actual data values (rendering the method largely "value-less"). We will bring an interactive demonstrator that uses this provenance information to make input/output dependencies in real-world SQL queries tangible.

References

[1]

P. Buneman, S. Khanna, and W.-C. Tan. Why and Where: A Characterization of Data Provenance. In Proc. ICDT, 2001.

Crossref

Google Scholar

[2]

J. Cheney, L. Chiticariu, and W.-C. Tan. Provenance in Databases: Why, How, and Where. Foundations and Trends in Databases, 1(4), 2007.

Crossref

Google Scholar

[3]

P. Cousot and R. Cousot. Inductive Definitions, Semantics and Abstract Interpretation. In Proc. POPL, 1992.

Crossref

Google Scholar

[4]

Y. Cui, J. Widom, and J. Wiener. Tracing the Lineage of View Data in a Warehousing Environment. ACM TODS, 25(2), 2000.

Crossref

Google Scholar

[5]

B. Glavic and G. Alonso. Provenance for Nested Subqueries. In Proc. EDBT, 2009.

Crossref

Google Scholar

[6]

Y. Klonatos, C. Koch, T. Rompf, and H. Chafi. Building Efficient Query Engines in a High-Level language. In Proc. VLDB, 2014.

Crossref

Google Scholar

[7]

T. Neumann. Efficiently Compiling Efficient Query Plans for Modern Hardware. In Proc. VLDB, 2011.

Crossref

Google Scholar

[8]

The PostgreSQL Relational Database System. postgresql.org.

Google Scholar

[9]

The Python Programming Language. python.org.

Google Scholar

[10]

M. Weiser. Program Slicing. IEEE Transactions on Software Engineering, SE-10(4), 1984.

Crossref

Google Scholar

[11]

A. Woodruff and M. Stonebraker. Supporting Fine-Grained Data Lineage in a Database Visualization Environment. In Proc. ICDE, 1997.

Crossref

Google Scholar

Cited By

View all

Usta AKarakayali AUlusoy Ö(2024)xDBTagger: explainable natural language interface to databases using keyword mappings and schema graphThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00809-w33:2(301-321)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s00778-023-00809-w
Shaikhha AElseidy MMihaila SEspino DKoch C(2020)Synthesis of Incremental Linear Algebra ProgramsACM Transactions on Database Systems10.1145/338539845:3(1-44)Online publication date: 26-Aug-2020
https://dl.acm.org/doi/10.1145/3385398
Deutch DFrost NGilad A(2019)Explaining Natural Language query resultsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-019-00584-729:1(485-508)Online publication date: 2-Nov-2019
https://dl.acm.org/doi/10.1007/s00778-019-00584-7
Show More Cited By

Provenance for SQL through abstract interpretation: value-less, but worthwhile
1. Information systems
  1. Data management systems

Recommendations

Sql: Learn Basics of Queries and Implement Easily (sql programming, SQL 2016, sql database programming, sql for beginners, sql beginners guide, sql ... sql workbook, sql guide, MSSQL) (Volume 1)
Using Template Haskell for Abstract Interpretation

Metaprogramming consists of writing programs that generate or manipulate other programs. Template Haskell is a recent extension of Haskell, currently implemented in the Glasgow Haskell Compiler, giving support to metaprogramming at compile time. Our aim ...
Data provenance for recursive SQL queries
TaPP '22: Proceedings of the 14th International Workshop on the Theory and Practice of Provenance

The adoption of recursion in SQL---framed either in terms of recursive common table expressions (CTEs) or recursive user-defined functions (UDFs)---marked a jump in the expressivity of the query language. The resulting queries can perform complex ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 8, Issue 12

Proceedings of the 41st International Conference on Very Large Data Bases, Kohala Coast, Hawaii

August 2015

728 pages

ISSN:2150-8097

Editors:
Chen Li
University of California, Irvine
,
Volker Markl
TU Berlin

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 August 2015

Published in PVLDB Volume 8, Issue 12

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
89
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Usta AKarakayali AUlusoy Ö(2024)xDBTagger: explainable natural language interface to databases using keyword mappings and schema graphThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00809-w33:2(301-321)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s00778-023-00809-w
Shaikhha AElseidy MMihaila SEspino DKoch C(2020)Synthesis of Incremental Linear Algebra ProgramsACM Transactions on Database Systems10.1145/338539845:3(1-44)Online publication date: 26-Aug-2020
https://dl.acm.org/doi/10.1145/3385398
Deutch DFrost NGilad A(2019)Explaining Natural Language query resultsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-019-00584-729:1(485-508)Online publication date: 2-Nov-2019
https://dl.acm.org/doi/10.1007/s00778-019-00584-7
O'Grady DMüller TGrust THerschel M(2018)How how explains what what computesProceedings of the 10th USENIX Conference on Theory and Practice of Provenance10.5555/3319379.3319391(8-8)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.5555/3319379.3319391
Müller TDietrich BGrust T(2018)You say 'what', i hear 'where' and 'why'Proceedings of the VLDB Endowment10.14778/3236187.323620411:11(1536-1549)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.14778/3236187.3236204
Deutch DFrost NGilad A(2017)Provenance for natural language queriesProceedings of the VLDB Endowment10.14778/3055540.305555010:5(577-588)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.14778/3055540.3055550
Herschel MDiestelkämper RBen Lahmar H(2017)A survey on provenanceThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-017-0486-126:6(881-906)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s00778-017-0486-1

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Sql: Learn Basics of Queries and Implement Easily (sql programming, SQL 2016, sql database programming, sql for beginners, sql beginners guide, sql ... sql workbook, sql guide, MSSQL) (Volume 1)

Using Template Haskell for Abstract Interpretation

Data provenance for recursive SQL queries