Rewriting of visibly pushdown languages for xml data integration

ABSTRACT

In this paper, we focus on XML data integration by studying rewritings of XML target schemas in terms of source schemas. Rewriting is very important in data integration systems where the system is asked to find and assemble XML documents from the data sources and produce documents which satisfy a target schema.

As schema representation, we consider Visibly Pushdown Automata (VPAs) which accept Visibly Pushdown Languages (VPLs). The latter have been shown to coincide with the family of (word-encoded) regular tree languages which are the basis of formalisms for specifying XML schemas. Furthermore, practical semi-formal XML schema specifications (defined by simple pattern conditions on XML) compile into VPAs which are exponentially more concise than other representations based on tree automata.

Notably, VPLs enjoy a "well-behavedness" which facilitates us in addressing rewriting problems for XML data integration. Based on VPAs, we positively solve these problems, and present detailed complexity analyses.

REFERENCES

• 1: Rajeev Alur, Marrying words and trees, 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.1265564]
• 2: Rajeev Alur , P. Madhusudan, Visibly pushdown languages, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007390]
• 3: Calvanese, D., De Giacomo, G., Lenzerini, M., and Vardi, Y. M. Rewriting of Regular Expressions and Regular Path Queries. J. Comput. Syst. Sci. 64(3): 2002, pp. 443--465.
• 4: Clark, J., and M. Murata, M. RELAX NG Specification. OASIS, December 2001.
• 5: Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Löding, C.,Tison, S., and Tommasi, M. Tree Automata Techniques and Applications. Available on: http://www.grappa.univ-lille3.fr/tata, October 12, 2007.
• 6: Jeffrey Friedl, Mastering Regular Expressions, O'Reilly Media, Inc., 2006
• 7: Gösta Grahne , Alex Thomo, An Optimization Technique for Answering Regular Path Queries, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.215-225, May 18-19, 2000
• 8: Gösta Grahne , Alex Thomo, Algebraic Rewritings for Optimizing Regular Path Queries, Proceedings of the 8th International Conference on Database Theory, p.301-315, January 04-06, 2001
• 9: Gösta Grahne , Alex Thomo, New Rewritings and Optimizations for Regular Path Queries, Proceedings of the 9th International Conference on Database Theory, p.242-258, January 08-10, 2003
• 10: Hashiguchi, K. Representation Theorems on Regular Languages. J. Comput. Syst. Sci. 27(1): 1983, pp. 101--115.
• 11: Viraj Kumar , P. Madhusudan , Mahesh Viswanathan, Visibly pushdown automata for streaming XML, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242714]
• 12: Wim Martens , Frank Neven , Thomas Schwentick , Geert Jan Bex, Expressiveness and complexity of XML Schema, ACM Transactions on Database Systems (TODS), v.31 n.3, p.770-813, September 2006 [doi>10.1145/1166074.1166076]
• 13: Makoto Murata , Dongwon Lee , Murali Mani , Kohsuke Kawaguchi, Taxonomy of XML schema languages using formal language theory, ACM Transactions on Internet Technology (TOIT), v.5 n.4, p.660-704, November 2005 [doi>10.1145/1111627.1111631]
• 14: Thomas Schwentick, Automata for XML---A survey, Journal of Computer and System Sciences, v.73 n.3, p.289-315, May, 2007 [doi>10.1016/j.jcss.2006.10.003]
• 15: Luc Segoufin , Victor Vianu, Validating streaming XML documents, 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.543622]
• 16: Sperberg-McQueen, C., M., and Thomson, H. XML Schema 1.0. http://www.w3.org/XML/Schema, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

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

General Terms:
Algorithms, Languages, Theory

Keywords:
data integration, visibly pushdown languages, xml