| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
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 give a new decision algorithm for the implication problem of a constraint $p \preceq q$ by a set of constraints $p_i \preceq u_i$ where $p$, $q$, and the $p_i$'s are regular path expressions and the $u_i$'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 $u_i \equiv v_i$, we give a more efficient decision algorithm for the implication of a word equality $u \equiv 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.
Cited literature [17 references]
https://hal.inria.fr/inria-00536715
Contributor : Denis Debarbieux <>
Submitted on : Tuesday, November 16, 2010 - 6:01:22 PM
Last modification on : Thursday, July 25, 2019 - 8:50:03 AM
Document(s) archivé(s) le : Thursday, February 17, 2011 - 3:08:39 AM
Contributor : Denis Debarbieux <>
Submitted on : Tuesday, November 16, 2010 - 6:01:22 PM
Last modification on : Thursday, July 25, 2019 - 8:50:03 AM
Document(s) archivé(s) le : Thursday, February 17, 2011 - 3:08:39 AM
File
Extraction-And-Implication-Of-...
Files produced by the author(s)