Describing differences between databases

ABSTRACT

We study the novel problem of efficiently computing the update distance for a pair of relational databases. In analogy to the edit distance of strings, we define the update distance of two databases as the minimal number of set-oriented insert, delete and modification operations necessary to transform one database into the other. We show how this distance can be computed by traversing a search space of database instances connected by update operations. This insight leads to a family of algorithms that compute the update distance or approximations of it. In our experiments we observed that a simple heuristic performs surprisingly well in most considered cases.Our motivation for studying distance measures for databases stems from the field of scientific databases. There, replicas of a single database are often maintained at different sites, which typically leads to (accidental or planned) divergence of their content. To re-create a consistent view, these differences must be resolved. Such an effort requires an understanding of the process that produced them. We found that minimal update sequences of set-oriented update operations are a proper and concise representation of systematic errors, thus giving valuable clues to domain experts responsible for conflict resolution.

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: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 4: H. M.Berman, J. Westbrook, Z. Feng, G. Gilliland, T. N. Bhat, H. Weissig, I. N. Shindyalov, P. E. Bourne. The Protein Data Bank. Nucleic Acids Research, Vol. 28(1), 2000, 235--242.
• 5: T. N. Bhat, et al. The PDB data uniformity project, Nucleic Acid Research, Vol. 29(1), 2001, 214--218.
• 6: H. Boutselakis, et al. E-MSD: the European Bioinformatics Institute Macromolecular Structure Database. Nucleic Acid Research, Vol. 31(1), 2003, 458--462.
• 7: Philip Bohannon , Wenfei Fan , Michael Flaster , Rajeev Rastogi, A cost-based model and effective heuristic for repairing constraints by value modification, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066175]
• 8: Sudarshan S. Chawathe , Hector Garcia-Molina, Meaningful change detection in structured data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.26-37, May 11-15, 1997, Tucson, Arizona, United States
• 9: Gao Cong , Anthony K. H. Tung , Xin Xu , Feng Pan , Jiong Yang, FARMER: finding interesting rule groups in microarray datasets, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007587]
• 10: Peter Dadam , Vincent Y. Lum , H.-D. Werner, Integration of Time Versions into a Relational Database System, Proceedings of the 10th International Conference on Very Large Data Bases, p.509-522, August 27-31, 1984
• 11: Weiguo Fan , Hongjun Lu , Stuart E. Madnick , David Cheung, Discovering and reconciling value conflicts for numerical data integration, Information Systems, v.26 n.8, p.635-656, December 2001 [doi>10.1016/S0306-4379(01)00043-6]
• 12: Mauricio A. Hernández , Salvatore J. Stolfo, The merge/purge problem for large databases, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.127-138, May 22-25, 1995, San Jose, California, United States
• 13: Wilburt Labio , Hector Garcia-Molina, Efficient Snapshot Differential Algorithms for Data Warehousing, Proceedings of the 22th International Conference on Very Large Data Bases, p.63-74, September 03-06, 1996
• 14: V. I. Levenshtein. Binary codes capable of correcting insertions and reversals. Sov. Phys. Dokl., 10:707--10, 1966.
• 15: A. E. Monge, C. P. Elkan. An efficient domain-independent algorithm for detecting approximately duplicate database tuples. Proc. SIGMOD Workshop on Data Mining and Knowledge Discovery, 1997.
• 16: Ulf Leser , Johann-Christoph Freytag, Mining for patterns in contradictory data, Proceedings of the 2004 international workshop on Information quality in information systems, June 18, 2004, Paris, France [doi>10.1145/1012453.1012463]
• 17: H. Müller, J.-C. Freytag, and U. Leser. On the Distance of Databases, Technical Report, HUB-IB-199, March 2006.
• 18: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceeding of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
• 19: K. Rother, H. Müller, S. Trissl, I. Koch, T. Steinke, R. Preissner, C. Frömmel, U. Leser. COLUMBA: Multidimensional Data Integration of Protein Annotations, Int. Workshop on Data Integration in Life Sciences (DILS 2004), Leipzig, Germany, 2004.
• 20: Gottfried Vossen, Data models, database languages and database management systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 21: Jianyong Wang , Jiawei Han , Jian Pei, CLOSET+: searching for the best strategies for mining frequent closed itemsets, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956779]
• 22: W. Winkler. The state of record linkage and current research problems. Technical report, Statistical Research Division, U.S. Bureau of the Census, Washington, DC, 1999.
• 23: M. J. Zaki and C.-J. Hsiao. CHARM: An efficient algorithm for closed itemset mining. In Proc. of the Second SIAM Int. Conference on Data Mining, Arlington, VA, 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Scientific databases

General Terms:
Algorithms, Documentation

Keywords:
conflict resolution, contradicting databases, update distance