5 papers · 1 filter
Revisiting Semiring Provenance for Datalog
Camille Bourgaux, Pierre Bourhis, Liat Peterfreund +1
Data provenance consists in bookkeeping meta information during query evaluation, in order to enrich query results with their trust level, likelihood, evaluation cost, and more. Th…
Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries
Pierre Bourhis, Daniel Deutch, Yuval Moskovitch
The algebraic approach for provenance tracking, originating in the semiring model of Green et. al, has proven useful as an abstract way of handling metadata. Commutative Semirings…
Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
Antoine Amarilli, Pierre Bourhis, Stefan Mengel +1
We give an algorithm to enumerate the results on trees of monadic second-order (MSO) queries represented by nondeterministic tree automata. After linear time preprocessing (in the…
Evaluating Datalog via Tree Automata and Cycluits
Antoine Amarilli, Pierre Bourhis, Mikaël Monet +1
We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We show that clique-frontier-gu…
Constant-Delay Enumeration for Nondeterministic Document Spanners
Antoine Amarilli, Pierre Bourhis, Stefan Mengel +1
We consider the information extraction framework known as document spanners, and study the problem of efficiently computing the results of the extraction from an input document, wh…