Expressiveness and complexity of xml publishing transducers

ABSTRACT

A number of languages have been developed for specifying XML publishing, i.e., 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 paper proposes a notion of publishing transducers. Unlike automata for querying XML data, a publishing transducer generates a new XML tree rather than performing a query on an existing tree. 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, i.e., excluded from the output tree. We first show how existing XML publishing languages can be characterized by such transducers. We then study the members ip, emptiness and equivalence problems for various classes of transducers and existing publishing languages. We establish lower and upper bounds, all matching except one, 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.

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: M. Benedikt and C. Koch. Interpreting tree-to-tree queries. In ICALP, pages 552--564, 2006.
• 5: M. Benedikt, C. Chan, W. Fan, R. Rastogi, S. Zheng and A. Zhou. DTD-directed publishing with attribute translation grammars. In VLDB, 2002.
• 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: E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Springer, 1997.
• 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: 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]
• 12: J. Flum and H. Ebbinghaus. Finite Model Theory. Springer, 2nd edition, 1999.
• 13: F. Gécseg and M. Steinby. Tree languages. In Handbook of Formal Languages, volume 3. Springer, 1996.
• 14: E. Grädel. On Transitive Closure Logic. In CSL, 1992.
• 15: IBM. DB2 XML Extender. http://www-3.ibm.com/software/data/db2/extended/xmlext/.
• 16: R. Krishnamurthy, R. Kaushik, and J. F. Naughton. XMLSQL query translation literature: The state of the art and open problems. In Xsym, 2003.
• 17: Leonid Libkin, Elements Of Finite Model Theory (Texts in Theoretical Computer Science. An Eatcs Series), SpringerVerlag, 2004
• 18: B. Ludäscher, P. Mukhopadhyay, and Y. Papakonstantinou. A transducer-based XML query processor. In VLDB, 2002.
• 19: Microsoft. XML support in microsoft SQL server 2005, 2005 msdn.microsoft.com/library/en-us/dnsql90/html/sql2k5xml.asp/.
• 20: 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]
• 21: 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]
• 22: 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]
• 23: Oracle. Oracle Database 10g Release 2 XML DB Whitepaper. http://www.oracle.com/technology/tech/xml/ xmldb/index.html.
• 24: C. H. Papadimitriou. Computational Complexity. AW, 1994.
• 25: Y. Papakonstantinou and V. Vianu. Type inference for views of semistructured data. In PODS, 2000.
• 26: 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
• 27: M. Spielmann. Abstract State Machines: Verification Problems and Complexity. PhD thesis, RWTH Aachen, 2000.
• 28: 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]
• 29: 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.3 Languages

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

General Terms:
Design, Languages, Theory

Keywords:
XML publishing, complexity, expressiveness