Mining approximate functional dependencies and concept similarities to answer imprecise queries

ABSTRACT

Current approaches for answering queries with imprecise constraints require users to provide distance metrics and importance measures for attributes of interest. In this paper we focus on providing a domain and end-user independent solution for supporting imprecise queries over Web databases without affecting the underlying database. We propose a query processing framework that integrates techniques from IR and database research to efficiently determine answers for imprecise queries. We mine and use approximate functional dependencies between attributes to create precise queries having tuples relevant to the given imprecise query. An approach to automatically estimate the semantic distances between values of categorical attributes is also proposed. We provide preliminary results showing the utility of our approach.

REFERENCES

• 1: BibFinder: A Computer Science Bibliography Mediator. Available at :http://kilimanjaro.eas.asu.edu/.
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: C. Buckley, G. Salton, and J. Allan. Automatic Retrieval with Locality Information Using Smart. TREC-1, National Institute of Standards and Technology, Gaithersburg, MD, 1992.
• 4: W. W. Chu, Q. Chen, and R. Lee. Cooperative query answering via type abstraction hierarchy. Cooperative Knowledge Based Systems, pages 271--290, 1991.
• 5: W. W. Chu, Q. Chen, and R. Lee. A structured approach for cooperative query answering. IEEE TKDE, 1992.
• 6: William W. Cohen, Integration of heterogeneous databases without common domains using queries based on textual similarity, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.201-212, June 01-04, 1998, Seattle, Washington, United States
• 7: Mehmet M. Dalkilic , Edward L. Roberston, Information dependencies, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.245-253, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.336059]
• 8: N. E. Efthimiadis. Query Expansion. In Annual Review of Information Systems and Technology, Vol. 31, pages 121--187, 1996.
• 9: Roy Goldman , Narayanan Shivakumar , Suresh Venkatasubramanian , Hector Garcia-Molina, Proximity Search in Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.26-37, August 24-27, 1998
• 10: Taher H. Haveliwala , Aristides Gionis , Dan Klein , Piotr Indyk, Evaluating strategies for similarity search on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511502]
• 11: Ykä Huhtala , Juha Kärkkäinen , Pasi Porkka , Hannu Toivonen, Efficient Discovery of Functional and Approximate Dependencies Using Partitions, Proceedings of the Fourteenth International Conference on Data Engineering, p.392-401, February 23-27, 1998
• 12: Jyrki Kivinen , Heikki Mannila, Approximate inference of functional dependencies from relations, Theoretical Computer Science, v.149 n.1, p.129-149, Sept. 18, 1995
• 13: Tony T. Lee, An information-theoretic analysis of relational databases—part I: data dependencies and information metric, IEEE Transactions on Software Engineering, v.13 n.10, p.1049-1061, October 1, 1987 [doi>10.1109/TSE.1987.232847]
• 14: J. M. Morrissey, Imprecise information and uncertainty in information systems, ACM Transactions on Information Systems (TOIS), v.8 n.2, p.159-180, Apr. 1990 [doi>10.1145/96105.96113]
• 15: A. Motro, FLEX: A Tolerant and Cooperative User Interface to Databases, IEEE Transactions on Knowledge and Data Engineering, v.2 n.2, p.231-246, June 1990 [doi>10.1109/69.54722]
• 16: Amihai Motro, VAGUE: a user interface to relational databases that permits vague queries, ACM Transactions on Information Systems (TOIS), v.6 n.3, p.187-214, July 1988 [doi>10.1145/45945.48027]
• 17: K. Nambiar. Some analytic tools for the Design of Relational Database Systems. In Proc. of 6th VLDB, 1980.
• 18: Ullas Nambiar , Subbarao Kambhampati, Providing ranked relevant results for web database queries, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013452]
• 19: Ullas Nambiar , Subbarao Kambhampati, Answering imprecise database queries: a novel approach, Proceedings of the 5th ACM international workshop on Web information and data management, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956699.956727]
• 20: Yahoo! autos. Available at http://autos.yahoo.com/.
• 21: Z. Nie, S. Kambhampati, and T. Hernandez. BibFinder/StatMiner: Effectively Mining and Using Coverage and Overlap Statistics in Data Integration. In Proc. of VLDB, 2003.
• 22: Michael Ortega-Binderberger , Sharad Mehrotra, Integrating similarity based retrieval and query refinement in databases, 2002

INDEX TERMS

Keywords:
approximate functional dependencies, imprecise queries, tuple similarity