Running tree automata on probabilistic XML

ABSTRACT

Tree automata (specifically, bottom-up and unranked) form a powerful tool for querying and maintaining validity of XML documents. XML with uncertain data can be modeled as a probability space of labeled trees, and that space is often represented by a tree with distributional nodes. This paper investigates the problem of evaluating a tree automaton over such a representation, where the goal is to compute the probability that the automaton accepts a random possible world. This problem is generally intractable, but for the case where the tree automaton is deterministic (and its transitions are defined by deterministic string automata), an efficient algorithm is presented. The paper discusses the applications of this result, including the ability to sample and to evaluate queries (e.g., in monadic second-order logic) while requiring a-priori conformance to a schema (e.g., DTD). XML schemas also include attribute constraints, and the complexity of key, foreign-key and inclusion constraints are studied in the context of probabilistic XML. Finally, the paper discusses the generalization of the results to an extended data model, where distributional nodes can repeatedly sample the same subtree, thereby adding another exponent to the size of the probability space.

REFERENCES

• 1: S. Abiteboul and P. Senellart. Querying and updating probabilistic information in XML. In EDBT, pages 1059--1068, 2006.
• 2: L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP completeness, recursive functions, and universal machines. Bull. A.M.S., 21:1--46, 1989.
• 3: A. Brüggemann-Klein, M. Murata, and D. Wood. Regular tree and regular hedge languages over unranked alphabets: Version 1, april 3, 2001. Technical Report HKUST-TCSC-2001-0, The Hongkong University of Science and Technology, 2001.
• 4: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 5: Sara Cohen , Benny Kimelfeld , Yehoshua Sagiv, Incorporating constraints in probabilistic XML, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376933]
• 6: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.864-875, August 31-September 03, 2004, Toronto, Canada
• 7: Nilesh Dalvi , Dan Suciu, The dichotomy of conjunctive queries on probabilistic structures, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265571]
• 8: J. Doner. Tree acceptors and some of their applications. J. Comput. Syst. Sci., 4(5):406--451, 1970.
• 9: Rod G. Downey , Michael R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing, v.24 n.4, p.873-921, Aug. 1995 [doi>10.1137/S0097539792228228]
• 10: R.G. Downey and M.R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999.
• 11: Wenfei Fan , Leonid Libkin, On XML integrity constraints in the presence of DTDs, Journal of the ACM (JACM), v.49 n.3, p.368-406, May 2002 [doi>10.1145/567112.567117]
• 12: Markus Frick , Martin Grohe, The Complexity of First-Order and Monadic Second-Order Logic Revisited, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.215-224, July 22-25, 2002
• 13: Erich Grädel , Yuri Gurevich , Colin Hirsch, The complexity of query reliability, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-234, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.295124]
• 14: John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 15: Edward Hung , Lise Getoor , V. S. Subrahmanian, Probabilistic Interval XML, Proceedings of the 9th International Conference on Database Theory, p.361-377, January 08-10, 2003
• 16: E. Hung, L. Getoor, and V.S. Subrahmanian. PXML: A probabilistic semistructured data model and algebra. In ICDE, pages 467--478, 2003.
• 17: Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , Richard E. Stearns, The Complexity of Planar Counting Problems, SIAM Journal on Computing, v.27 n.4, p.1142-1167, Aug. 1998 [doi>10.1137/S0097539793304601]
• 18: Benny Kimelfeld , Yuri Kosharovsky , Yehoshua Sagiv, Query efficiency in probabilistic XML models, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376687]
• 19: Benny Kimelfeld , Yehoshua Sagiv, Matching twigs in probabilistic XML, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 20: Christoph Koch, Approximating predicates and expressive queries on probabilistic databases, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376932]
• 21: Te Li , Qihong Shao , Yi Chen, PEPX: a query-friendly probabilistic XML database, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183761]
• 22: Wim Martens , Joachim Niehren, On the minimization of XML Schemas and tree automata for unranked trees, Journal of Computer and System Sciences, v.73 n.4, p.550-583, June, 2007 [doi>10.1016/j.jcss.2006.10.021]
• 23: A.R. Meyer. Weak monadic second-order theory of successor is not elementary recursive. Logic Colloquim, 453:132--154, 1975.
• 24: Frank Neven , Thomas Schwentick, Expressive and efficient pattern languages for tree-structured data (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.145-156, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335217]
• 25: Frank Neven , Thomas Schwentick, Query automata over finite trees, Theoretical Computer Science, v.275 n.1-2, p.633-674, March 28 2002 [doi>10.1016/S0304-3975(01)00301-2]
• 26: Andrew Nierman , H. V. Jagadish, ProTDB: probabilistic data in XML, Proceedings of the 28th international conference on Very Large Data Bases, p.646-657, August 20-23, 2002, Hong Kong, China
• 27: Yannis Papakonstantinou , Victor Vianu, Incremental Validation of XML Documents, Proceedings of the 9th International Conference on Database Theory, p.47-63, January 08-10, 2003
• 28: J.S. Provan and M.O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing, 12(4):777--788, 1983.
• 29: Pierre Senellart , Serge Abiteboul, On the complexity of managing probabilistic XML data, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265570]
• 30: J.W. Thatcher and J.B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory, 2(1):57--81, 1968.
• 31: Seinosuke Toda , Mitsunori Ogiwara, Counting classes are at least as hard as the polynomial-time hierarchy, SIAM Journal on Computing, v.21 n.2, p.316-328, April 1992 [doi>10.1137/0221023]
• 32: Maurice van Keulen , Ander de Keijzer , Wouter Alink, A Probabilistic XML Approach to Data Integration, Proceedings of the 21st International Conference on Data Engineering, p.459-470, April 05-08, 2005 [doi>10.1109/ICDE.2005.11]
• 33: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Algorithms, Theory

Keywords:
probabilistic trees, probabilistic xml, tree automata, xml constraints, xml query evaluation, xml schema