Grouping Techniques for Update Propagation in Intermittently Connected Databases.

Sameer Mahajan, Michael J. Donahoo, Shamkant B. Navathe, Mostafa H. Ammar, Sanjoy Malik: Grouping Techniques for Update Propagation in Intermittently Connected Databases. ICDE 1998: 46-53

@inproceedings{DBLP:conf/icde/MahajanDNAM98,
  author    = {Sameer Mahajan and
               Michael J. Donahoo and
               Shamkant B. Navathe and
               Mostafa H. Ammar and
               Sanjoy Malik},
  title     = {Grouping Techniques for Update Propagation in Intermittently
               Connected Databases},
  booktitle = {Proceedings of the Fourteenth International Conference on Data
               Engineering, February 23-27, 1998, Orlando, Florida, USA},
  publisher = {IEEE Computer Society},
  year      = {1998},
  isbn      = {0-8186-8289-2},
  pages     = {46-53},
  ee        = {db/conf/icde/MahajanDNAM98.html},
  crossref  = {DBLP:conf/icde/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We consider an environment where one or more servers carry databases that are of interest to a community of clients. The clients are only intermittently connected to the server for brief periods of time. Clients carry a part of the database for their own processing and accumulate local updates while disconnected. We call this the Intermittently Connected Database (ICDB) environment. ICDBs have a wide variety of applications including sales force automation, insurance claim processing, and mobile work forces. Our focus in the paper is on the problem of update propagation at the server in ICDBs and the associated processing at the clients. The typical client-centric approach involves the communication and processing of updates and transactions on a per-client basis, ignoring the overlap of data between clients. The complexity of this approach is on the order of the number of connecting clients, thereby limiting the scalability of the server. We propose a data-centric approach which clusters data into groups and assigns to each client one or more of these groups. The proposed scheme results in server processing complexity on the order of the number of groups, which we control. We propose various techniques for grouping and discuss the processing required at the clients to enable the grouping approach. While the client-centric approach is expected to significantly degrade with the increasing number of clients, we expect that a properly designed grouping scheme will sustain a number of clients that is significantly larger. A prototype has been developed and performance studies are currently in progress.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 7, ICDE 1996-1998, PDIS, Hypertext, ACL DL" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An2-7 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Proceedings of the Fourteenth International Conference on Data Engineering, February 23-27, 1998, Orlando, Florida, USA. IEEE Computer Society 1998, ISBN 0-8186-8289-2
Contents

References

[1]: ...
[2]: James J. Kistler, Mahadev Satyanarayanan: Disconnected Operation in the Coda File System. ACM Trans. Comput. Syst. 10(1): 3-25(1992)
[3]: Lily B. Mummert, Maria Ebling, Mahadev Satyanarayanan: Exploiting Weak Connectivity for Mobile File Access. SOSP 1995: 143-155
[4]: ...
[5]: Stephen E. Deering, David R. Cheriton: Multicast Routing in Datagram Internetworks and Extended LANs. ACM Trans. Comput. Syst. 8(2): 85-110(1990)
[6]: ...
[7]: Gary E. Herman, Gita Gopal, K. C. Lee, Abel Weinrib: The Datacycle Architecture for Very High Throughput Database Systems. SIGMOD Conference 1987: 97-103
[8]: Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)
[9]: Stefano Ceri, Jennifer Widom: Deriving Production Rules for Incremental View Maintenance. VLDB 1991: 577-589
[10]: Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339
[11]: Ashish Gupta, H. V. Jagadish, Inderpal Singh Mumick: Data Integration using Self-Maintainable Views. EDBT 1996: 140-144
[12]: Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166
[13]: John V. Harrison, Suzanne W. Dietrich: Maintenance of Materialized Views in a Deductive Database: An Update Propagation Approach. Workshop on Deductive Databases, JICSLP 1992: 56-65
[14]: Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104
[15]: Bernhard Mitschang, Hamid Pirahesh, Peter Pistor, Bruce G. Lindsay, Norbert Südkamp: SQL/XNF - Processing Composite Objects as Abstractions over Relational Data. ICDE 1993: 272-282
[16]: Xiaolei Qian, Gio Wiederhold: Incremental Recomputation of Active Relational Expressions. IEEE Trans. Knowl. Data Eng. 3(3): 337-341(1991)
[17]: Michel E. Adiba, Bruce G. Lindsay: Database Snapshots. VLDB 1980: 86-91
[18]: Bruce G. Lindsay, Laura M. Haas, C. Mohan, Hamid Pirahesh, Paul F. Wilms: A Snapshot Differential Refresh Algorithm. SIGMOD Conference 1986: 53-60
[19]: José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71
[20]: Susan Horwitz, Tim Teitelbaum: Generating Editing Environments Based on Relations and Attributes. ACM Trans. Program. Lang. Syst. 8(4): 577-608(1986)
[21]: Eric N. Hanson: A Performance Analysis of View Materialization Strategies. SIGMOD Conference 1987: 440-453
[22]: Nick Roussopoulos, Hyunchul Kang: Principles and Techniques in the Design of ADMS±. IEEE Computer 19(12): 19-25(1986)
[23]: H. V. Jagadish, Inderpal Singh Mumick, Abraham Silberschatz: View Maintenance Issues for the Chronicle Data Model. PODS 1995: 113-124
[24]: Arie Segev, Weiping Fang: Currency-Based Updates to Distributed Materialized Views. ICDE 1990: 512-520
[25]: Arie Segev, Jooseok Park: Updating Distributed Materialized Views. IEEE Trans. Knowl. Data Eng. 1(2): 173-184(1989)
[26]: ...
[27]: J. W. Wong, Mostafa H. Ammar: Analysis of Broadcast Delivery in a Videotex System. IEEE Trans. Computers 34(9): 863-866(1985)
[28]: Swarup Acharya, Michael J. Franklin, Stanley B. Zdonik: Disseminating Updates on Broadcast Disks. VLDB 1996: 354-365
[29]: M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
[30]: ...
[31]: Carlo Batini, Maurizio Lenzerini, Shamkant B. Navathe: A Comparative Analysis of Methodologies for Database Schema Integration. ACM Comput. Surv. 18(4): 323-364(1986)
[32]: ...