Page Numbers: No X: 530 Y: 10.5"
Columns: 1 Edge Margin: .6" Between Columns: .4"
Margins: Top: 1.3" Bottom: 1"
Line Numbers: No Modulus: 5 Page-relative

Design and Implementation of a
Relationship-Entity-Datum Data Model

R. G. G. Cattell

CSL-83-4 April 1983 [P83-00004]

c Copyright Xerox Corporation 1983. All rights reserved.

Abstract: The Model level of the Cypress Database Management System, built upon the earlier Cedar DBMS, provides data description and access capabilities at a higher level of abstraction than the existing system and other conventional DBMS’s. In this report we describe the design of the Cypress data model and discuss issues in the efficient implementation of such a model. Cypress incorporates features motivated by experience with local database applications. It may be viewed as an integration of a number of existing data models; we present the criteria that led to this choice. The Cypress primitives include simple data values such as strings or integers, entities representing real or abstract objects, and relationships among entities and/or simple data values. We also provide mechanisms for a hierarchy of types, relational keys, and segmentation of databases into independent files. Cypress allows a conventional relational query language. We argue that our extensions to simpler data models allow a more powerful and efficient implementation, and we describe the optimizations Cypress performs. We also discuss some preliminary experience with user tools and applications developed in conjunction with Cypress.

CR categories: H.2.1, H.2.2, H.4.1

Key words and phrases: Cedar, Cypress, database systems, semantic model, data model

XEROX

Xerox Corporation
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, California 94304


TABLE OF CONTENTS

1.Introduction𔁇

1.1Data modelling
1.2Cypress and Cedar
1.3Design criteria and motivation

2.Cypress data model concepts𔁋

2.1Data independence
2.2Basic primitives
2.3Names and keys
2.4Basic operations
2.5Aggregate operations
2.6Convenience operations
2.7Normalization
2.8Segments
2.9Augments
2.10Views
2.11Summary

3.Model level interface27

3.1Types
3.2Transactions and segments
3.3Data schema definition
3.4Basic operations
3.5Query operations
3.6System domains and relations
3.7Errors

4. Application example47

4.1A database application
4.2Schema design
4.3Example program

5. Data model design issues57

5.1Relations and attributes
5.2Entities and domains
5.3Entities as relationships
5.4Relationships as entities
5.5Lists and sets
5.6Entity names
5.7Keys, normalization, and dependencies
5.8Generalization and type hierarchies
5.9Access primitives
5.10Views, segments, and augments
5.11Summary



6.Data model implementation issues73

6.1Storage level structures
6.2Entities and relationships
6.3Values
6.4Caching the data schema
6.5Links and colocation
6.6Surrogate relations
6.7Basic operations
6.8Aggregate operations
6.9Summary

7.Database environment and applications87

7.1Database environment
7.2Database tools
7.3Database applications
7.4Summary

8.Status and conclusions101

8.1Summary
8.2Some results
8.3Status and plans
8.4Summary

9.Annotated bibliography105

10.Appendix and index113