×

Exploiting schemas in data synchronization. (English) Zbl 1115.68056

Summary: Increased reliance on optimistic data replication has led to burgeoning interest in tools and frameworks for synchronizing disconnected updates to replicated data. But good data synchronizers are challenging both to specify and to build.We have implemented a generic synchronization framework, called Harmony, that can be used to build state-based synchronizers for a wide variety of tree-structured data formats. A novel feature of this framework is that the synchronization process – in particular, the recognition of conflicts – is driven by the schema of the structures being synchronized.We formalize Harmony’s synchronization algorithm, prove that it obeys a simple and intuitive specification, and illustrate, using simple address books as a case study, how it can be used to synchronize trees representing a variety of specific forms of application data, including sets, records, tuples, and relations.

MSC:

68P05 Data structures

Software:

Unison
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.N. Foster, M.B. Greenwald, J.T. Moore, B.C. Pierce, A. Schmitt, Combinators for bi-directional tree transformations: A linguistic approach to the view update problem, in: ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), Long Beach, California, 2005, pp. 233-246; J.N. Foster, M.B. Greenwald, J.T. Moore, B.C. Pierce, A. Schmitt, Combinators for bi-directional tree transformations: A linguistic approach to the view update problem, in: ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), Long Beach, California, 2005, pp. 233-246 · Zbl 1369.68136
[2] M.B. Greenwald, S. Khanna, K. Kunal, B.C. Pierce, A. Schmitt, Agreeing to agree: Conflict resolution for optimistically replicated data, in: S. Dolev (Ed.), International Symposium on Distributed Computing (DISC), 2006; M.B. Greenwald, S. Khanna, K. Kunal, B.C. Pierce, A. Schmitt, Agreeing to agree: Conflict resolution for optimistically replicated data, in: S. Dolev (Ed.), International Symposium on Distributed Computing (DISC), 2006 · Zbl 1155.68330
[3] T. Lindholm, XML three-way merge as a reconciliation engine for mobile data, in: ACM Workshop on Data Engineering for Wireless and Mobile Access (MobiDE), San Diego, California, 2003, pp. 93-97; T. Lindholm, XML three-way merge as a reconciliation engine for mobile data, in: ACM Workshop on Data Engineering for Wireless and Mobile Access (MobiDE), San Diego, California, 2003, pp. 93-97
[4] Chawathe, S. S.; Rajamaran, A.; Garcia-Molina, H.; Widom, J., Change detection in hierarchically structured information, ACM SIGMOD Record, 25, 2, 493-504 (1996)
[5] M. Lanham, A. Kang, J. Hammer, A. Helal, J. Wilson, Format-independent change detection and propagation in support of mobile computing, in: Brazilian Symposium on Databases (SBBD), Gramado, Brazil, 2002, pp. 27-41; M. Lanham, A. Kang, J. Hammer, A. Helal, J. Wilson, Format-independent change detection and propagation in support of mobile computing, in: Brazilian Symposium on Databases (SBBD), Gramado, Brazil, 2002, pp. 27-41
[6] Bancilhon, F.; Spyratos, N., Update semantics of relational views, ACM Trans. Database Systems, 6, 4, 557-575 (1981) · Zbl 0465.68059
[7] T. Howes, M. Smith, F. Dawson, RFC 2425: A MIME content-type for directory information, September 1998; T. Howes, M. Smith, F. Dawson, RFC 2425: A MIME content-type for directory information, September 1998
[8] Dal Zilio, S.; Lugiez, D.; Meyssonnier, C., A logic you can count on, (ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), Venice, Italy (2004), ACM Press), 135-146 · Zbl 1325.03032
[9] Saito, Y.; Shapiro, M., Optimistic replication, Computing Surveys, 37, 1, 42-81 (2005)
[10] W.K. Edwards, E.D. Mynatt, K. Petersen, M.J. Spreitzer, D.B. Terry, M.M. Theimer, Designing and implementing asynchronous collaborative applications with Bayou, in: ACM Symposium on User Interface Software and Technology (UIST), Banff, Alberta, 1997, pp. 119-128; W.K. Edwards, E.D. Mynatt, K. Petersen, M.J. Spreitzer, D.B. Terry, M.M. Theimer, Designing and implementing asynchronous collaborative applications with Bayou, in: ACM Symposium on User Interface Software and Technology (UIST), Banff, Alberta, 1997, pp. 119-128
[11] A.-M. Kermarrec, A. Rowstron, M. Shapiro, P. Druschel, The IceCube approach to the reconciliation of diverging replicas, in: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), Newport, Rhode Island, 2001, pp. 210-218; A.-M. Kermarrec, A. Rowstron, M. Shapiro, P. Druschel, The IceCube approach to the reconciliation of diverging replicas, in: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), Newport, Rhode Island, 2001, pp. 210-218
[12] P. Molli, G. Oster, H. Skaf-Molli, A. Imine, Using the transformational approach to build a safe and generic data synchronizer, in: ACM SIGGROUP Conference on Supporting Group Work (GROUP), Sanibel Island, Florida, 2003, pp. 212-220; P. Molli, G. Oster, H. Skaf-Molli, A. Imine, Using the transformational approach to build a safe and generic data synchronizer, in: ACM SIGGROUP Conference on Supporting Group Work (GROUP), Sanibel Island, Florida, 2003, pp. 212-220
[13] Satyanarayanan, M.; Kistler, J. J.; Kumar, P.; Okasaki, M. E.; Siegel, E. H.; Steere, D. C., Coda: A highly available file system for a distributed workstation environment, IEEE Trans. Comput. C, 39, 4, 447-459 (1990)
[14] Page, T. W.; Guy, R. G.; Heidemann, J. S.; Ratner, D.; Reiher, P. L.; Goel, A.; Kuenning, G. H.; Popek, G. J., Perspectives on optimistically replicated, peer-to-peer filing, Softw. Pract. Exper., 28, 2, 155-180 (1998)
[15] R.G. Guy, P.L. Reiher, D. Ratner, M. Gunter, W. Ma, G.J. Popek, Rumor: Mobile data access through optimistic peer-to-peer replication, in: Proceedings of the ER Workshop on Mobile Data Access, 1998, pp. 254-265; R.G. Guy, P.L. Reiher, D. Ratner, M. Gunter, W. Ma, G.J. Popek, Rumor: Mobile data access through optimistic peer-to-peer replication, in: Proceedings of the ER Workshop on Mobile Data Access, 1998, pp. 254-265
[16] B. Richard, D.M. Nioclais, D. Chalon, Clique: A transparent, peer-to-peer collaborative file sharing system, in: International Conference on Mobile Data Management (MDM), Melbourne, Australia, 2003; B. Richard, D.M. Nioclais, D. Chalon, Clique: A transparent, peer-to-peer collaborative file sharing system, in: International Conference on Mobile Data Management (MDM), Melbourne, Australia, 2003 · Zbl 1022.68705
[17] S. Balasubramaniam, B.C. Pierce, What is a file synchronizer?, in: Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom ’98), 1998; full version available as Indiana University CSCI technical report #507, April 1998; S. Balasubramaniam, B.C. Pierce, What is a file synchronizer?, in: Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom ’98), 1998; full version available as Indiana University CSCI technical report #507, April 1998
[18] Ramsey, N.; Csirmaz, E., An algebraic approach to file synchronization, (Proceedings of the 8th European Software Engineering Conference (2001), ACM Press), 175-185
[19] Roundy, D., The DARCS system (2004)
[20] N. Preguiça, M. Shapiro, C. Matheson, Efficient semantics-aware reconciliation for optimistic write sharing, Technical Report MSR-TR-2002-52, Microsoft Research, May 2002; N. Preguiça, M. Shapiro, C. Matheson, Efficient semantics-aware reconciliation for optimistic write sharing, Technical Report MSR-TR-2002-52, Microsoft Research, May 2002
[21] P. Molli, G. Oster, H. Skaf-Molli, A. Imine, Safe generic data synchronizer, Rapport de recherche, LORIA, France, May 2003; P. Molli, G. Oster, H. Skaf-Molli, A. Imine, Safe generic data synchronizer, Rapport de recherche, LORIA, France, May 2003
[22] A. Imine, P. Molli, G. Oster, M. Rusinowitch, Proving correctness of transformation functions in real-time groupware, in: ACM Conference on Computer Supported Cooperative Work (CSCW), Helsinki, Finland, 2003; A. Imine, P. Molli, G. Oster, M. Rusinowitch, Proving correctness of transformation functions in real-time groupware, in: ACM Conference on Computer Supported Cooperative Work (CSCW), Helsinki, Finland, 2003 · Zbl 1108.68389
[23] Ekenstam, T.; Matheny, C.; Reiher, P. L.; Popek, G. J., The Bengal database replication system, Distributed and Parallel Databases, 9, 3, 187-210 (2001) · Zbl 1010.68588
[24] P.L. Reiher, J.S. Heidemann, D. Ratner, G. Skinner, G.J. Popek, Resolving file conflicts in the ficus file system, in: USENIX Summer Conference Proceedings, 1994, pp. 183-195; P.L. Reiher, J.S. Heidemann, D. Ratner, G. Skinner, G.J. Popek, Resolving file conflicts in the ficus file system, in: USENIX Summer Conference Proceedings, 1994, pp. 183-195
[25] J.P. Munson, P. Dewan, A flexible object merging framework, in: ACM Conference on Computer Supported Cooperative Work (CSCW), Chapel Hill, North Carolina, 1994, pp. 231-242; J.P. Munson, P. Dewan, A flexible object merging framework, in: ACM Conference on Computer Supported Cooperative Work (CSCW), Chapel Hill, North Carolina, 1994, pp. 231-242
[26] Prakash, A.; Knister, M. J., A framework for undoing actions in collaborative systems, ACM Trans. Computer-Human Interaction, 1, 4, 295-330 (1994)
[27] Abowd, G. D.; Dix, A. J., Giving undo attention, Interacting with Computers, 4, 3, 317-342 (1992)
[28] Florescu, D.; Levy, A. Y.; Mendelzon, A. O., Database techniques for the world-wide web: A survey, ACM SIGMOD Record, 27, 3, 59-74 (1998)
[29] S. Abiteboul, Querying semi-structured data, in: International Conference on Database Theory (ICDT), Delphi, Greece, 1997, pp. 1-18; S. Abiteboul, Querying semi-structured data, in: International Conference on Database Theory (ICDT), Delphi, Greece, 1997, pp. 1-18
[30] Halevy, A. Y., Theory of answering queries using views, ACM SIGMOD Record, 29, 4, 40-47 (2000)
[31] I. Tatarinov, Z.G. Ives, A.Y. Halevy, D.S. Weld, Updating XML, in: ACM SIGMOD Symposium on Management of Data (SIGMOD), Santa Barbara, California, 2001; I. Tatarinov, Z.G. Ives, A.Y. Halevy, D.S. Weld, Updating XML, in: ACM SIGMOD Symposium on Management of Data (SIGMOD), Santa Barbara, California, 2001
[32] Rahm, E.; Bernstein, P. A., A survey of approaches to automatic schema matching, VLDB J., 10, 4, 334-350 (2001) · Zbl 1012.68909
[33] T. Milo, S. Zohar, Using schema matching to simplify heterogeneous data translation, in: International Conference on Very Large Data Bases (VLDB), New York, 1998; T. Milo, S. Zohar, Using schema matching to simplify heterogeneous data translation, in: International Conference on Very Large Data Bases (VLDB), New York, 1998
[34] C. Beeri, T. Milo, Schemas for integration and translation of structured and semi-structured data, in: International Conference on Database Theory (ICDT), Jerusalem, Israel, 1999; C. Beeri, T. Milo, Schemas for integration and translation of structured and semi-structured data, in: International Conference on Database Theory (ICDT), Jerusalem, Israel, 1999
[35] A. Doan, P. Domingos, A.Y. Halevy, Reconciling schemas of disparate data sources: A machine-learning approach, in: ACM SIGMOD Symposium on Management of Data (SIGMOD), Santa Barbara, California, 2001; A. Doan, P. Domingos, A.Y. Halevy, Reconciling schemas of disparate data sources: A machine-learning approach, in: ACM SIGMOD Symposium on Management of Data (SIGMOD), Santa Barbara, California, 2001
[36] J. Madhavan, P.A. Bernstein, E. Rahm, Generic schema matching with Cupid, in: International Conference on Very Large Data Bases (VLDB), Roma, Italy, 2001, pp. 49-58; J. Madhavan, P.A. Bernstein, E. Rahm, Generic schema matching with Cupid, in: International Conference on Very Large Data Bases (VLDB), Roma, Italy, 2001, pp. 49-58
[37] B.C. Pierce, J. Vouillon, What’s in Unison? A formal specification and reference implementation of a file synchronizer, Tech. Rep. MS-CIS-03-36, Dept. of Computer and Information Science, University of Pennsylvania, 2004; B.C. Pierce, J. Vouillon, What’s in Unison? A formal specification and reference implementation of a file synchronizer, Tech. Rep. MS-CIS-03-36, Dept. of Computer and Information Science, University of Pennsylvania, 2004 · Zbl 1087.68554
[38] A. Bohannon, J.A. Vaughan, B.C. Pierce, Relational lenses: A language for updatable views, in: Principles of Database Systems (PODS), 2006; extended version available as University of Pennsylvania technical report MS-CIS-05-27; A. Bohannon, J.A. Vaughan, B.C. Pierce, Relational lenses: A language for updatable views, in: Principles of Database Systems (PODS), 2006; extended version available as University of Pennsylvania technical report MS-CIS-05-27
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.