A decidability result for conjunctive queries over data trees

Prelegent(ci)

Filip Murlak

Afiliacja

Uniwersytet Warszawski

Termin

14 października 2015 14:15

Pokój

p. 5870

Tytuł w języku angielskim

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

Seminarium

Seminarium „Teoria automatów”

---

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.

---