Retrieving XML data from heterogeneous sources through vague querying

ABSTRACT

We propose a framework for querying heterogeneous XML data sources. The framework ensures high autonomy to participating sources as it does not rely on a global schema or on semantic mappings between schemas. The basic intuition is that of extending traditional approaches for approximate query evaluation, by providing techniques for combining partial answers coming from different sources, possibly on the basis of limited knowledge about the local schemas (i.e., key constraints). We define a query language and its associated semantics, that allows us to collect as much information as possible from several heterogeneous XML sources. We provide algorithms for query evaluation and characterize the complexity of the query language. Finally, we validate the approach in a medical application scenario.

REFERENCES

• 1: Serge Abiteboul , Omar Benjelloun , Tova Milo, The Active XML project: an overview, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1019-1040, August 2008 [doi>10.1007/s00778-007-0049-y]
• 2: Sihem Amer-Yahia , SungRan Cho , Divesh Srivastava, Tree Pattern Relaxation, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.496-513, March 25-27, 2002
• 3: Sihem Amer-Yahia , Nick Koudas , Amélie Marian , Divesh Srivastava , David Toman, Structure and content scoring for XML, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 4: Sihem Amer-Yahia , Laks V. S. Lakshmanan , Shashank Pandit, FleXPath: flexible structure and full-text querying for XML, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007581]
• 5: Chaitan Baru , Amarnath Gupta , Bertram Ludäscher , Richard Marciano , Yannis Papakonstantinou , Pavel Velikhov , Vincent Chu, XML-based information mediation with MIX, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.597-599, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 6: BitTorrent. 2007. BitTorrent home page. http://www.bittorrent.com.
• 7: Angela Bonifati , Elaine Qing Chang , Aks V. S. Lakshmanan , Terence Ho , Rachel Pottinger, HePToX: marrying XML and heterogeneity in your P2P databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 8: Camillo, S. D., Heuser, C. A., and dos Santos Mello, R. 2003. Querying heterogeneous XML sources through a conceptual schema. In Proceedings of the ER. 186--199.
• 9: Cindy X. Chen , George A. Mihaila , Sriram Padmanabhan , Isabelle M. Rouvellou, Query translation scheme for heterogeneous XML data sources, Proceedings of the 7th annual ACM international workshop on Web information and data management, November 04-04, 2005, Bremen, Germany [doi>10.1145/1097047.1097055]
• 10: Hong-Hai Do , Erhard Rahm, COMA: a system for flexible combination of schema matching approaches, Proceedings of the 28th international conference on Very Large Data Bases, p.610-621, August 20-23, 2002, Hong Kong, China
• 11: AnHai Doan , Pedro Domingos , Alon Y. Halevy, Reconciling schemas of disparate data sources: a machine-learning approach, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.509-520, May 21-24, 2001, Santa Barbara, California, United States
• 12: Fazzinga, B., Flesca, S., and Pugliese, A. 2007. Vague queries on peer-to-peer XML databases. In Proceedings of the International Conference on Database and Expert Systems Applications (DEXA'07). 287--297.
• 13: Norbert Fuhr , Kai Groβjohann, XIRQL: An XML query language based on information retrieval concepts, ACM Transactions on Information Systems (TOIS), v.22 n.2, p.313-356, April 2004 [doi>10.1145/984321.984326]
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: Sudipto Guha , H. V. Jagadish , Nick Koudas , Divesh Srivastava , Ting Yu, Integrating XML data sources using approximate joins, ACM Transactions on Database Systems (TODS), v.31 n.1, p.161-207, March 2006 [doi>10.1145/1132863.1132868]
• 16: 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]
• 17: Luís Leitão , Pável Calado , Melanie Weis, Structure-based inference of xml similarity for fuzzy duplicate detection, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321483]
• 18: Jayant Madhavan , Philip A. Bernstein , Erhard Rahm, Generic Schema Matching with Cupid, Proceedings of the 27th International Conference on Very Large Data Bases, p.49-58, September 11-14, 2001
• 19: Mandreoli, F., Martoglia, R., and Tiberio, P. 2004. Approximate query answering for a heterogeneous XML document base. In Proceedings of the International Conference on Web Information Systems Engineering (WISE'04), 337--351.
• 20: Ioana Manolescu , Daniela Florescu , Donald Kossmann, Answering XML Queries on Heterogeneous Data Sources, Proceedings of the 27th International Conference on Very Large Data Bases, p.241-250, September 11-14, 2001
• 21: Gerome Miklau , Dan Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM (JACM), v.51 n.1, p.2-45, January 2004 [doi>10.1145/962446.962448]
• 22: Milano, D., Scannapieco, M., and Catarci, T. 2006. Structure aware XML object identification. In Proceedings of the International VLDB Workshop on Clean Databases (CleanDB).
• 23: Napster. 2007. Napster homepage. http://www.napster.com.
• 24: Nejdl, W., Wolf, B., Qu, C., Decker, S., Sintek, M., Naeve, A., Nilsson, M., Palmer, M., and Risch, T. 2001. Edutella: A p2p networking infrastructure based on rdf. https://edutella.dev.java.net/reports/edutella-whitepaper.pdf.
• 25: Evaggelia Pitoura , Serge Abiteboul , Dieter Pfoser , George Samaras , Michalis Vazirgiannis, DBGlobe: a service-oriented P2P system for global computing, ACM SIGMOD Record, v.32 n.3, September 2003 [doi>10.1145/945721.945737]
• 26: Neoklis Polyzotis , Minos Garofalakis, XSKETCH synopses for XML data graphs, ACM Transactions on Database Systems (TODS), v.31 n.3, p.1014-1063, September 2006 [doi>10.1145/1166074.1166082]
• 27: Puhlmann, S., Weis, M., and Naumann, F. 2006. XML duplicate detection using sorted neighborhoods. In Proceedings of the International Conference on Extending Database Technology (EDBT'06), 773--791.
• 28: Reyner, S. W. 1977. An analysis of a good algorithm for the subtree problem. SIAM J. Comput. 6, 4, 730--732.
• 29: Rodríguez-Gianolli, P. and Mylopoulos, J. 2001. A semantic approach to XML-based data integration. In Proceedings of the ER, 117--132.
• 30: Torsten Schlieder, Schema-Driven Evaluation of Approximate Tree-Pattern Queries, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.514-532, March 25-27, 2002
• 31: Igor Tatarinov , Alon Halevy, Efficient query reformulation in peer data management systems, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007629]
• 32: Anja Theobald , Gerhard Weikum, Adding Relevance to XML, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.105-124, May 18-19, 2000
• 33: Vdovjak, R. and Houben, G.-J. 2001. Rdf-Based architecture for semantic integration of heterogeneous information sources. In Proceedings of the Workshop on Information Integration on the Web, 51--57.
• 34: W3C. 2007. World wide web consortium. http://www.w3.org.
• 35: WordNet. 2007. WordNet homepage. http://wordnet.princeton.edu.
• 36: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Languages, Management

Keywords:
XML, heterogeneous databases, querying