Separability - An Approach to Physical Data Base Design.

Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Separability - An Approach to Physical Data Base Design. VLDB 1981: 320-332
  author    = {Kyu-Young Whang and
               Gio Wiederhold and
               Daniel Sagalowicz},
  title     = {Separability - An Approach to Physical Data Base Design},
  booktitle = {Very Large Data Bases, 7th International Conference, September
               9-11, 1981, Cannes, France, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1981},
  pages     = {320-332},
  ee        = {db/conf/vldb/WhangWS81.html},
  crossref  = {DBLP:conf/vldb/81},
  bibsource = {DBLP,}


A theoretical approach to the optimal design of a large multifile physical databases is presented. The design algorithm is based on the theory that given a set of join methods that satisfy a certain property called separability, the problem of optimal assignment of access structures to the whole database can be reduced to the subproblem of optimizing individual relations independently of one another. Coupling factors are defined to represent all the interactions among the relations. This approach not only reduces the complexity of the problem significantly, but also provides a better understanding of underlying mechanisms.

Copyright © 1981 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents BibTeX


[BAT 80]
Don S. Batory, C. C. Gotlieb: A Unifying Model of Physical Databases. ACM Trans. Database Syst. 7(4): 509-539(1982) BibTeX
[BAY 72]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[BLA 76]
[CAR 75]
Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) BibTeX
[ELM 80]
[GAM 77]
Thomas J. Gambino, Rob Gerritsen: A Data Base Design Decision Support System. VLDB 1977: 534-544 BibTeX
[GOT 75]
Leo R. Gotlieb: Computing Joins of Relations. SIGMOD Conference 1975: 55-63 BibTeX
[HAM 76]
Michael Hammer, Arvola Chan: Index Selection in a Self-Adaptive Data Base Management System. SIGMOD Conference 1976: 1-8 BibTeX
[HSI 70]
[KAT 80]
Randy H. Katz, Eugene Wong: An Access Path Model for Physical Database Design. SIGMOD Conference 1980: 22-29 BibTeX
[KIN 74]
[KNU 73]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
[PEC 75]
Robert M. Pecherer: Efficient Evaluation of Expressions in a Relational Algebra. ACM Pacific 1975: 44-49 BibTeX
[SCH 75]
Mario Schkolnick: The Optimal Selection of Secondary Indices for Files. Inf. Syst. 1(4): 141-146(1975) BibTeX
[SEL 79]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[SEV 75]
Dennis G. Severance: A Parametric Model of Alternative File Structures. Inf. Syst. 1(2): 51-55(1975) BibTeX
[SMI 75]
John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) BibTeX
[WHA 81]
[WIE 77]
[WIE 79]
Gio Wiederhold, Ramez Elmasri: The Structural Model for Database Design. ER 1979: 237-258 BibTeX
[WON 76]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[YAO 77]
S. Bing Yao: An Attribute Based Model for Database Access Cost Analysis. ACM Trans. Database Syst. 2(1): 45-67(1977) BibTeX
[Yao 79]
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) BibTeX

Referenced by

  1. Martin R. Frank, Edward Omiecinski, Shamkant B. Navathe: Adaptive and Automated Index Selection in RDBMS. EDBT 1992: 277-292
  2. Elena Barcucci, Alessandra Chiuderi, Renzo Pinzani, M. Cecilia Verri: Index Selection in Relational Databases. MFDBS 1989: 24-36
  3. Pasquale Rullo, Domenico Saccà, Qinsi Zhong: An Approximation Algorithm for the Physical Access Path Selection in the CODASYL Environment. ICDE 1986: 200-207
  4. Mario Schkolnick, Paolo Tiberio: Estimating the Cost of Updates in a Relational Database. ACM Trans. Database Syst. 10(2): 163-179(1985)
  5. Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Physical Design of Network Model Databases Using the Property of Separability. VLDB 1982: 98-107
  6. Arnon Rosenthal, David S. Reiner: An Architecture for Query Optimization. SIGMOD Conference 1982: 246-255
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:13 2009