Quotation Feinerer, Ingo, Pichler, Reinhard, Sallinger, Emanuel, Savenkov, Vadim. 2015. On the undecidability of the equivalence of second-order tuple generating dependencies. Information Systems Journal 48 113-129.


RIS


BibTeX

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.

Tags

Press 'enter' for creating the tag

Publication's profile

Status of publication Published
Affiliation WU
Type of publication Journal article
Journal Information Systems Journal (ISJ)
Citation Index SSCI
WU Journalrating 2009 A
WU-Journal-Rating new INF-A, STRAT-A, WH-A
Language English
Title On the undecidability of the equivalence of second-order tuple generating dependencies
Volume 48
Year 2015
Page from 113
Page to 129
Reviewed? Y
URL http://dx.doi.org/10.1016/j.is.2014.09.003

Associations

People
Savenkov, Vadim (Details)
External
Feinerer, Ingo
Pichler, Reinhard
Sallinger, Emanuel
Organization
Applied Information Technology (Details)
Google Scholar: Search