You are not logged in | Log in

joint work with Wojciech Czerwinski, Claire David, and Pawel Parys

Speaker(s)
Filip Murlak
Affiliation
Uniwersytet Warszawski
Date
Oct. 14, 2015, 2:15 p.m.
Room
room 5870
Seminar
Seminar Automata Theory

I will show how to decide validity and containment for unions of
conjunctive queries in which each conjunctive query uses either data
equalities or data inequalities (but not both). This extends
simultaneously two decidability results by Björklund, Martens, and
Schwentick, for the cases with only equalities and only inequalities.
The technique is based on a simple geometric lemma. The result has
applications to problems related to integrity constraints and data
exchange.