Path constraints in semistructured databases

Peter Buneman, Wenfei Fan, Scott Weinstein

Research output: Contribution to journalArticlepeer-review

Abstract

We investigate a class of path constraints that is of interest in connection with both semistructured and structured data. In standard database systems, constraints are typically expressed as part of the schema, but in semistructured data there is no explicit schema and path constraints provide a natural alternative. As with structured data, path constraints on semistructured data express integrity constraints associated with the semantics of data and are 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 and finite implication problems for several fragments of the path constraint language and demonstrate that these fragments suffice to express important semantic information such as extent constraints, inverse relationships, and local database constraints commonly found in object-oriented databases.
Original languageEnglish
Pages (from-to)146-193
Number of pages48
JournalJournal of Computer and System Sciences
Volume61
Issue number2
DOIs
Publication statusPublished - 2000

Fingerprint

Dive into the research topics of 'Path constraints in semistructured databases'. Together they form a unique fingerprint.

Cite this