Interactive query refinement

ABSTRACT

We investigate the problem of refining SQL queries to satisfy cardinality constraints on the query result. This has applications to the many/few answers problems often faced by database users. We formalize the problem of query refinement and propose a framework to support it in a database system. We introduce an interactive model of refinement that incorporates user feedback to best capture user preferences. Our techniques are designed to handle queries having range and equality predicates on numerical and categorical attributes. We present an experimental evaluation of our framework implemented in an open source data manager and demonstrate the feasibility and practical utility of our approach.

REFERENCES

• 1: S. Agrawal, S. Chaudhuri, G. Das, and A. Gionis. Automated ranking of database query results. CIDR, 2003.
• 2: S. Börzsönyi, D. Kossmann, and K. Stocker. The skyline operator. ICDE, 2001.
• 3: Nicolas Bruno , Surajit Chaudhuri , Dilys Thomas, Generating Queries with Cardinality Constraints for DBMS Testing, IEEE Transactions on Knowledge and Data Engineering, v.18 n.12, p.1721-1725, December 2006 [doi>10.1109/TKDE.2006.190]
• 4: Michael J. Carey , Donald Kossmann, On saying “Enough already!” in SQL, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.219-230, May 11-15, 1997, Tucson, Arizona, United States
• 5: Surajit Chaudhuri, Generalization and a Framework for Query Modification, Proceedings of the Sixth International Conference on Data Engineering, p.138-145, February 05-09, 1990
• 6: Surajit Chaudhuri , Nilesh Dalvi , Raghav Kaushik, Robust Cardinality and Cost Estimation for Skyline Operator, Proceedings of the 22nd International Conference on Data Engineering, p.64, April 03-07, 2006 [doi>10.1109/ICDE.2006.131]
• 7: Surajit Chaudhuri , Gautam Das , Vagelis Hristidis , Gerhard Weikum, Probabilistic ranking of database query results, Proceedings of the Thirtieth international conference on Very large data bases, p.888-899, August 31-September 03, 2004, Toronto, Canada
• 8: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 9: S. Chaudhuri and V. Narasayya. Program for TPC-D Data generation with skew. ftp://ftp.research.microsoft.com/users/viveknar/tpcdskew.
• 10: W. W. Chu , Q. Chen, A Structured Approach for Cooperative Query Answering, IEEE Transactions on Knowledge and Data Engineering, v.6 n.5, p.738-749, October 1994 [doi>10.1109/69.317704]
• 11: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 12: Marcus Fontoura , Vanja Josifovski , Ravi Kumar , Christopher Olston , Andrew Tomkins , Sergei Vassilvitskii, Relaxation in text search using taxonomies, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453930]
• 13: P. Godfrey. Skyline cardinality for relational processing. FoIKS, 2004.
• 14: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami, Fixed-precision estimation of join selectivity, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.190-201, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153875]
• 15: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 16: D Haussler , E Welzl, Epsilon-nets and simplex range queries, Proceedings of the second annual symposium on Computational geometry, p.61-71, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10522]
• 17: John Hershberger , Nisheeth Shrivastava , Subhash Suri , Csaba D. Toth, Adaptive Spatial Partitioning for Multidimensional Data Streams, Algorithmica, v.46 n.1, p.97-117, September 2006 [doi>10.1007/s00453-006-0070-3]
• 18: Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
• 19: Ihab F. Ilyas , Walid G. Aref , Ahmed K. Elmagarmid, Supporting top-K join queries in relational databases, Proceedings of the 29th international conference on Very large data bases, p.754-765, September 09-12, 2003, Berlin, Germany
• 20: Yannis E. Ioannidis , Stavros Christodoulakis, Optimal histograms for limiting worst-case error propagation in the size of join results, ACM Transactions on Database Systems (TODS), v.18 n.4, p.709-748, Dec. 1993 [doi>10.1145/169725.169708]
• 21: A. Kadlag, A. V. Wanjari, J. Freire, and J. R. Haritsa. Supporting exploratory queries in databases. DASFAA, 2004.
• 22: Nick Koudas , Chen Li , Anthony K. H. Tung , Rares Vernica, Relaxing join and selection queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 23: Gang Luo, Efficient detection of empty-result queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 24: Volker Markl , Vijayshankar Raman , David Simmen , Guy Lohman , Hamid Pirahesh , Miso Cilimdzic, Robust query processing through progressive optimization, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007642]
• 25: S. Martello and P. Toth. Worst-case analysis of greedy algorithms for the subset-sum problem. Math. Programming, 28(2), 1984.
• 26: Chaitanya Mishra , Nick Koudas , Calisto Zuzarte, Generating targeted queries for database testing, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376668]
• 27: V. N. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264--280, 1971.