Path Constraints in the Presence of Types
Peter Buneman, Wenfei Fan, Scott Weinstein · ScholarlyCommons (University of Pennsylvania) · 1997
Path constraints have been studied in [3, 8, 9] for semi-structured data. In this paper, we investigate path constraints for structured data. We show that there is interaction between path constraints and type constraints. In other words, results on path constraint implication in semistructured databases may no longer hold in the presence of types. We also investigate the class of word constraints for databases of two practical object-oriented data models. In particular, we present an abstraction of the databases in these models in terms of first-order logic, and establish the decidability of word constraint implication in these models. 1 Introduction Path constraints and their associated implication problems have been studied in [3, 8, 9] for semistructured data. In these papers, semistructured data is represented as a rooted edge-labeled directed graph, as in other semistructured data models (e.g., OEM [18, 2] and UnQL [7]. See [1] for a survey). Specifically, [8, 9] model semistruc...