Penn DB Group's logo
Path Constraints
Arrow; just used for page layout. People
Arrow, used for page layout Publications
Arrow, used for page layout Research
Arrow, used for page layout Classes
Arrow, used for page layout Seminar
Arrow, used for page layout Resources
Search this website

Path Constraints

Executive Summary

The aim of this project is to develop a formal mechanism for expressing, reasoning about and making use of integrity constraints that commonly arise in practice. Examples of these constraints include referential integrity, inverse and local database constraints. These constraints are not only a fundamental part of the semantics of the data, but are also important in query optimization. They have proven useful in a variety of database contexts, ranging from semistructured data as found for instance in the Web, to structured data as found in object-oriented databases. In particular, several proposals for specifying and querying XML documents also advocate the need for these constraints.

To this end, a path constraint language is introduced here to capture these integrity constraints. Methodology for using these constraints in, among others, query optimization, is studied. To take advantage of these constraints, their associated implication and finite implication problems are investigated in the context of semistructured data (i.e., data unconstrained by any type system or schema) as well as structured data (i.e., data constrained by a schema).

There is a natural analogy between this work and inclusion dependency theory established for the relational model. The theory of inclusion dependencies constitutes an important part of relational database theory. In the same way, the class of path constraints investigated here is important to a variety of data models developed to meet the demands of a wide range of applications. At one end of the spectrum, these models include sophisticated ones with richer constructs than the relational model, such as object-oriented models proposed to deal with, for example, computer-aided design and office information systems. At the other end, among these models are semistructured data models, which have recently emerged in response to the need of data integration, data exchange and querying semistructured data such as XML documents.

Project Members

Peter Buneman   Wenfei Fan   


Levine Hall
3330 Walnut Street
Philadelphia, PA 19104

Last update: 08/02/11     Comments