Author name cluster

Victor Marsault

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

KR Conference 2023 Conference Paper

Run-Based Semantics for RPQs

Claire David
Nadime Francis
Victor Marsault

RPQs (regular path queries) are an important building block of most query languages for graph databases. They are generally evaluated under homomorphism semantics; in particular only the endpoints of the matched walks are returned. However, practical applications often need the full matched walks to compute aggregate values. In those cases, homomorphism semantics are not suitable since the number of matched walks can be infinite. Hence, graph-database engines adapt the semantics of RPQs, often neglecting theoretical red flags. For instance, the popular query language Cypher uses trail semantics, which ensures the result to be finite at the cost of making computational problems intractable. We propose a new kind of semantics for RPQs, including in particular simple-run and binding-trail semantics, as a candidate to reconcile theoretical considerations with practical aspirations. Both ensure the output to be finite in a way that is compatible with homomorphism semantics: projection on endpoints coincides with homomorphism semantics. Hence, testing the emptiness of result is tractable, and known methods readily apply. Moreover, simple-run and binding-trail semantics support bag semantics, and enumeration of the bag of results is tractable.

PDF Details DOI

Highlights Conference 2022 Conference Abstract

Simple-Run Semantics for RPQs

Victor Marsault

In database theory, RPQs (regular path queries) are the building block of most query languages for querying graph databases. RPQs are generally evaluated under homomorphism semantics; in particular only the endpoints of the matched walks are returned. On the contrary, due to user pressure, most real graph-database engines actually return the full matched walks. Under homomorphism semantics, there might be an infinite number of such walks. Hence each real query language had to adapt the semantics of RPQs in order to meet this popular demand, often neglecting theoretical implications. For instance, the most popular query language, Cypher, uses trail semantics: only walks with no repeated edges are returned. In that case, the result set is indeed finite, but the simplest computational problems are untractable. We propose new semantics for RPQs, called simple-run semantics, as a candidate to reconcile theoretical considerations with practical aspirations. Just as trail semantics, simple-run semantics aims at keeping the output finite by filtering out redundant results. Trail semantics filter based on redundancy in the computed walk: repeated edges are forbidden. Simple-run semantics filter based on redundancy in the run: a node can be reused only if the query computation did progress compared to the previous times the node was visited. Joint work with Claire David and Nadime Francis.

Details

TCS Journal 2017 Journal Article

The signature of rational languages

Victor Marsault
Jacques Sakarovitch

We present here the notion of signature of trees and of languages, and its relationships with the theory of numeration systems. The signature of an ordered infinite tree (of bounded degree) is an infinite (bounded) sequence of integers, the sequence of the degrees of the nodes taken in the visit order of the canonical breadth-first traversal of the tree. A prefix-closed language defines such a tree augmented with labels on arcs, hence is associated with a signature. This way of ‘traversing’ a language is related to the notion of abstract numeration system, due to Lecomte and Rigo. After having set in detail the framework of signature, we study and characterise the signatures of rational languages. Using a known construction from numeration system theory, we show that these signatures form a special subclass of morphic words. We then use this framework to give an alternative definition to morphic numeration systems (also called Dumont–Thomas numeration systems). We finally highlight that the classes of morphic numeration systems and of (prefix-closed) rational abstract numeration systems are essentially the same.

Details DOI