Edinburgh Research Explorer

Path constraints in semistructured databases

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions

Open

Documents

Original languageEnglish
Pages (from-to)146-193
Number of pages48
JournalJournal of Computer and System Sciences
Volume61
Issue number2
DOIs
Publication statusPublished - 2000

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.

Download statistics

No data available

ID: 10624575