Dynamic XML documents with distribution and replication

ABSTRACT

The advent of XML as a universal exchange format, and of Web services as a basis for distributed computing, has fostered the apparition of a new class of documents: dynamic XML documents. These are XML documents where some data is given explicitly while other parts are given only intensionally by means of embedded calls to web services that can be called to generate the required information. By the sole presence of Web services, dynamic documents already include inherently some form of distributed computation. A higher level of distribution that also allows (fragments of) dynamic documents to be distributed and/or replicated over several sites is highly desirable in today's Web architecture, and in fact is also relevant for regular (non dynamic) documents.The goal of this paper is to study new issues raised by the distribution and replication of dynamic XML data. Our study has originated in the context of the Active XML system [1, 3, 22] but the results are applicable to many other systems supporting dynamic XML data. Starting from a data model and a query language, we describe a complete framework for distributed and replicated dynamic XML documents. We provide a comprehensive cost model for query evaluation and show how it applies to user queries and service calls. Finally, we describe an algorithm that, for a given peer, chooses data and services that the peer should replicate to improve the efficiency of maintaining and querying its dynamic data.

REFERENCES

• 1: S. Abiteboul, O. Benjelloun, I. Manolescu, T. Milo, and R. Weber. Active XML: Peer-to-Peer Data and Web Services Integration (demo). Proc. of VLDB, 2002.
• 2: Ashraf Aboulnaga , Alaa R. Alameldeen , Jeffrey F. Naughton, Estimating the Selectivity of XML Path Expressions for Internet Scale Applications, Proceedings of the 27th International Conference on Very Large Data Bases, p.591-600, September 11-14, 2001
• 3: Active xml. http://www-rocq.inria.fr/verso/Gemo/Projects/axml/.
• 4: The Akamai webpage. http://www.akamai.com/.
• 5: Peter M. G. Apers, Data allocation in distributed database systems, ACM Transactions on Database Systems (TODS), v.13 n.3, p.263-304, Sept. 1988 [doi>10.1145/44498.45063]
• 6: Stefano Ceri , Giuseppe Pelagatti, Distributed databases principles and systems, McGraw-Hill, Inc., New York, NY, 1984
• 7: L. Chen and E. A. Rudensteiner. ACE-XQ: A CachE-aware XQuery Answering System. In Proc. of WebDB, 2002.
• 8: Microsoft .Net. http://www.microsoft.com/net/.
• 9: Michael J. Franklin , Björn Thór Jónsson , Donald Kossmann, Performance tradeoffs for client-server query processing, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.149-160, June 04-06, 1996, Montreal, Quebec, Canada
• 10: Juliana Freire , Jayant R. Haritsa , Maya Ramanath , Prasan Roy , Jérôme Siméon, StatiX: making XML count, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564713]
• 11: Gnutella homepage. http://www.gnutella.com/.
• 12: G. Gottlob, C. Koch, and R. Pichler. Efficient algorithms for processing XPath queries. In Proc. of VLDB, 2002.
• 13: V. Hristidis and M. Petropoulos. Semantic caching of XML databases. In Proc. of WebDB, 2002.
• 14: J. Mc Hugh, S. Abiteboul, R. Goldman, D. Quass, and J. Widom. Lore: A Database Management System for Semistructured Data. Technical report, Stanford University Database Group, Feb 1997.
• 15: Sun's JavaServer Pages. http://java.sun.com/products/jsp/.
• 16: Panos Kalnis , Wee Siong Ng , Beng Chin Ooi , Dimitris Papadias , Kian-Lee Tan, An adaptive peer-to-peer network for distributed caching of OLAP results, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564695]
• 17: Olga Kapitskaia , Raymond T. Ng , Divesh Srivastava, Evolution and Revolutions in LDAP Directory Caches, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.202-216, March 27-31, 2000
• 18: Anne-Marie Kermarrec , Antony Rowstron , Marc Shapiro , Peter Druschel, The IceCube approach to the reconciliation of divergent replicas, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.210-218, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384020]
• 19: Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000 [doi>10.1145/371578.371598]
• 20: Macromedia Dreamweaver. http://www.macromedia.com/.
• 21: 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
• 22: Tova Milo , Serge Abiteboul , Bernd Amann , Omar Benjelloun , Fred Dang Ngoc, Exchanging intensional XML data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872793]
• 23: Wee Siong Ng, Beng Chin Ooi, Kian Lee Tan, and AoYing Zhou. PeerDB: A P2P-based system for distributed data sharing. In Proc. of ICDE, 2003.
• 24: Dan Olteanu , Holger Meuss , Tim Furche , François Bry, XPath: Looking Forward, Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers, p.109-127, March 24-28, 2002
• 25: V. Papadimos and D. Maier. Mutant query plans. In OOPSLA, 2001.
• 26: Yannis Papakonstantinou , Serge Abiteboul , Hector Garcia-Molina, Object Fusion in Mediator Systems, Proceedings of the 22th International Conference on Very Large Data Bases, p.413-424, September 03-06, 1996
• 27: PHP. http://www.php.net/.
• 28: J. Shanmugasundaram, E. Shekita, and R. Barr. Efficiently publishing XML views of relational databases. In Proc. of VLDB, 2000.
• 29: M. Tamer Özsu , Patrick Valduriez, Principles of distributed database systems (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 30: Igor Tatarinov , Zachary G. Ives , Alon Y. Halevy , Daniel S. Weld, Updating XML, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.413-424, May 21-24, 2001, Santa Barbara, California, United States
• 31: The World Wide Web Consortium (W3C). http://www.w3.org/.
• 32: Beverly Yang , Hector Garcia-Molina, Comparing Hybrid Peer-to-Peer Systems, Proceedings of the 27th International Conference on Very Large Data Bases, p.561-570, September 11-14, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing; Distributed databases

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.1 Document and Text Editing
          Subjects: Document management
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Algorithms, Design, Experimentation, Performance