The Complexity of Operations on a Fragmented Relation.

Carlo Meghini, Costantino Thanos: The Complexity of Operations on a Fragmented Relation. ACM Trans. Database Syst. 16(1): 56-87(1991)

@article{DBLP:journals/tods/MeghiniT91,
  author    = {Carlo Meghini and
               Costantino Thanos},
  title     = {The Complexity of Operations on a Fragmented Relation},
  journal   = {ACM Trans. Database Syst.},
  volume    = {16},
  number    = {1},
  year      = {1991},
  pages     = {56-87},
  ee        = {http://doi.acm.org/10.1145/103140.103143, db/journals/tods/MeghiniT91.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Data fragmentation is an important aspect of distributed database design, in which portions of relations, tailored to the specific needs of local applications, are defined to be further allocated to the sites of the computer network supporting the database system. In this paper we present a theory of fragmentation with overlapping fragments to study the complexity of the problems involved in checking the completeness of a fragmentation schema and in querying and updating a fragmented relation. We analyze these problems from the complexity viewpoint and present sound and complete algorithms for their solution.

Copyright © 1991 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" 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/An3-2 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" 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/aDVD2 or /dvd

BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 2083 KB]

References

[1]: Elisa Bertino, Carlo Meghini, Costantino Thanos: The Update Problem in the Distributed Database System Hermes/1. ICOD 1983: 317-331 BibTeX
[2]: Stefano Ceri, Giuseppe Pelagatti: Correctness of Query Execution Strategies in Distributed Databases. ACM Trans. Database Syst. 8(4): 577-607(1983) BibTeX
[3]: Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX
[4]: E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[5]: 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
BibTeX
[6]: ...
[7]: David Maier, Jeffrey D. Ullman: Fragments of Relations. SIGMOD Conference 1983: 15-22 BibTeX
[8]: Carlo Meghini, Costantino Thanos: Querying Fragmented Relations in a Distributed Database. Acta Inf. 22(2): 125-138(1985) BibTeX
[9]: James B. Rothnie Jr., Philip A. Bernstein, Stephen Fox, Nathan Goodman, Michael Hammer, T. A. Landers, Christopher L. Reeve, David W. Shipman, Eugene Wong: Introduction to a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 1-17(1980) BibTeX
[10]: Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

Referenced by

Sha Guo, Wei Sun, Mark Allen Weiss: Solving Satisfiability and Implication Problems in Database Systems. ACM Trans. Database Syst. 21(2): 270-293(1996)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]