Research Projects
Graph Query Languages
Graph databases allow one to store data while emphasizing the importance of the data itself along with its internal connections. GQL, the new standard for graph query languages, has been under development since 2019. Standardization raises many inherent questions on expressivity and complexity. The outcomes of such theoretical analysis can lead to design decisions that would affect the standard.
Incomplete Information
Handling incomplete information is a longstanding problem in data management. Classical research on the subject is focused mainly on simple relational queries (SELECT-FROM-WHERE). In practice, queries include aggregations, comparisons, arithmetics, and more. How can we adapt theory to study such queries? What approaches can be taken to define the notion of query answering under these settings?
SQL Semantics
SQL is inarguably the query language for relational databases (in which data is stored in a tabular form). Its formal semantics is based on Kleene's three-valued logic which is used to handle incomplete information. Unfortunately, the three-valued approach often leads to unintuitive behavior and internal inconsistencies. Is there a way to avoid this? Can we harness existing implementations for that? What lessons can be applied on graph query languages?
Publications
GPC: A Pattern Calculus for Property Graphs
with N.Francis, A.Gheerbrant, P.Guagliardo, L.Libkin, V.Marsault, W.Martens, F.Murlak, A.Rogova, D.Vrgoc
PODS23
Querying Incomplete Numerical Data: Between Certain and Possible Answers
with Marco Console, Leonid Libkin.
PODS23
PODS23
with N.Francis, A.Gheerbrant, P.Guagliardo, L.Libkin, V.Marsault, W.Martens, F.Murlak, A.Rogova, D.Vrgoc
ICDT23
Revisiting Semiring Provenance for Datalog
with Camille Bourgaux, Pierre Bourhis, and Michaël Thomazo.
KR22
Playing Guess Who with Your Kids
with Ami Paz.
INVITED TO Theoretical Computer Science SPECIAL ISSUE
FUN22
ICALP21
ICDT21
TCS20
with Johannes Doleschal, Benny Kimelfeld, Wim Martens.
INVITED TO Logical Methods in Computer Science SPECIAL ISSUE
ICDT20
LMCS22
Complexity Bounds for Relational Algebra over Document Spanners
with Dominik D. Freydenberger, Benny Kimelfeld, Markus Kröll
PODS19
ICDT19
PODS18
CSR18
ICDT17
Incorporating Information Extraction in the Relational Database Model
with Yoav Nahshon Stijn Vansummeren.
BEST PAPER AWARD
WebDB16
A Note on the Emptiness Problem for Alternating Finite-Memory Automata
with Daniel Genkin, Michael Kaminski.
TCS14