{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T00:14:54Z","timestamp":1761264894056,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,11,1]],"date-time":"2008-11-01T00:00:00Z","timestamp":1225497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["GR\/S63205\/01GR\/T27433\/01EP\/E029213\/1"],"award-info":[{"award-number":["GR\/S63205\/01GR\/T27433\/01EP\/E029213\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2008,11]]},"abstract":"<jats:p>\n            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\n            <jats:italic>publishing transducers<\/jats:italic>\n            , 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.\n          <\/jats:p>","DOI":"10.1145\/1412331.1412337","type":"journal-article","created":{"date-parts":[[2008,12,10]],"date-time":"2008-12-10T15:32:31Z","timestamp":1228923151000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Expressiveness and complexity of XML publishing transducers"],"prefix":"10.1145","volume":"33","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"University of Edinburgh and Bell Laboratories, Scotland, UK"}]},{"given":"Floris","family":"Geerts","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Scotland, UK"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Diepenbeek, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2008,12,12]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/772062.772065"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065171"},{"volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Benedikt M.","key":"e_1_2_2_4_1","unstructured":"Benedikt , M. , Chan , C. , Fan , W. , Rastogi , R. , Zheng , S. , and Zhou , A . 2002. DTD-directed publishing with attribute translation grammars . In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Francisco, CA, 838--849. Benedikt, M., Chan, C., Fan, W., Rastogi, R., Zheng, S., and Zhou, A. 2002. DTD-directed publishing with attribute translation grammars. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Francisco, CA, 838--849."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_47"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007625"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"B\u00f6rger E. Gr\u00e4del E. and Gurevich Y. 1997. The Classical Decision Problem. Springer.  B\u00f6rger E. Gr\u00e4del E. and Gurevich Y. 1997. The Classical Decision Problem. Springer.","DOI":"10.1007\/978-3-642-59207-2"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90268-2"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265542"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/582410.582413"},{"key":"e_1_2_2_13_1","unstructured":"Flum J. and Ebbinghaus H. 1999. Finite Model Theory 2nd ed. Springer.  Flum J. and Ebbinghaus H. 1999. Finite Model Theory 2nd ed. Springer."},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"G\u00e9cseg F. and Steinby M. 1996. Tree languages. In Handbook of Formal Languages. Vol. 3. Springer.  G\u00e9cseg F. and Steinby M. 1996. Tree languages. In Handbook of Formal Languages. Vol. 3. Springer.","DOI":"10.1007\/978-3-642-59126-6_1"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/647841.736267"},{"key":"e_1_2_2_16_1","unstructured":"IBM. DB2 XML Extender. http:\/\/www-3.ibm.com\/software\/data\/db2\/extended\/xmlext\/.  IBM. DB2 XML Extender. http:\/\/www-3.ibm.com\/software\/data\/db2\/extended\/xmlext\/."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42273"},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of the 1st International XML Database Symposium (XSym). Lecture Notes in Computer Science","volume":"626","author":"Krishnamurthy R.","unstructured":"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. 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."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00736-3"},{"volume-title":"Elements of Finite Model Theory","author":"Libkin L.","key":"e_1_2_2_20_1","unstructured":"Libkin , L. 2004. Elements of Finite Model Theory . Springer . Libkin, L. 2004. Elements of Finite Model Theory. Springer."},{"volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Lud\u00e4scher B.","key":"e_1_2_2_21_1","unstructured":"Lud\u00e4scher , B. , Mukhopadhyay , P. , and Papakonstantinou , Y . 2002. A transducer-based XML query processor . In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Francisco, CA, 227--238. Lud\u00e4scher, B., Mukhopadhyay, P., and Papakonstantinou, Y. 2002. A transducer-based XML query processor. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Francisco, CA, 227--238."},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the 7th International Workshop on Database Programming Languages (DBPL). Lecture Notes in Computer Science","volume":"1949","author":"Maneth S.","unstructured":"Maneth , S. and Neven , F . 1999. Structured document transformations based on XSL . In Proceedings of the 7th International Workshop on Database Programming Languages (DBPL). Lecture Notes in Computer Science , vol. 1949 , Springer, Berlin, Heidelberg, New York, 80--98. Maneth, S. and Neven, F. 1999. Structured document transformations based on XSL. In Proceedings of the 7th International Workshop on Database Programming Languages (DBPL). Lecture Notes in Computer Science, vol. 1949, Springer, Berlin, Heidelberg, New York, 80--98."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166076"},{"key":"e_1_2_2_24_1","unstructured":"Melton J. and Simon A. 1993. Understanding the New SQL: A Complete Guide. Morgan Kaufman.   Melton J. and Simon A. 1993. Understanding the New SQL: A Complete Guide. Morgan Kaufman."},{"key":"e_1_2_2_25_1","volume-title":"XML support in microsoft SQL server","author":"Microsoft","year":"2005","unstructured":"Microsoft . 2005. XML support in microsoft SQL server 2005 . msdn.microsoft.com\/library\/en-us\/dnsql90\/html\/sql2k5xml.asp\/. Microsoft. 2005. XML support in microsoft SQL server 2005. msdn.microsoft.com\/library\/en-us\/dnsql90\/html\/sql2k5xml.asp\/."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00030-2"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543624"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00301-2"},{"key":"e_1_2_2_29_1","unstructured":"Oracle. Oracle Database 10g Release 2 XML DB Whitepaper. http:\/\/www.oracle.com\/technology\/tech\/xml\/xmldb\/index.html.  Oracle. Oracle Database 10g Release 2 XML DB Whitepaper. http:\/\/www.oracle.com\/technology\/tech\/xml\/xmldb\/index.html."},{"volume-title":"Computational Complexity","author":"Papadimitriou C. H.","key":"e_1_2_2_30_1","unstructured":"Papadimitriou , C. H. 1994. Computational Complexity . Addison Wesley . Papadimitriou, C. H. 1994. Computational Complexity. Addison Wesley."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335173"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/767141.767144"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1455"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412331.1412337","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412331.1412337","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:51Z","timestamp":1750286931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412331.1412337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["10.1145\/1412331.1412337"],"URL":"https:\/\/doi.org\/10.1145\/1412331.1412337","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2008,11]]},"assertion":[{"value":"2007-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}