Informatics Report Series


Report   

EDI-INF-RR-1130


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Expressiveness and Complexity of XML Publishing Transducers
Authors: Wenfei Fan ; Floris Geerts ; Frank Neven
Date: 2007
Publication Title:Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
Publisher:ACM Press
Publication Type:Conference Paper Publication Status:Published
Page Nos:83-92
DOI:10.1145/1265530.1265542 ISBN/ISSN:978-1-59593-685-1
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 membership, 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.
Links To Paper
1st Link
Bibtex format
@InProceedings{EDI-INF-RR-1130,
author = { Wenfei Fan and Floris Geerts and Frank Neven },
title = {Expressiveness and Complexity of XML Publishing Transducers},
book title = {Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems},
publisher = {ACM Press},
year = 2007,
pages = {83-92},
doi = {10.1145/1265530.1265542},
url = {http://homepages.inf.ed.ac.uk/fgeerts/pdf/pods07.pdf},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh