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. 1 Introduction The representation of data as a rooted edge-labeled graph has gained enormous popularity recently in semistructured data. It has proven to be useful for a wide range of applications such as integrating heterogeneous data sources (Lorel [3], MSL [22]), querying biological data (UnQL [9]) and querying the Web (W3QS [17], WebSQL [..