The Decidability of Some Restricted Implication Problems for Path Constraints

In [10], we introduced a path constraint language and established the undecidability of its associated implication problems. In this paper, we identify several fragments of the language, and establish the decidability of the implication and finite implication problems for each of these fragments in the context of semistructured databases. In addition, we demonstrate that these fragments suffice to express important semantic information such as extent constraint, inverse relationships and local database constraints commonly found in object-oriented databases. We also show that these fragments are useful for, among other things, query optimization.