Technical Report MS-CIS-98-33,
University of Pennsylvania, 1998.
We study path constraints for deterministic graph model, a variation of semistructured data model in which data is represented as a rooted edge-labeled directed graph with deterministic edge relations. The path constraint languages considered include the class of word constraints, the language Pc investigated in PODS98, and an extension of Pc defined in terms of regular expressions. Complexity results on the implication and finite implication problems for these constraint languages are established.
See here for the paper.
Back to DB Group Homepage
sharker@saul.cis.upenn.edu