Some Undecidable Implication Problems for Path Constraints
Peter Buneman, Wenfei Fan, Scott Weinstein · ScholarlyCommons (University of Pennsylvania) · 1997
We present a class of path constraints of interest in connection with both structured and semistructured databases, and investigate their associated implication problems. These path constraints are capable of expressing natural integrity constraints that are not only a fundamental part of the semantics of the data, but are also important in query optimization. We show that, despite the simple syntax of the constraints, the implication problem for the constraints is r.e. complete and the finite implication problem for the constraints is co-r.e. complete. Indeed, we establish the existence of a conservative reduction of the set of all first-order sentences to the path constraint language. 1 Introduction Path inclusion constraints have been studied in [5] in the context of semistructured data. Consider the following object-oriented schema: class studentf Name: string; Taking: set(course); g class coursef CName: string; Enrolled: set(student); g Students: set(student); Courses: set(cou...