On the complexity of deriving schema mappings from database instances

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of deriving schema mappings from database instances

Full text

Pdf (332 KB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems table of contents

Vancouver, Canada

SESSION: Schema Mappings table of contents

Pages 23-32

Year of Publication: 2008

ISBN:978-1-60558-108-8

Authors

Pierre Senellart	INRIA Saclay - Île-de-France & Universitéé Paris-Sud, Orsay, France
Georg Gottlob	Oxford University, Oxford, United Kngdm

Sponsors

ACM: Association for Computing Machinery
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 28, Downloads (12 Months): 65, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1376916.1376921 What is a DOI?

ABSTRACT

We introduce a theoretical framework for discovering relationships between two database instances over distinct and unknown schemata. This framework is grounded in the context of data exchange. We formalize the problem of understanding the relationship between two instances as that of obtaining a schema mapping so that a minimum repair of this mapping provides a perfect description of the target instance given the source instance. We show that this definition yields "intuitive" results when applied on database instances derived from each other by basic operations. We study the complexity of decision problems related to this optimality notion in the context of different logical languages and show that, even in very restricted cases, the problem is of high complexity.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Arenas, L. Bertossi, and J. Chomicki. Consistent query answers in inconsistent databases. In Proc. PODS, Philadelphia, United States, May 1999.
	2	C. Beeri, R. Fagin, D. Maier, A. Mendelzon, J. Ullman, and M. Yannakakis. Properties of acyclic database schemes. In Proc. STOC, Milwaukee, USA, May 1981.
	3	P. Bernstein. Applying model management to classical meta data. In Proc. CIDR, Asilomar, USA, Jan. 2003.
	4	P. A. Bernstein and D.-M. W. Chiu. Using semi-joins to solve relational queries. Journal of the ACM, 28(1):25--40, 1981.
	5	V. Crescenzi, G. Mecca, and P. Merialdo. Roadrunner: Towards automatic data extraction from large Web sites. In Proc. VLDB, Roma, Italy, Sept. 2001.
	6	R. Diestel. Graph Theory. Springer, New York, USA, 2005.
	7	R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query answering. In Proc. ICDT, Siena, Italy, Jan. 2003.
	8	R. Fagin, P. G. Kolaitis, L. Popa, and W. C. Tan. Quasi-inverses of schema mapping. In Proc. PODS, Beijing, China, June 2007.
	9	R. Fagin, P. G. Kolaitis, W.-C. Tan, and L. Popa. Composing schema mappings: Second-order dependencies to the rescue. In Proc. PODS, Paris, France, June 2004.
	10	G. H. L. Fletcher. On the data mapping problem. PhD thesis, Indiana University, 2007.
	11	M. R. Garey and D. S. Johnson. Computers And Intractability. A Guide to the Theory of NP--completeness. W. H. Freeman, New York, USA, 1979.
	12	G. Gottlob, N. Leone, and F. Scarcello. On the complexity of some inductive logic programming problems. In Proc. ILP, Prag, Czech Republic, Sept. 1997.
	13	G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. In Proc. PODS, Philadelphia, United States, May 1999.
	14	L. Ilie, R. Solis-Oba, and S. Yu. Reducing the size of NFAs by using equivalences and preorders. In Combinatorial Pattern Matching, Jeju Island, South Korea, June 2002.
	15	P. G. Kolaitis. Schema mappings, data exchange, and metadata management. In Proc. PODS, Baltimore, Maryland, June 2005.
	16	D. KQnig. Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft, Leipzig, Germany, 1936.
	17	N. Lavrač and S. Džeroski. Inductive Logic Programming: Techniques and Applications. Ellis Horwood, New York, USA, 1994.
	18	M. Lenzerini. Data integration: a theoretical perspective. In Proc. PODS, Madison, USA, June 2002.
	19	M. Li and P. Vitányi. An Introduction to Kolmogorov a Complexity and Its Applications. Springer, New York, USA, second edition, 1997.
	20	E. Rahm and P. A. Bernstein. A survey of approaches to automatic schema matching. VLDB Journal, 10(4):334--350, 2001.
	21	R. E. Tarjan and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13(3):566--579, 1984.
	22	M. Yannakakis. Algorithms for acyclic database schemes. In Proc. VLDB, Cannes, France, Sept. 1981.