University of Birmingham > Talks@bham > Theoretical computer science seminar > Relational Lattices

Relational Lattices

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Paul Levy.

This is a joint work with Szabolcs Mikulas (Birkbeck) and Jan Hidders (TU Delft). We study an interpretation of lattice connectives as “natural join” and “inner union” operations between database relations with non-uniform headers (also known as relation “schemes” or “types”). This interpretation yields a class of lattices (with an additional constant) which has not been considered in the existing lattice-theoretical literature. They do not possess most of known weak distributivity properties, e.g., local modularity, almost neardistributivity, upper- or lower- semimodularity etc. And yet, the variety generated by these structures is smaller than the variety of all lattices. We propose to call them “relational lattices” or “Tropashko lattices”—-to honour the researcher from Oracle who invented them.

The quasi-equational theory of Tropashko lattices seems of interest both from the database perspective and the algebraic perspective. We discuss its axiomatizability and decidability and propose an equational axiomatization for a corresponding abstract algebraic class. While several questions remain open, our main result shows that relational lattices in many aspects display behaviour typical of “untamed” structures from algebraic logic like cylindric or relation algebras. They also provide an interesting alternative to other algebras of “heterogeneous” relations, such as those proposed by Craig or Quine.

This talk is part of the Theoretical computer science seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.