On the complexity of deriving schema mappings from database instances

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

• 1: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki, Consistent query answers in inconsistent databases, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.68-79, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303983]
• 2: Catriel Beeri , Ronald Fagin , David Maier , Alberto Mendelzon , Jeffrey Ullman , Mihalis Yannakakis, Properties of acyclic database schemes, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.355-362, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802489]
• 3: P. Bernstein. Applying model management to classical meta data. In Proc. CIDR, Asilomar, USA, Jan. 2003.
• 4: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• 5: Valter Crescenzi , Giansalvatore Mecca , Paolo Merialdo, RoadRunner: Towards Automatic Data Extraction from Large Web Sites, Proceedings of the 27th International Conference on Very Large Data Bases, p.109-118, September 11-14, 2001
• 6: R. Diestel. Graph Theory. Springer, New York, USA, 2005.
• 7: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 8: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa , Wang-Chiew Tan, Quasi-inverses of schema mappings, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265548]
• 9: Ronald Fagin , Phokion G. Kolaitis , Wang-Chiew Tan , Lucian Popa, Composing schema mappings: second-order dependencies to the rescue, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055572]
• 10: George H. L. Fletcher, On the data mapping problem, Indiana University, Indianapolis, IN, 2007
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: Georg Gottlob , Nicola Leone , Francesco Scarcello, On the Complexity of Some Inductive Logic Programming Problems, Proceedings of the 7th International Workshop on Inductive Logic Programming, p.17-32, September 17-20, 1997
• 13: Georg Gottlob , Nicola Leone , Francesco Scarcello, Hypertree decompositions and tractable queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.21-32, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303979]
• 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: Phokion G. Kolaitis, Schema mappings, data exchange, and metadata management, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065176]
• 16: D. KQnig. Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft, Leipzig, Germany, 1936.
• 17: Nada Lavrac , Saso Dzeroski, Inductive Logic Programming: Techniques and Applications, Routledge, New York, NY, 1993
• 18: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 19: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 20: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 21: Robert E. Tarjan , Mihalis Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on Computing, v.13 n.3, p.566-579, August 1984 [doi>10.1137/0213035]
• 22: Mihalis Yannakakis, Algorithms for acyclic database schemes, Proceedings of the seventh international conference on Very Large Data Bases, p.82-94, September 09-11, 1981, Cannes, France

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.5 Heterogeneous Databases

General Terms:
Languages, Theory

Keywords:
complexity, data exchange, instance, match, schema mapping