Search Results

Documents authored by Tison, Sophie

Document
DOI: 10.4230/LIPIcs.ICDT.2024.17
Containment of Regular Path Queries Under Path Constraints

Authors: Sylvain Salvati and Sophie Tison

Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)

Abstract
Data integrity is ensured by expressing constraints it should satisfy. One can also view constraints as data properties and take advantage of them for several tasks such as reasoning about data or accelerating query processing. In the context of graph databases, simple constraints can be expressed by means of path constraints while simple queries are modeled as regular path queries (RPQs). In this paper, we investigate the containment of RPQs under path constraints. We focus on word constraints that can be viewed as tuple-generating dependencies (TGDs) of the form ∀x_1,x_2, ∃y⁻, a_1(x_1,y_1) ∧ ... ∧ a_i(y_{i-1},y_i) ∧ ... ∧ a_n(y_{n-1},x_2) ⟶ ∃z⁻, b_1(x_1,z_1) ∧ ... ∧ b_i(z_{i-1},z_i) ∧ ... ∧ b_m(z_{m-1},x_2). Such a constraint means that whenever two nodes in a graph are connected by a path labeled a_1 … a_n, there is also a path labeled b_1 … b_m that connects them. Rewrite systems offer an abstract view of these TGDs: the rewrite rule a_1 … a_n → b_1 … b_m represents the previous constraint. A set of constraints 𝒞 is then represented by a rewrite system R and, when dealing with possibly infinite databases, a path query p is contained in a path query q under the constraints 𝒞 iff p rewrites to q with R. Contrary to what has been claimed in the literature we show that, when restricting to finite databases only, there are cases where a path query p is contained in a path query q under the constraints 𝒞 while p does not rewrite to q with R. More generally, we study the finite controllability of the containment of RPQs under word constraints, that is when this containment problem on unrestricted databases does coincide with the finite case. We give an exact characterisation of the cases where this equivalence holds. We then deduce the undecidability of the containment problem in the finite case even when RPQs are restricted to word queries. We prove several properties related to finite controllability, and in particular that it is undecidable. We also exhibit some classes of word constraints that ensure the finite controllability and the decidability of the containment problem.
Cite as

Sylvain Salvati and Sophie Tison. Containment of Regular Path Queries Under Path Constraints. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{salvati_et_al:LIPIcs.ICDT.2024.17,
  author =	{Salvati, Sylvain and Tison, Sophie},
  title =	{{Containment of Regular Path Queries Under Path Constraints}},
  booktitle =	{27th International Conference on Database Theory (ICDT 2024)},
  pages =	{17:1--17:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-312-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{290},
  editor =	{Cormode, Graham and Shekelyan, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.17},
  URN =		{urn:nbn:de:0030-drops-197994},
  doi =		{10.4230/LIPIcs.ICDT.2024.17},
  annote =	{Keywords: Graph databases, rational path queries, query containment, TGDs, word constraints, rewrite systems, finite controllability, decision problems}
}
Document
DOI: 10.4230/LIPIcs.RTA.2011.1
Tree Automata, (Dis-)Equality Constraints and Term Rewriting: What's New?

Authors: Sophie Tison

Published in: LIPIcs, Volume 10, 22nd International Conference on Rewriting Techniques and Applications (RTA'11) (2011)

Abstract
Connections between Tree Automata and Term Rewriting are now well known. Whereas tree automata can be viewed as a subclass of ground rewrite systems, tree automata are successfully used as decision tools in rewriting theory. Furthermore, applications, including rewriting theory, have influenced the definition of new classes of tree automata. In this talk, we will first present a short and not exhaustive reminder of some fruitful applications of tree automata in rewriting theory. Then, we will focus on extensions of tree automata, specially tree automata with local or/and global (dis-)equality constraints: we will emphasize new results, compare different extensions, and sketch some applications.
Cite as

Sophie Tison. Tree Automata, (Dis-)Equality Constraints and Term Rewriting: What's New?. In 22nd International Conference on Rewriting Techniques and Applications (RTA'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 10, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{tison:LIPIcs.RTA.2011.1,
  author =	{Tison, Sophie},
  title =	{{Tree Automata, (Dis-)Equality Constraints and Term Rewriting: What's New?}},
  booktitle =	{22nd International Conference on Rewriting Techniques and Applications (RTA'11)},
  pages =	{1--2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-30-9},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{10},
  editor =	{Schmidt-Schauss, Manfred},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2011.1},
  URN =		{urn:nbn:de:0030-drops-31404},
  doi =		{10.4230/LIPIcs.RTA.2011.1},
  annote =	{Keywords: Tree Automata, Constraints, Term Rewriting}
}
Document
DOI: 10.4230/DagSemProc.05061.5
N-ary Queries by Tree Automata

Authors: Joachim Niehren, Laurent Planque, Jean-Marc Talbot, and Sophie Tison

Published in: Dagstuhl Seminar Proceedings, Volume 5061, Foundations of Semistructured Data (2005)

Abstract
Information extraction from semi-structured documents requires to find n-ary queries in trees that define appropriate sets of n-tuples of nodes. We propose new representation formalisms for n-ary queries by tree automata that we prove to capture MSO. We then investigate n-ary queries by unambiguous tree automata which are relevant for query induction in multi-slot information extraction. We show that this representation formalism captures the class of n-ary queries that are finite unions of Cartesian closed queries, a property we prove decidable.
Cite as

Joachim Niehren, Laurent Planque, Jean-Marc Talbot, and Sophie Tison. N-ary Queries by Tree Automata. In Foundations of Semistructured Data. Dagstuhl Seminar Proceedings, Volume 5061, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{niehren_et_al:DagSemProc.05061.5,
  author =	{Niehren, Joachim and Planque, Laurent and Talbot, Jean-Marc and Tison, Sophie},
  title =	{{N-ary Queries by Tree Automata}},
  booktitle =	{Foundations of Semistructured Data},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5061},
  editor =	{Frank Neven and Thomas Schwentick and Dan Suciu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05061.5},
  URN =		{urn:nbn:de:0030-drops-2263},
  doi =		{10.4230/DagSemProc.05061.5},
  annote =	{Keywords: Information extraction, semistructured documents, node selecting queries in trees}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact