Distributed XML design

ABSTRACT

A distributed XML document is an XML document that spans several machines or Web repositories. We assume that a distribution design of the document tree is given, providing an XML tree some of whose leaves are "docking points", to which XML subtrees can be attached. These subtrees may be provided and controlled by peers at remote locations, or may correspond to the result of function calls, e.g., Web services. If a global type τ, e.g. a DTD, is specified for a distributed document T, it would be most desirable to be able to break this type into a collection of local types, called a local typing, such that the document satisfies τ if and only if each peer (or function) satisfies its local type. In this paper we lay out the fundamentals of a theory of local typing and provide formal definitions of three main variants of locality: local typing, maximal local typing, and perfect typing, the latter being the most desirable. We study the following relevant decision problems: (i) given a typing for a design, determine whether it is local, maximal local, or perfect; (ii) given a design, establish whether a (maximal) local, or perfect typing does exist. For some of these problems we provide tight complexity bounds (polynomial space), while for the others we show exponential upper bounds. A main contribution is a polynomial-space algorithm for computing a perfect typing in this context, if it exists.

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: Serge Abiteboul , Angela Bonifati , Grégory Cobéna , Ioana Manolescu , Tova Milo, Dynamic XML documents with distribution and replication, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872821]
• 3: S. Abiteboul, I. Manolescu, and E. Taropa. A framework for distributed XML data management. In Y. E. Ioannidis, M. H. Scholl, J. W. Schmidt, F. Matthes, M. Hatzopoulos, K. Bohm, A. Kemper, T. Grust, and C. Bohm, editors, EDBT, volume 3896 of Lecture Notes in Computer Science, pages 1049--1058. Springer, 2006.
• 4: Serge Abiteboul , Tova Milo , Omar Benjelloun, Regular rewriting of active XML and unambiguity, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065204]
• 5: J.-M. Bremer and M. Gertz. On distributing XML repositories. In V. Christophides and J. Freire, editors, WebDB, pages 73--78, 2003.
• 6: Stefano Ceri , Piero Fraternali , Aldo Bongio, Web Modeling Language (WebML): a modeling language for designing Web sites, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.137-157, June 2000
• 7: S. Ceri, B. Pernici, and G. Wiederhold. An overview of research in the design of distributed databases. IEEE Database Eng. Bull., 7(4):46--51, 1984.
• 8: J. Clark and M. Murata. RELAX NG Specification. OASIS, 1 edition, December 2001.
• 9: G. Ghelli, D. Colazzo, and C. Sartiani. Efficient inclusion for a class of XML types with interleaving and counting. In M. Arenas and M. I. Schwartzbach, editors, DBPL, volume 4797 of Lecture Notes in Computer Science, pages 231--245. Springer, 2007.
• 10: P. Grosso and D. Veillard. XML fragment interchange. Internet Publication, Feb 2001. W3C Candidate Recommendation 12 February 2001.
• 11: Christian Hagenah , Anca Muscholl, Computing epsilon-Free NFA from Regular Expressions in O(n log²(n)) Time, Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, p.277-285, August 24-28, 1998
• 12: Luis O. Hernández , Mahmoud Pegah, WebDAV: what it is, what it does, why you need it, Proceedings of the 31st annual ACM SIGUCCS conference on User services, p.249-254, September 21-24, 2003, San Antonio, TX, USA [doi>10.1145/947469.947535]
• 13: M. Holzer and M. Kutrib. State complexity of basic operations on nondeterministic finite automata. In J.-M. Champarnaud and D. Maurel, editors, CIAA, volume 2608 of Lecture Notes in Computer Science, pages 148--157. Springer, 2002.
• 14: Juraj Hromkovic , Sebastian Seibert , Thomas Wilke, Translating Regular Expressions into Small epsilon-Free Nondeterministic Finite Automata, Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, p.55-66, February 27-March 01, 1997
• 15: H. V. Jagadish , Laks V. S. Lakshmanan , Tova Milo , Divesh Srivastava , Dimitra Vista, Querying network directories, ACM SIGMOD Record, v.28 n.2, p.133-144, June 1999
• 16: W. Martens, F. Neven, and T. Schwentick. Complexity of decision problems for simple regular expressions. In J. Fiala, V. Koubek, and J. Kratochvil, editors, MFCS, volume 3153 of Lecture Notes in Computer Science, pages 889--900. Springer, 2004.
• 17: M. Tamer Özsu , Patrick Valduriez, Distributed Database Systems: Where Are We Now?, Computer, v.24 n.8, p.68-78, August 1991 [doi>10.1109/2.84879]
• 18: Yannis Papakonstantinou , Victor Vianu, DTD inference for views of XML data, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.35-46, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335173]
• 19: W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4(2):177--192, 1970.
• 20: Helmut Seidl, Deciding equivalence of finite tree automata, SIAM Journal on Computing, v.19 n.3, p.424-437, June 1990 [doi>10.1137/0219027]
• 21: L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
• 22: Dan Suciu, Typechecking for Semistructured Data, Revised Papers from the 8th International Workshop on Database Programming Languages, p.1-20, September 08-10, 2001
• 23: H. Thompson, D. Beech, M. Maloney, and N. Mendelsohn. XML schema part 1: Structures second edition. Internet Publication, Oct 2004. Recommendation, World Wide Web Consortium, Boston, Tokyo, Sophia Antipolis.
• 24: M. Veanes. On computational complexity of basic decision problems of finite tree automata. Technical Report 133, Uppsala Programming Methodology and Artificial Intelligence Laboratory, Sweden, Jan. 1997.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models; Schema and subschema

General Terms:
Design, Languages, Theory

Keywords:
distributed XML, dtd, xml typing, xml-schema