Seminars

Title: Extracting nested relational queries from implicit definitions

Abstract:
arxiv.org/pdf/2005.06503.pdf

In this talk, I will present results obtained jointly with Michael
Benedikt establishing a connection between the Nested Relational
Calculus (NRC) and sets implicitly definable using Δ₀ formulas.

Call a formula φ(I,O) an implicit definition of the relation O(x,...) in
terms of I(y,...) if O is functionally determined by I: for every I, O,
O', if both φ(I,O) and φ(I,O') hold, then we have O ≡ O'. When φ is
first-order and I and O are relations over base sorts, then Beth's
definability theorem states that there is a first-order formula
ψ(I,x,...) corresponding to O whenever φ(I,O) holds. Further, this
explicit definition ψ can be effectively be computed from a sequent
calculus proof witnessing that φ is functional. This allows for
practical use of implicit definitions in the context of database
programming, as there is a well-established link between fragments of
explicitly FO definable relations and relational calculi.

NRC is a conservative extension of relational calculi from database
theory with limited powerset types in addition to tupling and anonymous
base types. NRC expressions thus not only encompass flat relations over
primitive datatypes like SQL but also nested collections, while
remaining useful in practice.

We extend the above correspondence between first-order logic and flat
relational queries to NRC and implicit definitions using set-theoretical
Δ₀ formulas over (typed) nested collection. Our proof of the equivalence
goes through a notion of Δ₀-interpretation and a generalization of Beth
definability for multi-sorted structures. This proof is non-constructive
and thus does not yield any useful algorithm for converting implicit
definitions into NRC terms. Using an approach more closely related to
proof-theoretic interpolation, we give a constructive proof of the
result restricted to intuitionistic provability, i.e, when the input
functionality proof π of φ(I,O) is carried out in intuitionistic logic.
Further, if π is cut-free, this can be done efficiently. Whether or not
there exists a polynomial-time procedure working with classical proofs
of functionality is still an open problem.

I will focus on the effective result for the talk, and if time allows,
discuss the difficulties with extending it to classical logic. I will
not assume any background in either database or model theory.

Title: The Complexity of Counting Problems over Incomplete Databases

Abstract: In this presentation, I will talk about various counting problems that naturally
arise in the context of query evaluation over incomplete databases. Incomplete
databases are relational databases that can contain unknown values in the form
of labeled nulls. We will assume that the domains of these unknown values are
finite and, for a Boolean query $q$, we will consider the following two
problems: given as input an incomplete database $D$, (a) return the number of
completions of $D$ that satisfy $q$; or (b) return or the number of valuations
of the nulls of $D$ yielding a completion that satisfies $q$.


We will study the computational complexity of these problems when $q$ is a
self-join--free conjunctive query, and study the impact on the complexity of
the following two restrictions: (1) every null occurs at most once in $D$ (what
is called *Codd tables*); and (2) the domain of each null is the same. Roughly
speaking, we will see that counting completions is much harder than counting
valuations, and that both (1) and (2) can reduce the complexity of our
problems.

I will also talk about the approximability of these problems and prove that,
while counting valuations can efficiently be approximated, in most cases
counting completions cannot.

On our way, we will encounter the counting complexity classes #P, Span-P and
Span-L.

The presentation will be based on joint work with Marcelo Arenas and Pablo
Barcelo; see arxiv.org/abs/1912.11064