Path Constraints in Semistructured and Structured Databases
Peter Buneman, Wenfei Fan, Scott Weinstein
Full Paper (PDF)

Abstract
We present a class of path constraints of interest in connection with both structured and semistructured databases, and investigate their associated implication problems. These path constraints are capable of expressing natural integrity constraints that are not only a fundamental part of the semantics of the data, but are also important in query optimization. We show that in semistructured databases, despite the simple syntax of the constraints, their associated implication problem is r.e. complete and finite implication problem is co-r.e. complete. However, we establish the decidability of the implication problems for several fragments of the path constraint language, and demonstrate that these fragments suffice to express important semantic information such as inverse relationships and local database constraints commonly found in object-oriented databases. We also show that in the presence of types, the analysis of path constraint implication becomes more delicate. We demonstrate some simple decidability results for two practical object-oriented data models.

References

References, where available, link to the DBLP on the World Wide Web.

[1]
Serge Abiteboul: Querying Semi-Structured Data. ICDT 1997: 1-18
[2]
Serge Abiteboul, Dallan Quass, Jason McHugh, Jennifer Widom, Janet L. Wiener: The Lorel Query Language for Semistructured Data. Int. J. on Digital Libraries 1(1): 68-88(1997)
[3]
Serge Abiteboul, Victor Vianu: Regular Path Queries with Constraints. PODS 1997: 122-133
[4]
François Bancilhon, Claude Delobel, Paris C. Kanellakis (Eds.): Building an Object-Oriented Database System, The Story of O2. Morgan Kaufmann 1992, ISBN 1-55860-169-4
Contents
[5]
...
[6]
...
[7]
Peter Buneman, Susan B. Davidson, Gerd G. Hillebrand, Dan Suciu: A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996: 505-516
[8]
...
[9]
...
[10]
...
[11]
R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.2). Morgan Kaufmann 1996
[12]
...
[13]
Charles Lamb, Gordon Landis, Jack A. Orenstein, Danel Weinreb: The ObjectStore System. CACM 34(10): 50-63(1991)
[14]
...
[15]
...
BIBTEX

@inproceedings{DBLP:conf/pods/BunemanFW98,
author = {Peter Buneman and
Wenfei Fan and
Scott Weinstein},
title = {Path Constraints in Semistructured and Structured Databases},
booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-966-3},
pages = {129-138},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}


DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).