Digital Symposium Collection 2000

Interaction between Path and Type Constraints Peter Buneman, Wenfei Fan, and Scott Weinstein   View Paper (PDF)   Return to Semantics Abstract XML [7], which is emerging as an important standard for data exchange on the World-Wide Web, highlights the importance of semistructured data. Although the XML standard itself does not require any schema or type system, a number of proposals [6, 17, 191 have been developed that roughly correspond to data definition languages. These allow one to constrain the structure of XML data by imposing a schema on it. These and other proposals also advocate the need for integrity constraints, another form of constraints that should, for example, be capable of expressing inclusion constraints and inverse relationships. The latter have recently been studied as path constraints in the context of semistructured data [4, 91. It is likely that future XML proposals will involve both forms of constraints, and it is therefore appropriate to understand the interaction between them. This paper investigates that interaction. In particular it studies constraint implication problems, which are important both in understanding the semantics of type/constraint systems and in query optimization. A number of results on path constraint implication are established in the presence and absence of type systems. These results demonstrate that adding a type system may in some cases simplify reasoning about path constraints and in other cases make it harder. For example, it is shown that there is a path constraint implication problem that is decidable in PTIME in the untyped context, but that becomes undecidable when a type system is added. On the other hand, there is an implication problem that is undecidable in the untyped context, but becomes not only decidable in cubic time but also finitely axiomatizable when a type system is imposed. References Note: References link to DBLP on the Web. [1] Serge Abiteboul : Querying Semi-Structured Data. ICDT 1997 : 1-18 [2] Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0 Contents [3] Serge Abiteboul , Paris C. Kanellakis : Object Identity as a Query Language Primitive. SIGMOD Conference 1989 : 159-173 [4] Serge Abiteboul , Victor Vianu : Regular Path Queries with Constraints. PODS 1997 : 122-133 [5] ... [6] ... [7] ... [8] Peter Buneman : Semistructured Data. PODS 1997 : 117-121 [9] Peter Buneman , Wenfei Fan , Scott Weinstein : Path Constraints in Semistructured and Structured Databases. PODS 1998 : 129-138 [10] ... [11] R. G. G. Cattell : The Object Database Standard: ODMG-93 (Release 1.2). Morgan Kaufmann 1996 [12] Upen S. Chakravarthy , John Grant , Jack Minker : Foundations of Semantic Query Optimization for Deductive Databases. Foundations of Deductive Databases and Logic Programming. 1988 : 243-273 [13] Sophie Cluet , Claude Delobel : A General Framework for the Optimization of Object-Oriented Queries. SIGMOD Conference 1992 : 383-392 [14] ... [15] ... [16] ... [17] ... [18] ... [19] ... [20] ... [21] ... [22] Lucian Popa , Val Tannen : An Equational Chase for Path-Conjunctive Queries, Constraints, and Views. ICDT 1999 : 39-57 [23] ... BIBTEX @inproceedings{DBLP:conf/pods/BunemanFW99,   author    = {Peter Buneman and                 Wenfei Fan and                 Scott Weinstein},    title     = {Interaction between Path and Type Constraints},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {56-67},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM