Query by output

ABSTRACT

It has recently been asserted that the usability of a database is as important as its capability. Understanding the database schema, the hidden relationships among attributes in the data all play an important role in this context. Subscribing to this viewpoint, in this paper, we present a novel data-driven approach, called Query By Output (QBO), which can enhance the usability of database systems. The central goal of QBO is as follows: given the output of some query Q on a database D, denoted by Q(D), we wish to construct an alternative query Q′ such that Q(D) and Q′ (D) are instance-equivalent. To generate instance-equivalent queries from Q(D), we devise a novel data classification-based technique that can handle the at-least-one semantics that is inherent in the query derivation. In addition to the basic framework, we design several optimization techniques to reduce processing overhead and introduce a set of criteria to rank order output queries by various notions of utility. Our framework is evaluated comprehensively on three real data sets and the results show that the instance-equivalent queries we obtain are interesting and that the approach is scalable and robust to queries of different selectivities.

REFERENCES

• 1: Periklis Andritsos , Renée J. Miller , Panayiotis Tsaparas, Information-theoretic tools for mining database structure from large data sets, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007650]
• 2: C. Binnig, D. Kossmann, and E. Lo. Reverse query processing. In ICDE, pages 506--515, 2007.
• 3: Carsten Binnig , Donald Kossmann , Eric Lo , M. Tamer Özsu, QAGen: generating query-aware test databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247520]
• 4: Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
• 5: 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]
• 6: Peter Buneman , James Cheney , Wang-Chiew Tan , Stijn Vansummeren, Curated databases, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376918]
• 7: T. Gaasterl, P. Godfrey, and J. Minker. An overview of cooperative answering. Journal of Intelligent Information Systems, (2):123--157, 1992.
• 8: Lise Getoor , Benjamin Taskar , Daphne Koller, Selectivity estimation using probabilistic models, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.461-472, May 21-24, 2001, Santa Barbara, California, United States
• 9: Parke Godfrey , Jarek Gryz , Calisto Zuzarte, Exploiting constraint-like data characterizations in query optimization, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.582-592, May 21-24, 2001, Santa Barbara, California, United States
• 10: H. V. Jagadish , Adriane Chapman , Aaron Elkiss , Magesh Jayapandian , Yunyao Li , Arnab Nandi , Cong Yu, Making database systems usable, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247483]
• 11: T. Johnson, A. Marathe, and T. Dasu. Database exploration and bellman. 26(3):34--39, 2003.
• 12: Georgia Koutrika , Alkis Simitsis , Yannis Ioannidis, Précis: The Essence of a Query Answer, Proceedings of the 22nd International Conference on Data Engineering, p.69, April 03-07, 2006 [doi>10.1109/ICDE.2006.114]
• 13: Manish Mehta , Rakesh Agrawal , Jorma Rissanen, SLIQ: A Fast Scalable Classifier for Data Mining, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.18-32, March 25-29, 1996
• 14: 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]
• 15: A. Motro, Intensional Answers to Database Queries, IEEE Transactions on Knowledge and Data Engineering, v.6 n.3, p.444-454, June 1994 [doi>10.1109/69.334858]
• 16: Pang-Ning Tan , Michael Steinbach , Vipin Kumar, Introduction to Data Mining, (First Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 17: Naren Ramakrishnan , Deept Kumar , Bud Mishra , Malcolm Potts , Richard F. Helm, Turning CARTwheels: an alternating algorithm for mining redescriptions, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014083]
• 18: J. Rissanen. Modeling by shortest data description. Automatica, 14:465--471, 1978.
• 19: A. Simitsis, G. Koutrika, and Y. E. Ioannidis. Generalized précis queries for logical database subset creation. In ICDE, pages 1382--1386, 2007.
• 20: Q. T. Tran, C.-Y. Chan, and S. Parthasarathy. Query by output. Technical Report TRA4/09, National University of Singapore - School of Computing, April 2009.
• 21: Patrick Valduriez, Join indices, ACM Transactions on Database Systems (TODS), v.12 n.2, p.218-246, June 1987 [doi>10.1145/22952.22955]
• 22: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 23: Wensheng Wu , Berthold Reinwald , Yannis Sismanis , Rajesh Manjrekar, Discovering topical structures of databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376717]
• 24: Xiaokui Xiao , Yufei Tao, Output perturbation with query relaxation, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453949]
• 25: Moshé M. Zloof, Query by example, Proceedings of the May 19-22, 1975, national computer conference and exposition, May 19-22, 1975, Anaheim, California [doi>10.1145/1499949.1500034]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Design

Keywords:
at-least-one semantics, instance-equivalent queries, query by output