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.
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 tagPublication'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 (Former researcher)
- External
- Feinerer, Ingo
- Pichler, Reinhard
- Sallinger, Emanuel
- Organization
- Institute for Data, Process and Knowledge Management (AE Polleres) (Details)