K-relevance: a spectrum of relevance for data sources impacting a query

ABSTRACT

Applications ranging from grid management to sensor nets to web-based information integration and extraction can be viewed as receiving data from some number of autonomous remote data sources and then answering queries over this collected data. In such environments it is helpful to inform users which data sources are "relevant" to their query results. It is not immediately obvious what "relevant" should mean in this context, as different users will have different requirements. In this paper, rather than proposing a single definition of relevance, we propose a spectrum of definitions, which we term "k-relevance", for k ≥ 0. We give algorithms for identifying k-relevant data sources for relational queries and explore their efficiency both analytically and experimentally. Finally, we explore the impact of integrity constraints (including dependencies) and materialized views on the problem of computing and maintaining relevant data sources.

REFERENCES

• 1: D. Agrawal , A. El Abbadi , A. Singh , T. Yurek, Efficient view maintenance at data warehouses, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.417-427, May 11-15, 1997, Tucson, Arizona, United States
• 2: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 3: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• 4: Rajendra Bose , James Frew, Lineage retrieval for scientific data processing: a survey, ACM Computing Surveys (CSUR), v.37 n.1, p.1-28, March 2005 [doi>10.1145/1057977.1057978]
• 5: Peter Buneman , Sanjeev Khanna , Wang Chiew Tan, Why and Where: A Characterization of Data Provenance, Proceedings of the 8th International Conference on Database Theory, p.316-330, January 04-06, 2001
• 6: Stefano Ceri , Jennifer Widom, Deriving Production Rules for Incremental View Maintenance, Proceedings of the 17th International Conference on Very Large Data Bases, p.577-589, September 03-06, 1991
• 7: Soumen Chakrabarti , Kunal Punera , Mallela Subramanyam, Accelerated focused crawling through online relevance feedback, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511466]
• 8: Y. Cui and J. Widom. Practical lineage tracing in data warehouses. In ICDE, pages 367--378, 2000.
• 9: Yingwei Cui , Jennifer Widom, Lineage Tracing for General Data Warehouse Transformations, Proceedings of the 27th International Conference on Very Large Data Bases, p.471-480, September 11-14, 2001
• 10: A. Doan, R. Ramakrishnan, F. Chen, P. DeRose, Y. Lee, R. McCann, M. Sayyadian, and W. Shen. Community information management. IEEE Data Eng. Bull., 29(1):64--72, 2006.
• 11: A. Gupta and I. S. Mumick. Maintenance of materialized views: Problems, techniques, and applications. IEEE Data Eng. Bull., 18(2):3--18, 1995.
• 12: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 13: Jiansheng Huang , Jeffrey F. Naughton , Miron Livny, TRAC: toward recency and consistency reporting in a database with distributed data sources, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 14: Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
• 15: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 16: Hartmut Liefke , Susan B. Davidson, View Maintenance for Hierarchical Semistructured Data, Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, p.114-125, September 04-06, 2000
• 17: D. J. Rosenkrantz and H. B. Hunt. Processing conjunctive predicates and queries. In VLDB, pages 64--72, 1980.
• 18: Oded Shmueli , Alon Itai, Maintenance of views, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 19: Yue Zhuge , Héctor García-Molina , Joachim Hammer , Jennifer Widom, View maintenance in a warehousing environment, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.316-327, May 22-25, 1995, San Jose, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
k-relevance, k-relevant, lineage relevance, materialized view, relevant sources, update relevance