BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//132.216.98.100//NONSGML kigkonsult.se iCalcreator 2.20.4//
BEGIN:VEVENT
UID:20261001T084424EDT-8316xrhUNe@132.216.98.100
DTSTAMP:20261001T124424Z
DESCRIPTION:Title: (Un)Decidability of logical theories of the natural join
  and inner union. (Generalized ultrametric spaces for databases)\n\nThe na
 tural join and the inner union operations combine relations (tables) of a 
 database.\n	\n	Tropashko and Spight realized that these two operations are t
 he meet and join operations in a class of lattices\, known by now as the r
 elational lattices. They proposed then lattice theory as an algebraic appr
 oach to the theory of databases\, alternative to the relational algebra. P
 revious works proved that the quasiequational theory of these lattices - t
 hat is\, the set of definite Horn sentences valid in all the relational la
 ttices - is undecidable\, even when the signature is restricted to the pur
 e lattice signature. In this talk I'll argue that injective generalized ul
 trametric spaces on a powerset algebra yield duals for these lattices. In 
 particular\, I'll argue that ideas stemming from the theory of generalized
  ultrametric spaces are the keys to prove that the equational theory of re
 lational lattices is decidable - by finding a finite countermodel of bound
 ed size. Namely\, we provide an algorithm to decide if two lattice theoret
 ic terms t\, s are made equal under all intepretations in some relational 
 lattice. We achieve this goal by showing that if an inclusion t ≤ s fails 
 in any of these lattices\, then it fails in a relational lattice whose siz
 e is bound by a triple exponential function of the sizes of t and s.\n
DTSTART:20181120T193000Z
DTEND:20181120T203000Z
LOCATION:Room 920\, Burnside Hall\, CA\, QC\, Montreal\, H3A 0B9\, 805 rue 
 Sherbrooke Ouest
SUMMARY:Luigi Santocanale\, Aix-Marseille 
URL:https://www.mcgill.ca/mathstat/channels/event/luigi-santocanale-aix-mar
 seille-291796
END:VEVENT
END:VCALENDAR