research
∙
04/12/2023
Skyline Operators for Document Spanners
When extracting a relation of spans (intervals) from a text document, a ...
share
research
∙
02/07/2023
Degree-3 Planar Graphs as Topological Minors of Wall Graphs in Polynomial Time
In this note, we give a proof of the fact that we can efficiently find d...
research
∙
12/21/2022
Tighter bounds for query answering with Guarded TGDs
We consider the complexity of the open-world query answering problem, wh...
research
∙
09/29/2022
Enumerating Regular Languages in Constant Delay
We study the task, for a given language L, of enumerating the (generally...
research
∙
09/22/2022
Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries
We study the uniform query reliability problem, which asks, for a fixed ...
research
∙
05/09/2022
Worst-case Analysis for Interactive Evaluation of Boolean Provenance
In recent work, we have introduced a framework for fine-grained consent ...
research
∙
05/02/2022
Weighted Counting of Matchings in Unbounded-Treewidth Graph Families
We consider a weighted counting problem on matchings, denoted PrMatching...
research
∙
02/17/2022
Query Answering with Transitive and Linear-Ordered Data
We consider entailment problems involving powerful constraint languages ...
research
∙
01/03/2022
Efficient enumeration algorithms for annotated grammars
We introduce annotated grammars, an extension of context-free grammars w...
research
∙
02/15/2021
Dynamic Membership for Regular Languages
We study the dynamic membership problem for regular languages: fix a lan...
research
∙
03/16/2020
Equivalent Rewritings on Path Views with Binding Patterns
A view with a binding pattern is a parameterized query on a database. Su...
research
∙
03/05/2020
Finite Open-World Query Answering with Number Restrictions
Open-world query answering is the problem of deciding, given a set of fa...
research
∙
10/04/2019
A Dichotomy for Homomorphism-Closed Queries on Probabilistic Graphs
We study the problem of probabilistic query evaluation (PQE) over probab...
research
∙
08/19/2019
Model Counting for Conjunctive Queries Without Self-Joins
We study the problem of model counting for Boolean Conjunctive Queries (...
research
∙
06/01/2019
Smoothing Structured Decomposable Circuits
We study the task of smoothing a circuit, i.e., ensuring that all childr...
research
∙
12/22/2018
Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
We give an algorithm to enumerate the results on trees of monadic second...
research
∙
11/07/2018
Connecting Knowledge Compilation Classes and Width Parameters
The field of knowledge compilation establishes the tractability of many ...
research
∙
08/14/2018
Evaluating Datalog via Tree Automata and Cycluits
We investigate parameterizations of both database instances and queries ...
research
∙
07/24/2018
Constant-Delay Enumeration for Nondeterministic Document Spanners
We consider the information extraction approach known as document spanne...
research
∙
01/19/2018
Computing Possible and Certain Answers over Order-Incomplete Data
This paper studies the complexity of query evaluation for databases whos...
research
∙
09/18/2017
Connecting Width and Structure in Knowledge Compilation (Extended Version)
Several query evaluation tasks can be done via knowledge compilation: th...
research
∙
09/18/2017
Connecting Width and Structure in Knowledge Compilation
Several query evaluation tasks can be done via knowledge compilation: th...
research
∙
09/18/2017
Enumeration on Trees under Relabelings
We study how to evaluate MSO queries with free variables on trees, withi...
research
∙
07/22/2017
Possible and Certain Answers for Queries over Order-Incomplete Data
To combine and query ordered data from multiple sources, one needs to ha...
research
∙
07/13/2017
A Dichotomy on Constrained Topological Sorting
We introduce the constrained topological sorting problem (CTS-problem): ...
research
∙
06/24/2017