Quotation Kolaitis, Phokion, Pichler, Reinhard, Sallinger, Emanuel, Savenkov, Vadim. 2020. On the Language of Nested Tuple Generating Dependencies. ACM Transactions on Database Systems. 45 (2), 1-59.




During the past 15 years, schema mappings have been extensively used in formalizing and studying such critical data interoperability tasks as data exchange and data integration. Much of the work has focused on GLAV mappings, i.e., schema mappings specified by source-to-target tuple-generating dependencies (s-t tgds), and on schema mappings specified by second-order tgds (SO tgds), which constitute the closure of GLAV mappings under composition. In addition, nested GLAV mappings have also been considered, i.e., schema mappings specified by nested tgds, which have expressive power intermediate between s-t tgds and SO tgds. Even though nested GLAV mappings have been used in data exchange systems, such as IBM’s Clio, no systematic investigation of this class of schema mappings has been carried out so far. In this article, we embark on such an investigation by focusing on the basic reasoning tasks, algorithmic problems, and structural properties of nested GLAV mappings. One of our main results is the decidability of the implication problem for nested tgds. We also analyze the structure of the core of universal solutions with respect to nested GLAV mappings and develop useful tools for telling apart SO tgds from nested tgds. By discovering deeper structural properties of nested GLAV mappings, we show that also the following problem is decidable: Given a nested GLAV mapping, is it logically equivalent to a GLAV mapping?


Press 'enter' for creating the tag

Publication's profile

Status of publication Published
Affiliation WU
Type of publication Journal article
Journal ACM Transactions on Database Systems
Citation Index SCI
WU Journalrating 2009 A
WU-Journal-Rating new INF-A
Language English
Title On the Language of Nested Tuple Generating Dependencies
Volume 45
Number 2
Year 2020
Page from 1
Page to 59
Reviewed? Y
URL https://dl.acm.org/doi/10.1145/3369554
DOI http://dx.doi.org/10.1145/3369554
Open Access N


Savenkov, Vadim (Former researcher)
Kolaitis, Phokion (University of California, Santa Cruz, United States/USA)
Pichler, Reinhard (Vienna University of Technology, Austria)
Sallinger, Emanuel (Oxford University, United Kingdom)
Institute for Data, Process and Knowledge Management (AE Polleres) (Details)
Google Scholar: Search