ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction.

Stephen J. Hegner: Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction. PODS 1988: 174-183
@inproceedings{DBLP:conf/pods/Hegner88,
  author    = {Stephen J. Hegner},
  title     = {Decomposition of Relational Schemata into Components Defined
               by Both Projection and Restriction},
  booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 21-23, 1988, Austin,
               Texas},
  publisher = {ACM},
  year      = {1988},
  isbn      = {0-89791-263-2},
  pages     = {174-183},
  ee        = {http://doi.acm.org/10.1145/308386.308434, db/conf/pods/Hegner88.html},
  crossref  = {DBLP:conf/pods/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A generalized approach to the decomposition of relational schemata is developed in which the component views may be defined using both restriction and projection operators, thus admitting both horizontal and vertical decompositions. The realization of restrictions is enabled through the use of a Boolean algebra of types, while true independence of projections is modelled by permitting null values in the base schema. The flavor of the approach is algebraic, with the collection of all candidate views of a decomposition modelled within a lattice-like framework, and the actual decompositions arising as Boolean subalgebras. Central to the framework is the notion of bidimensional join dependency, which generalizes the classical notion of join dependency by allowing the components of the join to be selected horizontally as well as vertically. Several properties of such dependencies are presented,including a generalization of many of the classical results known to be equivalent to schema acyclicity. Finally, a characterization of the nature of dependencies which participate in decompositions is presented. It is shown that there are two major types, the bidimensional join dependencies, which are tuple generating and allow tuple removal by implicit encoding of knowledge, and splitting dependencies, which simply partition the database into two components.

Copyright © 1988 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 21-23, 1988, Austin, Texas. ACM 1988, ISBN 0-89791-263-2
Contents BibTeX

Online Edition: ACM Digital Library

References

[AhBU79]
Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979) BibTeX
[AïNa86]
Hassan Aït-Kaci, Roger Nasr: Logic and Inheritance. POPL 1986: 219-228 BibTeX
[BaSp81a]
François Bancilhon, Nicolas Spyratos: Independent Components of Databases. VLDB 1981: 398-408 BibTeX
[BaSp81b]
François Bancilhon, Nicolas Spyratos: Update Semantics of Relational Views. ACM Trans. Database Syst. 6(4): 557-575(1981) BibTeX
[BeVa81]
...
[BFMY83]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX
[Birk67]
...
[Bisk81]
...
[BrMy86]
...
[ChMe87]
Edward P. F. Chan, Alberto O. Mendelzon: Independent and Separable Database Schemes. SIAM J. Comput. 16(5): 841-851(1987) BibTeX
[DGKG86]
David J. DeWitt, Robert H. Gerber, Goetz Graefe, Michael L. Heytens, Krishna B. Kumar, M. Muralikrishna: GAMMA - A High Performance Dataflow Database Machine. VLDB 1986: 228-237 BibTeX
[Fagi82]
Ronald Fagin: Horn clauses and database dependencies. J. ACM 29(4): 952-985(1982) BibTeX
[Gold81]
Billie S. Goldstein: Constraints on Null Values in Relational Databases. VLDB 1981: 101-110 BibTeX
[Grät78]
...
[GrYa84]
Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. J. Comput. Syst. Sci. 28(1): 121-141(1984) BibTeX
[Hegn83]
Stephen J. Hegner: Algebraic Aspects of Relational Database Decomposition. PODS 1983: 400-413 BibTeX
[Hegn84]
Stephen J. Hegner: Canonical View Update Support through Boolean Algebras of Components. PODS 1984: 163-173 BibTeX
[Hegn88]
...
[Kers86]
...
[Mai83]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[McMi79]
...
[Mink87]
...
[Ore42]
...
[Reit80]
Raymond Reiter: Equality and Domain Closure in First-Order Databases. J. ACM 27(2): 235-249(1980) BibTeX
[Reit84]
...
[Riss77]
Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX
[Scio80]
...
[Scio82]
Edward Sciore: A Complete Axiomatization of Full Join Dependencies. J. ACM 29(2): 373-393(1982) BibTeX
[Smit78]
John Miles Smith: A Normal Form for Abstract Syntax. VLDB 1978: 156-162 BibTeX
[Vard82]
Moshe Y. Vardi: On Decomposition of Relational Databases. FOCS 1982: 176-185 BibTeX

Referenced by

  1. Stephen J. Hegner: Pairwise-Definable Subdirect Decompositions of General Database Schemata. MFDBS 1991: 243-257
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:54 2009