[Back]


Talks and Poster Presentations (with Proceedings-Entry):

I. Feinerer, R. Pichler, E. Sallinger, V. Savenkov:
"On the Undecidability of the Equivalence of Second-Order Tuple Generating Dependencies";
Talk: AMW - Alberto Mendelzon International Workshop on Foundations of Data Management, Santiago, Chile; 2011-05-09 - 2011-05-12; in: "CEUR Workshop Proceedings", P. Barceló, V. Tannen (ed.); 749 (2011), ISSN: 1613-0073; Paper ID 5, 13 pages.



English abstract:
Second-Order tuple generating dependencies (SO tgds) were introduced
by Fagin et al. to capture the composition of simple schema mappings.
Testing the equivalence of SO tgds would be important for applications like model management and mapping optimization. However, we prove the undecidability of the logical equivalence of SO tgds. Moreover, under weak additional assumptions, we also show the undecidability of a relaxed notion of equivalence between two SO tgds, namely the so-called conjunctive query equivalence.

Created from the Publication Database of the Vienna University of Technology.