Determining source contribution in integration systems

ABSTRACT

Owners of sources registered in an information integration system, which provides answers to a (potentially evolving) set of client queries, need to know their contribution to the query results. We study the problem of deciding, given a client query Q and a source registration R, whether R is (i) "self-sufficient" (can contribute to the result of Q even if it is the only source in the system) or (ii) "now complementary" (can contribute, but only in cooperation with other specific existing sources), or (iii)"later complementary" (can contribute if in the future appropriate new sources join the system). We consider open-world integration systems in which registrations are expressed using source-to-target constraints, and queries are answered under "certain answer" semantics.

REFERENCES

• 1: Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275516]
• 2: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: Andrea Calì , Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Data Integration under Integrity Constraints, Proceedings of the 14th International Conference on Advanced Information Systems Engineering, p.262-279, May 27-31, 2002
• 4: Andrea Cali, Giuseppe De Giacomo, and Maurizio Lenzerini. Models of information integration: Turning local-as-view into global-as-view. In FMII, 2001.
• 5: Andrea Calì , Domenico Lembo , Riccardo Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.260-271, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773179]
• 6: Alin Deutsch, Bertram Ludäscher and Alan Nash. Rewriting Queries Using Views with Access Patterns under Integrity Constraints. In ICDT, 2005.
• 7: Alin Deutsch , Lucian Popa , Val Tannen, Physical Data Independence, Constraints, and Optimization with Universal Plans, Proceedings of the 25th International Conference on Very Large Data Bases, p.459-470, September 07-10, 1999
• 8: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 9: Alin Deutsch , Val Tannen, XML Queries and constraints, containment and reformulation, Theoretical Computer Science, v.336 n.1, p.57-87, 25 May 2005 [doi>10.1016/j.tcs.2004.10.032]
• 10: Oliver Duschka, Michael Genesereth, and Alon Levy. Recursive query plans for data integration. Journal of Logic Programming, 43(1):49--73, 2000.
• 11: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 12: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.90-101, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773163]
• 13: Marc Friedman , Alon Levy , Todd Millstein, Navigational plans for data integration, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.67-73, July 18-22, 1999, Orlando, Florida, United States
• 14: Jack Minker, Introduction to logic-based artificial intelligence, Logic-based artificial intelligence, Kluwer Academic Publishers, Norwell, MA, 2000
• 15: The Piazza Peer Data Management System, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.787-798, July 2004 [doi>10.1109/TKDE.2004.1318562]
• 16: Christoph Koch, Query Rewriting with Symmetric Constraints, Proceedings of the Second International Symposium on Foundations of Information and Knowledge Systems, p.130-147, February 20-23, 2002
• 17: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 18: Renée J. Miller , Mauricio A. Hernández , Laura M. Haas , Lingling Yan , C. T. Howard Ho , Ronald Fagin , Lucian Popa, The Clio project: managing heterogeneity, ACM SIGMOD Record, v.30 n.1, p.78-83, March 2001 [doi>10.1145/373626.373713]
• 19: Todd Millstein , Alon Halevy , Marc Friedman, Query containment for data integration systems, Journal of Computer and System Sciences, v.66 n.1, p.20-39, 01 February 2003 [doi>10.1016/S0022-0000(02)00028-4]
• 20: Jeffrey D. Ullman, Information Integration Using Logical Views, Proceedings of the 6th International Conference on Database Theory, p.19-40, January 08-10, 1997
• 21: Cong Yu , Lucian Popa, Constraint-based XML query rewriting for data integration, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007611]