NDLI: Characterizing schema mappings via data examples

Content Provider	ACM Digital Library
Author	Tan, Wang-Chiew Alexe, Bogdan Kolaitis, Phokion G. Cate, Balder TEN
Copyright Year	2011
Abstract	Schema mappings are high-level specifications that describe the relationship between two database schemas; they are considered to be the essential building blocks in data exchange and data integration, and have been the object of extensive research investigations. Since in real-life applications schema mappings can be quite complex, it is important to develop methods and tools for understanding, explaining, and refining schema mappings. A promising approach to this effect is to use “good” data examples that illustrate the schema mapping at hand. We develop a foundation for the systematic investigation of data examples and obtain a number of results on both the capabilities and the limitations of data examples in explaining and understanding schema mappings. We focus on schema mappings specified by source-to-target tuple generating dependencies (s-t tgds) and investigate the following problem: which classes of s-t tgds can be “uniquely characterized” by a finite set of data examples? Our investigation begins by considering finite sets of positive and negative examples, which are arguably the most natural choice of data examples. However, we show that they are not powerful enough to yield interesting unique characterizations. We then consider finite sets of universal examples, where a universal example is a pair consisting of a source instance and a universal solution for that source instance. We first show that unique characterizations via universal examples is, in a precise sense, equivalent to the existence of Armstrong bases (a relaxation of the classical notion of Armstrong databases). After this, we show that every schema mapping specified by LAV s-t tgds is uniquely characterized by a finite set of universal examples with respect to the class of LAV s-t tgds. Moreover, this positive result extends to the much broader classes of $\textit{n}-modular$ schema mappings, $\textit{n}$ a positive integer. Finally, we study the unique characterizability of GAV schema mappings. It turns out that some GAV schema mappings are uniquely characterizable by a finite set of universal examples with respect to the class of GAV s-t tgds, while others are not. By unveiling a tight connection with homomorphism dualities, we establish an effective, sound, and complete criterion for determining whether or not a GAV schema mapping is uniquely characterizable by a finite set of universal examples with respect to the class of GAV s-t tgds.
Starting Page	1
Ending Page	48
Page Count	48
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/2043652.2043656
Volume Number	36
Issue Number	4
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-12-19
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Schema mappings Data examples Data exchange Data integration
Content Type	Text
Resource Type	Article
Subject	Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Characterizing schema mappings via data examples

Designing and refining schema mappings via data examples

MapMerge: correlating independent schema mappings

Normalization and optimization of schema mappings

Collaborative data sharing via update exchange and provenance

Schema mappings and data examples ( EDBT '13 )

Learning schema mappings

Quasi-inverses of schema mappings

Inverting schema mappings

Characterizing schema mappings via data examples

Similar Documents

Characterizing schema mappings via data examples

Designing and refining schema mappings via data examples

MapMerge: correlating independent schema mappings

Normalization and optimization of schema mappings

Collaborative data sharing via update exchange and provenance

Schema mappings and data examples ( EDBT '13 )

Learning schema mappings

Quasi-inverses of schema mappings

Inverting schema mappings

Characterizing schema mappings via data examples