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

Title in Polish

A decidability result for conjunctive queries over data trees

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.

---