Expressiveness and complexity of XML publishing transducers

ABSTRACT

A number of languages have been developed for specifying XML publishing, that is, transformations of relational data into XML trees. These languages generally describe the behaviors of a middleware controller that builds an output tree iteratively, issuing queries to a relational source and expanding the tree with the query results at each step. To study the complexity and expressive power of XML publishing languages, this article proposes a notion of publishing transducers, which generate XML trees from relational data. We study a variety of publishing transducers based on what relational queries a transducer can issue, what temporary stores a transducer can use during tree generation, and whether or not some tree nodes are allowed to be virtual, that is, excluded from the output tree. We first show how existing XML publishing languages can be characterized by such transducers, and thus provide a synergy between theory and practice. We then study the membership, emptiness, and equivalence problems for various classes of transducers. We establish lower and upper bounds, all matching, ranging from PTIME to undecidable. Finally, we investigate the expressive power of these transducers and existing languages. We show that when treated as relational query languages, different classes of transducers capture either complexity classes (e.g., PSPACE) or fragments of datalog (e.g., linear datalog). For tree generation, we establish connections between publishing transducers and logical transductions, among other things.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Noga Alon , Tova Milo , Frank Neven , Dan Suciu , Victor Vianu, Typechecking XML views of relational databases, ACM Transactions on Computational Logic (TOCL), v.4 n.3, p.315-354, July 2003 [doi>10.1145/772062.772065]
• 3: Marcelo Arenas , Leonid Libkin, XML data exchange: consistency and query answering, 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.1065171]
• 4: Michael Benedikt , Chee Yong Chan , Wenfei Fan , Rajeev Rastogi , Shihui Zheng , Aoying Zhou, DTD-directed publishing with attribute translation grammars, Proceedings of the 28th international conference on Very Large Data Bases, p.838-849, August 20-23, 2002, Hong Kong, China
• 5: Benedikt, M. and Koch, C. 2006. Interpreting tree-to-tree queries. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 4052, Springer, Berlin, Heidelberg, New York, 552--564.
• 6: Philip Bohannon , Byron Choi , Wenfei Fan, Incremental evaluation of schema-directed XML publishing, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007625]
• 7: Börger, E., Grädel, E., and Gurevich, Y. 1997. The Classical Decision Problem. Springer.
• 8: Bruno Courcelle, Monadic second-order definable graph transductions: a survey, Theoretical Computer Science, v.126 n.1, p.53-75, April 11, 1994 [doi>10.1016/0304-3975(94)90268-2]
• 9: Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001 [doi>10.1145/502807.502810]
• 10: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, ACM Transactions on Database Systems (TODS), v.30 n.1, p.174-210, March 2005 [doi>10.1145/1061318.1061323]
• 11: Wenfei Fan , Floris Geerts , Frank Neven, Expressiveness and complexity of xml publishing transducers, 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.1265542]
• 12: Mary Fernández , Yana Kadiyska , Dan Suciu , Atsuyuki Morishima , Wang-Chiew Tan, SilkRoute: A framework for publishing relational data in XML, ACM Transactions on Database Systems (TODS), v.27 n.4, p.438-493, December 2002 [doi>10.1145/582410.582413]
• 13: Flum, J. and Ebbinghaus, H. 1999. Finite Model Theory, 2nd ed. Springer.
• 14: Gécseg, F. and Steinby, M. 1996. Tree languages. In Handbook of Formal Languages. Vol. 3. Springer.
• 15: Erich Grädel, On Transitive Closure Logic, Proceedings of the 5th Workshop on Computer Science Logic, p.149-163, October 07-11, 1991
• 16: IBM. DB2 XML Extender. http://www-3.ibm.com/software/data/db2/extended/xmlext/.
• 17: Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
• 18: Krishnamurthy, R., Kaushik, R., and Naughton, J. 2003. XML-SQL query translation literature: the state of the art and open problems. In Proceedings of the 1st International XML Database Symposium (XSym). Lecture Notes in Computer Science, vol. 626, Springer, Berlin, Heidelberg, New York, 1--18.
• 19: Leonid Libkin, Expressive power of SQL, Theoretical Computer Science, v.296 n.3, p.379-404, 14 March 2003 [doi>10.1016/S0304-3975(02)00736-3]
• 20: Leonid Libkin, Elements Of Finite Model Theory (Texts in Theoretical Computer Science. An Eatcs Series), SpringerVerlag, 2004
• 21: Bertram Ludäscher , Pratik Mukhopadhyay , Yannis Papakonstantinou, A transducer-based XML query processor, Proceedings of the 28th international conference on Very Large Data Bases, p.227-238, August 20-23, 2002, Hong Kong, China
• 22: Sebastian Maneth , Frank Neven, Structured Document Transformations Based on XSL, Revised Papers from the 7th International Workshop on Database Programming Languages: Research Issues in Structured and Semistructured Database Programming, p.80-98, September 01-03, 1999
• 23: 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]
• 24: Jim Melton , Alan R. Simon, Understanding the new SQL: a complete guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 25: Microsoft. 2005. XML support in microsoft SQL server 2005. msdn.microsoft.com/library/en-us/dnsql90/html/sql2k5xml.asp/.
• 26: Tova Milo , Dan Suciu , Victor Vianu, Typechecking for XML transformers, Journal of Computer and System Sciences, v.66 n.1, p.66-97, 01 February 2003 [doi>10.1016/S0022-0000(02)00030-2]
• 27: Frank Neven, On the power of walking for querying tree-structured data, 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.543624]
• 28: 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]
• 29: Oracle. Oracle Database 10g Release 2 XML DB Whitepaper. http://www.oracle.com/technology/tech/xml/xmldb/index.html.
• 30: Papadimitriou, C. H. 1994. Computational Complexity. Addison Wesley.
• 31: 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]
• 32: Jayavel Shanmugasundaram , Eugene Shekita , Rimon Barr , Michael Carey , Bruce Lindsay , Hamid Pirahesh , Berthold Reinwald, Efficiently publishing relational data as XML documents, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.133-154, September 2001
• 33: Spielmann, M. 2000. Abstract state machines: verification problems and complexity. Ph.D. thesis, RWTH Aachen.
• 34: Ron van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Journal of Computer and System Sciences, v.54 n.1, p.113-135, Feb. 1997 [doi>10.1006/jcss.1997.1455]
• 35: 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.5 Heterogeneous Databases

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.m Miscellaneous

General Terms:
Design, Languages, Theory

Keywords:
XML publishing, complexity, data exchange, expressiveness, transducer