Relational Lattices

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

• Tadeusz Litak, University of Leicester
• Friday 21 May 2010, 14:00-15:00
• UG40 Computer Science.

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.

This talk is included in these lists:

• Computer Science Departmental Series
• Computer Science Distinguished Seminars
• Theoretical computer science seminar
• UG40 Computer Science
• computer sience

Note that ex-directory lists are not shown.