The data structure

THE DATA STRUCTURE

C h e r l e s W. Bachman Honeywell Corporation

This

paper

is

an

edited

version

of

the

talk.

The

Data

Structure

Set Model

3

I t h i n k w e h a v e a d i s c u s s i o n t o d a y ; not a d e b a t e . Its r e a l p u r p o s e is to i n c r e a s e o u r u n d e r s t a n d i n g o f the b a s i c concepts underlying data basestructures and their models; to n o t e the s i m i l a r i t i e s and d i f f e r e n c e s b e t w e e n them, and to d e t e r m i n e t h e i r c o m p a t i b i l i t y o r the l a c k t h e r e o f . We are t a l k i n g a b o u t c o n c e p t s , n o t a b o u t i m p l e m e n t a t i o n s . T h e r e a s o n for all d a t a b a s e s t r u c t u r i n g is r e t r i e v a l : r e t r ie v a l for o u t p u t , r e t r i e v a l for d e c i s i o n - m a k i n g , ret r i e v a l for u p d a t i n g . To p i n p o i n t t h e o b j e c t o f r e t r i e v a l w e m u s t i n t e l l i g e n t l y s e l e c t t h e " r i g h t " d a t a -- the c o r r e c t s i n g l e r e c o r d , the c o r r e c t g r o u p o f r e c o r d s , and, in s o m e sense, t h e c o r r e c t s e q ue n c e o f r e c o r d s (in t h o s e s i t u a t i o n s w h e r e t h e s e q u e n c e in w h i c h t h e s e r e c o r d s a r e s e e n is i m p o r t a n t ) . For a c c u r a t e s e l e c t i o n , d e p e n d e n t on t h e particular interests, needs, and requirements of a given p e r s o n , w e w a n t a m e c h a n i s m for r e a d i l y d e f i n i n g r e c o r d s to beselected. W e w a n t a m e c h a n i s m t h a t w i l l p e r m i t the d a t a b a s e to e v o l v e as the e n t e r p r i s e and i n f o r m a t i o n s y s t e m s change. We want a mechanism which will protect already existing i n v e s t m e n t in p r o g r a m s and r e p o r t s p e c i f i c a t i o n s , w h i l e the d a t a b a s e e v o l v e s . We want a mechanism which p e r m i t sthe r e o p t i m i z a t i o n o f the s t r u c t u r e of s t o r e d d a t a as t h i n g s c h a n g e . T h e r e l a t i o n a l d e b a t e , as I see it, is o v e r s t y l e in ret r i e v a l l a n g u a g e s , and style, r e a l l y , is o n l y o n e a s p e c t of a data base system. T h e e n t i r e s y s t e m is m o s t l y c o n cerned with integrity, security, aspects ofevolvability, and c e r t a i n l y p e r f o r m a n c e , n o n e o f w h i c h is b e i n g d i s c u s s e d here today. T h e o n l y d e b a t a b l e i s s u e is " W h a t is the m o r e 'natural' v i e w ? " I a c c e p t the r e l a t i o n a l v i e w a n d the data-structure-set v i e w as b e i n g f u n d a m e n t a l l y c o m p a t i b l e as t h e y a r e a p p l i e d in p r a c t ic e , a n d I'd l i k e to d e m o n s t r a t e t h e e q u i v a l a n c e b e t w e e n t h e two v i e w s . J u s t b r i e f l y , a r e l a t i o n is a table, o r m a t r i x , of t u p l e s vs. a t t r i b u t e s . I'll u s e C h r i s D a t e ' s e x a m p l e s (Fig. i.i.i, p a g e 89). He t a l k e d a b o u t s u p p l i e r s , p a r t s , and p u r c h a s e o r d e r s as e x a mp l e s of r e l a t i o n s . In the r e a l w o r l d t h e r e are e n t i t i e s -- p e o p l e , rooms, m e e t i n g s , ideas, c o n c e p t s -and the p u r p o s e of an i n f o r m a t i o n s y s t e m ( w h e t h e r b a s e d on the r e l a t i o n a l or on the d a t a - s t r u c t u r e - s e t m o d e l ) is to c a p t u r e i n f o r m a t i o n a b o u t e n t i t i e s and mo d e l t h e m so t h e y c a n b e e x a m i n e d in the a b s t r a c t . These entities have c e r t a i n a t t r i b u t e s ; for e x a m p l e , a p e r s o n has a name, an age, a w e i g h t , t h i n g s like that. In the d a t a base, the e n t i t i e s are r e c o r d s , and the a t t r i b u t e s b e c o m e v a l u e s o f f i e l d s in the r e c o r d s . T h e r e l a t i o...