Path Constraints on Semistructured and Structured Data

Peter Buneman, Wenfei Fan, Scott Weinstein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationPODS '98 Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems
PublisherACM Press
Number of pages10
ISBN (Print)0-89791-996-3
Publication statusPublished - 1998


Dive into the research topics of 'Path Constraints on Semistructured and Structured Data'. Together they form a unique fingerprint.

Cite this