ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Path Constraints in Semistructured and Structured Databases.

Peter Buneman, Wenfei Fan, Scott Weinstein: Path Constraints in Semistructured and Structured Databases. PODS 1998: 129-138
@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-996-3},
  pages     = {129-138},
  ee        = {http://doi.acm.org/10.1145/275487.275502, db/conf/pods/BunemanFW98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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.

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington. ACM Press 1998, ISBN 0-89791-996-3
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1259 KB]

References

[1]
Serge Abiteboul: Querying Semi-Structured Data. ICDT 1997: 1-18 BibTeX
[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) BibTeX
[3]
Serge Abiteboul, Victor Vianu: Regular Path Queries with Constraints. PODS 1997: 122-133 BibTeX
[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 BibTeX
[5]
...
[6]
...
[7]
Peter Buneman, Susan B. Davidson, Gerd G. Hillebrand, Dan Suciu: A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conference 1996: 505-516 BibTeX
[8]
...
[9]
...
[10]
...
[11]
R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.2). Morgan Kaufmann 1996
BibTeX
[12]
...
[13]
Charles Lamb, Gordon Landis, Jack A. Orenstein, Daniel Weinreb: The ObjectStore Database System. Commun. ACM 34(10): 50-63(1991) BibTeX
[14]
...
[15]
...

Referenced by

  1. Vitaliy L. Khizder, David Toman, Grant E. Weddell: On Decidability and Complexity of Description Logics with Uniqueness Constraints. ICDT 2001: 54-67
  2. Frank Neven, Thomas Schwentick: Expressive and Efficient Pattern Languages for Tree-Structured Data. PODS 2000: 145-156
  3. Wenfei Fan, Jérôme Siméon: Integrity Constraints for XML. PODS 2000: 23-34
  4. Sihem Amer-Yahia, H. V. Jagadish, Laks V. S. Lakshmanan, Divesh Srivastava: On Bounding-Schemas for LDAP Directories. EDBT 2000: 287-301
  5. Peter T. Wood: Optimising Web Queries Using Document Type Definitions. Workshop on Web Information and Data Management 1999: 28-32
  6. Yaron Kanza, Werner Nutt, Yehoshua Sagiv: Queries with Incomplete Answers over Semistructured Data. PODS 1999: 227-236
  7. Carmem S. Hara, Susan B. Davidson: Reasoning about Nested Functional Dependencies. PODS 1999: 91-100
  8. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi: Rewriting of Regular Expressions and Regular Path Queries. PODS 1999: 194-204
  9. Peter Buneman, Wenfei Fan, Scott Weinstein: Interaction between Path and Type Constraints. PODS 1999: 56-67
  10. Catriel Beeri, Tova Milo: Schemas for Integration and Translation of Structured and Semi-structured Data. ICDT 1999: 296-313
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:19 2009