We investigate a class of path consiraints 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 consiraints 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 synlax of the constraints. their associated implication problem is r.e. complete and finite implication problem is core complete. However. we establish the decidability of the implication and finite implication problems for several Yagments 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 databasess
展开▼
