Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/9155
Full metadata record
DC FieldValueLanguage
dc.contributor.authorFan, Wenfei-
dc.contributor.authorGEERTS, Floris-
dc.contributor.authorNEVEN, Frank-
dc.date.accessioned2009-01-15T14:47:20Z-
dc.date.available2009-01-15T14:47:20Z-
dc.date.issued2008-
dc.identifier.citationACM TRANSACTIONS ON DATABASE SYSTEMS, 33(4). p. 1-49-
dc.identifier.issn0362-5915-
dc.identifier.urihttp://hdl.handle.net/1942/9155-
dc.description.abstractA number of languages have been developed for specifying XML publishing, that is, transforma- tions 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 expres- sive 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 trans- ducers. 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.-
dc.language.isoen-
dc.publisherACM-
dc.titleExpressiveness and complexity of XML publishing transducers-
dc.typeJournal Contribution-
dc.identifier.epage49-
dc.identifier.issue4-
dc.identifier.spage1-
dc.identifier.volume33-
local.bibliographicCitation.jcatA1-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.bibliographicCitation.oldjcatA1-
dc.identifier.doi10.1145/1412331.1412337-
dc.identifier.isi000263490800006-
dc.identifier.urlhttp://doi.acm.org/10.1145/1412331.1412337-
item.fulltextNo Fulltext-
item.accessRightsClosed Access-
item.contributorFan, Wenfei-
item.contributorNEVEN, Frank-
item.contributorGEERTS, Floris-
item.fullcitationFan, Wenfei; GEERTS, Floris & NEVEN, Frank (2008) Expressiveness and complexity of XML publishing transducers. In: ACM TRANSACTIONS ON DATABASE SYSTEMS, 33(4). p. 1-49.-
item.validationecoom 2010-
crisitem.journal.issn0362-5915-
crisitem.journal.eissn1557-4644-
Appears in Collections:Research publications
Show simple item record

SCOPUSTM   
Citations

3
checked on Sep 2, 2020

Page view(s)

50
checked on Jun 29, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.