Please use this identifier to cite or link to this item:
Title: Typechecking XML views of relational databases
Authors: Alon, Noga
Milo, Tova
NEVEN, Frank 
Suciu, Dan
Vianu, Victor
Issue Date: 2003
Publisher: ACM Press; New York, NY, USA
Source: ACM Transactions on Computational Logic (TOCL), 4(3). p. 315-354
Abstract: Motivated by the need to export relational databases as XML data in the context of the Web, we investigate the typechecking problem for transformations of relational data into tree data (XML). The problem consists of statically verifying that the output of every transformation belongs to a given output tree language (specified for XML by a DTD), for input databases satisfying given integrity constraints. The typechecking problem is parameterized by the class of formulas defining the transformation, the class of output tree languages, and the class of integrity constraints. While undecidable in its most general formulation, the typechecking problem has many special cases of practical interest that turn out to be decidable. The main contribution of this article is to trace a fairly tight boundary of decidability for typechecking in this framework. In the decidable cases we examine the complexity, and show lower and upper bounds. We also exhibit a practically appealing restriction for which typechecking is in PTIME.
Document URI:
Link to publication:
ISSN: 1529-3785
e-ISSN: 1557-945X
Category: A2
Type: Journal Contribution
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
18 + 28 lics2001.pdf198.94 kBAdobe PDFView/Open
Show full item record

Page view(s)

checked on May 19, 2022


checked on May 19, 2022

Google ScholarTM


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