@techreport{TD:100985,
	att_abstract={{We study the following problem: Given a database D with schema G and  
an output table Out, compute a SQL 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 arising in data mining, keyword search and schema 
mapping. All prior work we are aware of imposes limitations on the 
join graph of Q (e.g., the graph must be a subgraph of the schema 
graph, or a tree at instance level). Such limitations are not always 
consistent with the goal of the application, but rather imposed for 
ease of computation. We discuss several natural SQL queries that 
cannot be discovered by prior work.

In this paper, we propose an efficient algorithm that discovers 
queries with arbitrary join graphs. A crucial step is defining and 
exploring a set of lattices over graphs. We prove that our algorithm 
is correct using concepts from graph theory. We also describe several 
optimizations that significantly improve the running time. Finally, 
we conduct an extensive experimental study over a benchmark database 
and show that our approach is fast, scalable, and able to accurately 
discover complex queries.
}},
	att_authors={ds8961, cp2838},
	att_categories={C_NSS.2},
	att_copyright={{ACM}},
	att_copyright_notice={{(c) ACM, 2013. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in 2013 {{, 2013-06-23}}.
}},
	att_donotupload={},
	att_private={false},
	att_projects={},
	att_tags={},
	att_techdoc={true},
	att_techdoc_key={TD:100985},
	att_url={http://web1.research.att.com:81/techdocs_downloads/TD:100985_DS1_2013-07-01T02:14:13.898Z.pdf},
	author={Divesh Srivastava and Cecilia Procopiuc and Meihui Zhang and Hazem Elmeleegy},
	institution={{SIGMOD}},
	month={June},
	title={{Reverse Engineering SQL Answers}},
	year=2013,
}