We support the TCS4F — an initiative for reducing the carbon footprint. Learn more...
log in

May 6 — May 7

Logic and databases 2021 workshop

Spotlight on Logic & Databases is the third in a series of online workshops on Logic, Games and Automata. The aim of this workshop series is to bring together the community throughout the year, around four topics:

+ Games: 25-26 November 2020 (past)
+ Transducers: 17-18 March 2021(past)
+ Logic and databases: this workshop, 6-7 May 2021
+ Automata and category

organisers:
Thomas Zeume and Nils Vortmeier

IMPORTANT DATES

until May 4 2021: registration (please contact the organisers directly)
May 6 — May 7 2021: the workshop

Program

06

Thursday, May 06: Matrix query languages

Get-together on gather.town

Long talk

  • Floris Geerts What if Codd would have been a linear algebraist?

    Authors:

    Abstract:

    Imagine that instead of the relational data model and relational algebra, data would be stored as matrices and queries would consist of linear algebra operators. How would such a matrix query language look like? What can we do and cannot do in such a language? And how does it relate to query languages based on first-order logic or the relational algebra? In this talk, some answers to these questions will be given. Furthermore, zooming in on adjacency matrices (graphs) connections to graph neural networks will be made.

break on gather.town

Short talks

  • Erich Grädel Logics with Linear-Algebraic Operators, Approximations of Isomorphism, and the Problem of Capturing Polynomial Time

    Authors:

    Abstract:

    We prove that no extension of fixed-point logic with linear-algebraic operators can capture PTIME, unless it includes such operators for ALL prime characteristics. We study approximations of graph isomorphism by invertible map equivalences, parametrised by a number k and a set Q of primes, which refine the well-known Weisfeiler-Leman method. The intuition is that k-Q-IM-equivalent graphs cannot be distinguished by a refinement of k-tuples given by linear operators acting on vector spaces over fields of characteristic p, for any p in Q. These equivalences first appeared in the study of rank logic, but they can be used to delimit the expressive power of any extension of fixed-point logic with linear-algebraic operators. We define an infinitary logic with k variables and all linear-algebraic operators over finite vector spaces of characteristic p in Q and show that the k-Q-IM-equivalence is the natural notion of elementary equivalence for this logic. By means of a new and much deeper algebraic analysis of a generalized variant, for any prime p, of the CFI-structures due to Cai, Fürer, and Immerman, we prove that, as long as Q is not the set of all primes, there is no k such that k-Q-IM-equivalence is the same as isomorphism. It follows that there are polynomial-time properties of graphs which are not definable in the infinitary logic with all Q-linear-algebraic operators and finitely many variables. Our analysis requires substantial algebraic machinery, including a homogeneity property of CFI-structures and Maschke's Theorem, an important result from the representation theory of finite groups.

    This talk is based on joint work with Anuj Dawar and Wied Pakusa.
  • Jorge Perez The Expressiveness of Matrix and Tensor Query Languages in Terms of Machine-Learning Operators

    Authors:

    Abstract:

    Tensors are one of the most widely used data structures in modern Machine Learning (ML) applications. Although they provide a flexible way of storing and accessing data, they often expose too many low-level details that may result in error prone code that is difficult to maintain and extend. This has lead a part of the ML community to consider tensors, as they are used today by scientists and practitiones, a harmful abstraction.

    Abstracting low-level functionalities into high-level operators in the form of a query language is a task in which the Data Management community has extensive experience. It is thus important to understand how such an experience can be applied in the design of useful languages for tensor manipulation. In this talk I will present a study on matrix and tensor query languages that have been recently proposed by the database community. I will show, by using examples, how these proposals are in line with the practical interest in rethinking tensor abstractions. I will also show some results on comparing the languages in terms of operators that naturally arise in Machine Learning pipelines, such as convolution, matrix-inverse, and Einstein summation.

    This talk is based on a joint work with Pablo Barceló, Nelson Higuera and Bernardo Subercaseaux presented at DEEM@SIGMOD 2019 and ICDT 2020.

Get-together on gather.town

07

Friday, May 07: Updates for query languages

Get-together on gather.town

Long talk

  • Ahmet Kara and Dan Olteanu Trade-Offs in Incremental Maintenance for Conjunctive Queries

    Authors:

    Abstract:

    We give an overview on recent results and techniques for the evaluation of conjunctive queries under single-tuple updates to the input database. We consider a refinement of the overall evaluation time into preprocessing time, which is used to compute a data structure that represents the query result, the update time, which is the time to update the data structure under inserts and deletes to the input data, and the enumeration delay, which is the time to list one distinct tuple after another one has been listed from the data structure.

    We first review key results for q-hierarchical, free-connex acyclic, and general conjunctive queries that achieve constant-delay enumeration at the expense of varying preprocessing and update times. We then present IVMepsilon, an approach for incremental maintenance for hierarchical queries that can recover these previous results and allows for flexible trade-offs between preprocessing time, update time, and enumeration delay

break on gather.town

Short talks

  • Jens Keppeler Answering Conjunctive Queries Under Updates

    Authors:

    Abstract:

    This talk investigates the query evaluation problem for fixed queries over fully dynamic databases, where tuples can be inserted or deleted. The task is to design a dynamic algorithm that immediately reports the new result of a fixed query after every database update. In particular, the goal is to construct a data structure that allows to support the following scenario. After every database update, the data structure can be updated in constant time such that afterwards we are able to support some procedures such as
    * test within constant time for a given tuple whether or not it belongs to the query result,
    * output the number of tuples in the query result,
    * enumerate all tuples in the query result with constant delay.

    In this talk, conjunctive queries on arbitrary relational databases are considered. The notion of q-hierarchical conjunctive queries, for which the scenario above is tractable, will be introduced.
  • Nils Vortmeier Dynamic query maintenance via first-order logic

    Authors:

    Abstract:

    When we talk about query evaluation, we usually think about a static setting, where we express a database query in a declarative query language like SQL and let a system evaluate the query on the input database. The system returns the query result and the task is finished. But many real-world scenarios have a dynamic nature, where databases change over time and the query result needs to be available for the current input at all times.

    In the dynamic complexity framework, as introduced by Patnaik and Immerman in the 90s, we study the expressiveness of declarative query languages in dynamic scenarios. Its main class DynFO contains the queries whose results can be maintained by updates of the result (and additionally stored relations) that are expressed in first-order logic (or, equivalently, relational algebra).

    In this talk, we highlight the expressive power of DynFO by earlier and more recent examples, mostly concerning variants of the graph reachability query. We will see that beyond insertions and deletions of single tuples, we can also deal with more complex changes to the input database. We will also see that linear algebra was successfully used to obtain some of the results. We will also discuss recent research that studies how DynFO expressibility results may lead to efficient maintenance algorithms.

Get-together on gather.town

Contact

designed and delivered