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
until May 4 2021: registration (please contact the organisers directly)
May 6 — May 7 2021: the workshop
Get-together on gather.town
Long talk
Floris Geerts What if Codd would have been a linear algebraist?
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
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.Jorge Perez The Expressiveness of Matrix and Tensor Query Languages in Terms of Machine-Learning Operators
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.Get-together on gather.town
Get-together on gather.town
Long talk
Ahmet Kara and Dan Olteanu Trade-Offs in Incremental Maintenance for Conjunctive Queries
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.break on gather.town
Short talks
Jens Keppeler Answering Conjunctive Queries Under Updates
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 asNils Vortmeier Dynamic query maintenance via first-order logic
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.Get-together on gather.town