Fragments of relations

ABSTRACT

We develop a theory of relations that are constructed by the union and selection operations from fragment relations. Algorithms for inserting and deleting from relations that are composed of physical fragments are discussed, and we show when such insertions and deletions are meaningful. We also show how to find an access set for a relation, that is, a set of fragments sufficient to produce the relation, and we apply the test to the question of how the fragmentation of relations interacts with a query on the relation, showing that a selection on the relation can be implemented by retrieving a set of physical fragments that forms an access set for another particular relation.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: {CP} S. Ceri and G. Pelagatti. "Correctness of execution strategies of read-only transactions in distributed databases." Instituto di Elettrotecnica ed Elettronica Politecnico di Milano internal report 80-16.
• 3: {DB} U. Dayal and P. A. Bernstein, "The fragmentation problem: Lossless decomposition of relations into files." Computer Corporation of America TR CCA-78-13, November 1978.
• 4: Robert Epstein , Michael Stonebraker , Eugene Wong, Distributed query processing in a relational data base system, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509292]
• 5: {P} J. Paredaens. "Horizontal and vertical decompositions." Presented at XP1 Workshop on Relational Database Theory, Stony Brook, N.Y., June--July 1980.
• 6: J. B. Rothnie, Jr. , P. A. Bernstein , S. Fox , N. Goodman , M. Hammer , T. A. Landers , C. Reeve , D. W. Shipman , E. Wong, Introduction to a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.1-17, March 1980 [doi>10.1145/320128.320129]
• 7: {RG} J. B. Rothnie and N. Goodman. "An overview of the preliminary design of SDD-1: A system for distributed databases." Proc. 1977 Berkeley Workshop on Distributed Data Management and Computer Networks, May 1977, pages 39--57.