Extraction and Implication of Path Constraints?

Abstract. We consider semistructured data as rooted edge-labeled directed graphs, and path inclusion constraints on these graphs. In this paper, we show that we can extract from a nite datum D a nite set Cf (D) of word inclusions, which implies exactly every word inclusion satised by D. Then, we give a new decision algorithm for the implication problem of a constraint p q by a set of constraints pi ui where p, q, and the pi's are regular path expressions and the ui's are non empty paths, improving in this particular case, the more general algorithms of S. Abiteboul and V. Vianu, and Alechina et al. Moreover, in the case of a set of word equalities ui vi, we give a more ecient decision algorithm for the implication of a word equality u v, improving the more general algorithm of P. Buneman et al., and we prove that, in this case, the implication problem for non deterministic models or for (complete) deterministic models are equivalent.