License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.25
URN: urn:nbn:de:0030-drops-33598
URL: http://drops.dagstuhl.de/opus/volltexte/2011/3359/
Go to the corresponding Portal


Kolaitis, Phokion G.

Schema Mappings and Data Examples: Deriving Syntax from Semantics (Invited Talk)

pdf-format:
Document 1.pdf (218 KB)


Abstract

Schema mappings are high-level specifications that describe the relationship between two database schemas. Schema mappings are considered to be the essential building blocks in such critical data interoperability tasks as data exchange and data integration. For this reason, they have been the focus of extensive research investigations over the past several years. Since in real-life applications schema mappings can be quite complex, it is important to develop methods and tools for illustrating, explaining, and deriving schema mappings. A promising approach to this effect is to use “good” data examples that illustrate the schema mapping at hand. In this talk, we present an overview of recent work on characterizing and deriving schema mappings via a finite set of data examples. We show that every LAV schema mapping (i.e., a schema mapping specified by a finite set of local-as-view tuple-generating dependencies) is uniquely characterized by a finite set of universal data examples with respect to the class of all LAV schema mappings. We also show that this type of result does not hold for arbitrary GAV schema mappings (i.e., schema mappings specified by a finite set of global-as-view tuple- generating dependencies). After this, we give a necessary and sufficient algorithmic condition for a GAV schema mapping to be uniquely characterizable by a finite set of universal examples with respect to the class of all GAV schema mappings. Along the way, we establish tight connections between unique characterizability of schema mappings and homomorphism dualities. This is joint work with Bogdan Alexe (IBM Research - Almaden), Balder ten Cate (UC Santa Cruz), and Wang-Chiew Tan (UC Santa Cruz and IBM Research - Almaden) based on [1, 2, 3].

BibTeX - Entry

@InProceedings{kolaitis:LIPIcs:2011:3359,
  author =	{Phokion G. Kolaitis},
  title =	{{Schema Mappings and Data Examples: Deriving Syntax from Semantics (Invited Talk)}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{25--25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3359},
  URN =		{urn:nbn:de:0030-drops-33598},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.25},
  annote =	{Keywords: Schema mappings, database constraints, data exchange, data integration, universal solutions, homomorphism dualities}
}

Keywords: Schema mappings, database constraints, data exchange, data integration, universal solutions, homomorphism dualities
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011


DROPS-Home | Fulltext Search | Imprint Published by LZI