Please use this identifier to cite or link to this item: https://doi.org/10.1145/2463676.2465320
Title: Reverse engineering complex join queries
Authors: Zhang, M. 
Elmeleegy, H.
Procopiuc, C.M.
Srivastava, D.
Keywords: Query join graph
Query lattice
SQL query discovery
Issue Date: 2013
Source: Zhang, M.,Elmeleegy, H.,Procopiuc, C.M.,Srivastava, D. (2013). Reverse engineering complex join queries. Proceedings of the ACM SIGMOD International Conference on Management of Data : 809-820. ScholarBank@NUS Repository. https://doi.org/10.1145/2463676.2465320
Abstract: We study the following problem: Given a database D with schema G and an output table Out, compute a join query Q that generates Out from D. A simpler variant allows Q to return a superset of Out. This problem has numerous applications, both by itself, and as a building block for other problems. Related prior work imposes conditions on the structure of Q which are not always consistent with the application, but simplify computation. We discuss several natural SQL queries that do not satisfy these conditions and cannot be discovered by prior work. In this paper, we propose an efficient algorithm that discovers queries with arbitrary join graphs. A crucial insight is that any graph can be characterized by the combination of a simple structure, called a star, and a series of merge steps over the star. The merge steps define a lattice over graphs derived from the same star. This allows us to explore the set of candidate solutions in a principled way and quickly prune out a large number of infeasible graphs. We also design several optimizations that significantly reduce the running time. Finally, we conduct an extensive experimental study over a benchmark database and show that our approach is scalable and accurately discovers complex join queries. Copyright © 2013 ACM.
Source Title: Proceedings of the ACM SIGMOD International Conference on Management of Data
URI: http://scholarbank.nus.edu.sg/handle/10635/78326
ISBN: 9781450320375
ISSN: 07308078
DOI: 10.1145/2463676.2465320
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

21
checked on Feb 21, 2018

Page view(s)

31
checked on Feb 17, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.