Page Numbers: Yes X: 530 Y: 10.5" First Page: 105
Columns: 1 Edge Margin: .6" Between Columns: .4"
Margins: Top: 1.3" Bottom: 1"
Line Numbers: No Modulus: 5 Page-relative
Even Heading:
DESIGN AND IMPLEMENTATION OF A RELATIONSHIP-ENTITY-DATUM DATA MODEL
Odd Heading: Not-on-first-page
BIBLIOGRAPHY
9. Annotated bibliography
Abrial, J. R. Data Semantics, in Klimbie, J. and Koffman, K., Database Management, North-Holland, 1974.
Describes a data model based on binary relations. Relations that are N-ary even in functionally irreducible form must be represented by the introduction of artificial entities to represent relationships. See also Bracchi et al [1976] and Senko [1976] for binary relation models.
Armstrong, W. W. Dependency structures of data base relationships, Proceedings IFIP Congress, North-Holland, 1974.
This was one of the first studies of functional dependencies and relational normalization after Codd [1970]. LeDoux & Parker [1982] summarize more recent work.
Astrahan, M. M., et al. System R: Relational Approach to Database Management, ACM Transactions on Database Systems, 1, 2 (June 1976).
This is one of the most widely known and successful implementations of the relational data model. Much of the design of the original Cedar DBMS was derived from "RSS level" of this system.
Bachman, C. W. The Role Concept in Database Models, Proceedings 3rd International Conference on Very Large Databases, Tokyo, October 1977.
Concerned with behavioral properites of database objects, the treatment of entities in multiple roles, and integrating data models with programming languages. "Roles" for entities are actually more powerful than the sub-type hierarchy, although they are somewhat more complex.
Beeri, C., Bernstein, P. A., and Goodman, N. A Sophisticate’s Introduction to Database Normalization Theory, Proceedings 4th International Conference on Very Large Data Bases, West Berlin, West Germany, 1978.
A discussion of relational normalization.
Biller, H. On the notion of Irreducible Relations. Database Architecture, G. Bracchi and G. Nijssen, Eds. North-Holland, 1979.
Proposes a semantic definition of the irreducible relational form described in this paper. Contrasts the definition used in this paper with an earlier definition in terms of loss-less relational joins, showing our definition is more restrictive.
Bjorner, D. Formalization of Data Base Models. TR ID811, DCS, Tech. U. of Demark, Decemeber 1978.
The relational, hierarchical, and network models are sequentially formally defined. Both the data definition and data modification/query are considered.
Bobrow, D., and Goldstein, I. Representing Design Alternatives, Prooceedings of the Conference on Artificial Intelligence and the Simulation of Behavior, Amsterdam (July 1980). Also available as part of Xerox Palo Alto Research Center Report CSL-81-3.
A description of the layer concept in the PIE system. Layers are similar in concept to the augments discussed in this paper. However the basic data primitive is a Smalltalk object rather than relationships and entities, so the result does not provide the power of a database system, e.g. a query language. An implementation of layers was built, and feedback from that experience and the authors’ applications built on it were invaluable in the implementation of augments.
Bobrow, D. An Overview of KRL, a Knowledge Representation Language, Cognitive Science 1, 1, 1977.
Describes a knowledge representation language KRL, intended for artificial intelligence applications. Many of the ideas in knowledge representation languages, most of which are present in KRL, are now being incorporated in database models (see Wong & Mylopoulos [1977]). With an implementation of these ideas such as Cypress, the result is a system with much of the representational flexibility of knowledge representation languages without the database system features they normally lack: performance, shared access, persistent storage, or large quantities of data.
Bracchi, G., Paolini, P., and Pelagatti, G. Binary Logical Associations in Data Modelling, Proceedings IFIP TC-2 Working Conference on Modelling in Databa Base Management Systems, North-Holland, 1976.
Another discussion of binary relation models, similar to Abrial et al [1974]. Presents a number of arguments in favor of binary over N-ary relations, although these arguments are in reference to 3rd normal form rather than the irreducible form described in the present paper.
Brodie, M. L. Data types and databases, IFSM TR #37, University of Maryland, December 1978.
Relates data types and data models. We do not directly include this idea in Cypress, although relational views can be used to represent operations on object-oriented entity "data types", and the Squirrel interface is also oriented around the entity types. The paper references Brodie’s thesis on data types and other topics.
Brodie, M. L., and Zilles, S. N., Eds. Proceedings of Pingree Park Workshop on Data Abstraction, Databases, and Conceptual Modelling, SIGMOD Record 11, 2 (February 1981).
A collection of papers relating data modelling from the points of view of programming languages, artificial intelligence, and databases. The same concepts (e.g. hierarchies of types) have independently been studied in these three areas. The Pingree Park workshop provided a useful interchange of ideas.
Brown, M., Cattell, R., Suzuki, N. The Cedar Database Management System: A Preliminary Report, Proceedings ACM SIGMOD Conference 1981, Ann Arbor (April 1981).
An overview of the Cedar DBMS as it existed prior to the introduction of the Cypress data model, Squirrel tools, and Pilot and Alpine file systems.
Buneman, P., Frankel, R. FQL: A Functional Query Language, Proceedings of ACM SIGMOD International Conference on the Management of Data, Boston, (May) 1979.
A "functional" data model and query language (see also Shipman[1981]).
Cattell, R., Donahue, J., Haugelan, W., Maxwell, J. Integrating Database Applications in a Personal Computing Environment, submitted to IFIP Conference on High-Performance Personal Computers, (July) 1983.
This paper provides a more thorough discussion of the ideas behind integrating the database applications built on top of Cypress, using Squirrel.
Chan, A., Danberg, S., Fox, S., Lin, W., Nori, A., Ries, D. Storage and Access Structures to support a Semantic Data Model, Proceedings International Conference on Very Large Data Bases.
This is the only other implementation effort of which the author is aware under way to implement some of the features of recent semantic data models. The implementation is of an adaptation of DAPLEX to the programming language ADA (see Shipman [1981], Smith et al [1981]). Although the implementation was still under way at the time of this writing, the design includes a number of the ideas used in our implementation, e.g. clustering of data on the basis of entities. They do not maintain back-pointers to assist in updating entity references when data is moved or the entity is destroyed, instead using a level of indirection in an "entity directory".
Chen, P. The Entity-Relationship Model - Towards a Unified View of Data, ACM Transactions on Data Base Systems 1,1 (January 1976).
This was the earliest widely-referenced work on extensions to the relational model. It introduced entities and entity types (domains), and showed how they could be integrated with relationships, relations, and values.
Codd, E. F. A Relational Model of Data for Large Shared Data Banks, CACM 13, 6 (June 1970).
This was the earliest widely-referenced work defining the relational model. It introduced relationships, relations (relationship types), values, and value types.
Codd, E. F. Extending the Database Relational Model to Capture More Meaning, ACM Transactions on Data Base Systems 4,4 (December 1979).
Codd assembles several proposed extensions to the relational model. The biggest contribution of this paper is in recognizing that the operations on data are at least as important a component of the data model as the structural data definition, a fact most of the literature has ignored. Codd suggests such operations.
Demers, A., Donahue, J., and Skinner, G. Data Types as Values: Polymorphism, Type-checking, Encapsulation, Conference Record 5th ACM Symposium on Principles of Programming Languages, 1978.
Propose some more powerful mechanisms for types in programming languages. Russel, the authors’ language, supports these mechanisms (but is not yet implemented).
Fagin, R. Multivalued dependencies and a new normal form for relational databases. ACM Transactions on Database Systems 2, 3, 1977.
Fagin, R. A Normal Form for Relational Databases that is based on Domains and Keys. ACM Transactions on Database Systems 6, 3, 1981.
The above two papers by Fagin describe two normal forms for databases, the second more restrictive than the first, and the first more restrictive than Codd’s [1970].
Feldman, J., & Rovner, P. An Algol-based Associative Language, CACM 12, 8 (August) 1969.
The LEAP language described here has many of the properties of more recent data models, and some interesting language-integrated ideas about access to the data (looping constructs and user-defined procedures for matching tuples). LEAP uses binary relations.
Hall, P., Oulett, J., & Todd, S. Relations and Entities, Proceedings of the IFIP TC-2 Working Conference on Modelling in Data Base Management Systems, 1976.
An earlier discussion of entities and the irreducible relations which Biller [1979] further formalizes.
Hammer, M. & McLeod, D. The Semantic Data Model: A Modelling Mechanism for Data Base Applications, ACM Transactions on Database Systems 6, 3 (September) 1981.
A more recent summary of the SDM data model described in McLeod’s PhD disseration [1978].
Herot, C. The Spatial Data Management System. Proceedings International Conference on Very Large Data Bases, Rio de Janeiro, 1981.
Describes a novel user interface to a database system allowing browsing in a spatial layout of entities.
Israel, J., Mitchell, J., Sturgis, H. Separating Data from Function in a Distributed File System, Technical Report CSL-78-5, Xerox Palo Alto Research Center, 1978.
Describes Juniper, the transaction-based file system on which the Cedar DBMS was constructed.
Kapp, D., & Leben, J. IMS Programming Techniques, Van Nostrand, 1978.
Describes IBM’s IMS, the most widely used commercial database system, and it’s access language DL/I. IMS uses a form of hierarchical data model, and comes in a number of versions (IMS/VS, IMS360) with somewhat different features.
Katz, R. and Wong, E. Heterogenous Data Models - Part 1: Semantic Issues, ERL memo UCB/ERL m79/56, UC Berkeley, 1979.
Discusses issues in providing an integrated database system composing database system components based on different data models. This is a hard and generally unsolved problem.
Kent, W. Data and Reality, North-Holland, 1978.
This book has an excellent thorough discussion of philosophical and epistemological aspects of entities, entity types, relations, and issues only briefly mentioned in most recent data model literature. There are little or no new ideas here, the purpose is to revisit questions inadequately studied elsewhere, e.g. "What is an entity?".
Kent, W. Limitations of Record-based Information Models, ACM Transactions on Database Systems, 4,1 (March 1979).
A good summary of limitations of the relational model, and some of the advantages of more recent data models.
Kent, W. Choices in Practical Data Desgin, Proceedings 8th International Conference on Very Large Databases, Mexico City, (September) 1982.
Discusses some important unsolved issues in data modelling and schema design. One issue is whether an entity name composed of multiple parts or a relation with multiple attributes should be collapsed into a single name/attribute or kept separate (examples are month/day/year, or city/state/country). Another issue is is whether to encode information as type or as data (for example, whether to include sex as a property of persons, or to declare different subtypes of Person for men and women). Other issues are "nameless" entities and uniqueness of entity names when there are several subtypes of a domain.
Kent, W. The Entity Join, Proceedings 5th International Conference on Very Large Databases, 1979.
Discusses the distinction between entities and their names.
Kerschberg, L., Klug, A., Tsichritzis, D. A Taxonomy of Data Models, Systems for Large Data Bases, P. Lockemann & F. Neuhold (eds), North-Holland, 1976.
This paper is a brief survey of 23 data models along some global dimensions: graph-theoretic versus set-theoretic, mathematical foundation, terminology, and level of abstraction.
King, R., McLeod, D. Semantic Database Models, Database Design, S. B. Yao, Ed., 1982.
A recent survey of data models (see also Lochovsky & Tsichritzis [1982]).
LeDoux, C., and Parker, D. Reflections on Boyce-Codd Normal Form. Proceedings 8th International Conference on Very Large Data Bases, Mexico City, 1982.
A recent study of relational normalization.
Lindgreen, P. Basic operations on information as a basis for data base design, Proceedings IFIP Congress, North Holland, 1974.
A binary-relation data model.
McLeod, D. A Semantic Database Model and its Associated Structured User Interface, PhD Thesis, EE & CS, MIT, 1978.
Describes the SDM data model, including most of the ideas in the Cypress data model and some other ones, such as the introduction of events.
Mitchell, J., Maybury, W., Sweet, R. Mesa Language Manual. Xerox Palo Alto Research Center Report CSL-79-3, 1979
Describes Mesa 5.0, the language in which the Cedar database system was originally implemented. No reference is externally available at the time of this writing for Cedar Mesa, the language in which the Cypress database system is implemented. The Cedar Mesa language of course strongly influenced the design of the programmer’s interface to the Cypress data model.
Mylopoulos, J., Bernstein, P., and Wong, H. A Preliminary Specification of TAXIS: A Language for Designing Information Systems, TR CCA-78-02 (January 1978).
Integrates a number of the concepts discussed in recent data models, including generalization hierarchies and specialization.
Pirotte, A. "The Entity-Property-Association Model: An Information-Oriented Data Base Model", MBLE Report R343, (March) 1977.
Another early data model.
Quillian, M. R. Semantic Memory, in M. Minsky, (ed.), Semantic Information Processing, MIT Press, 1968.
This is the earliest widely-referenced work with semantic nets, which have been used widely in Artificial Intelligence. Semantic nets, as they are generally used, allow entities and relationships but lacked some capabilities the relational model allows (e.g. queries on relations).
Redell, D, et al. Pilot: An Operating System for a Personal Computer, Proceedings 7th Symposium on Operating Systems Principles, Asilomar, (ACM order #534790) 1979.
Describes the Pilot operating system, on which the Cedar programming environment and Cedar DBMS depend. The Pilot file system provides a local transaction-based access to data for the Cedar DBMS (Juniper, described by Israel et al [1979], provides a remote transaction-based file system).
Rissanen, J. Independent Components of Relations, ACM TODS 2, 4 (December) 1977.
A study of what Biller [1979] calls a-irreducible relational form, which is less restrictive than the irreducible form we use.
Roussopoulos, N., and Mylopoulos, J. Using Semantic Networks for Database Management, Proceedings 2nd International Conference on Very Large Databases, September 1975.
Discusses a data model based on semantic networks (Quillian [1968]).
Sadri, F., Ullman, J. The Interaction between Functional Dependencies and Template Dependencies. Proceedings ACM SIGMOD Conference 1980, Santa Monica.
Describes more complex kinds of dependencies and relational normal forms.
Schmidt, H. A., & Swenson, J. R. On the Semantics of the Relational Data Model, in King, F. (ed.), Proceedings ACM SIGMOD Conference, San Jose, 1975.
An early paper discussing shortcomings of the relational model.
Senko, M. E. Data Structures and Data Accessing in Data Base Systems Past, Present, Future, IBM Systems Journal 16, 3 (1977a).
A binary-relation data model with separate physical, conceptual, and user levels.
Shipman, D. W. The Functional Data Model and the Data Language DAPLEX, ACM Transactions on Database Systems 6, 1 (March) 1981.
Describes a data model, the functional data model, which is superficially quite different but actually very similar to the Cypress model. The Functional data model takes an attractively simple point of view, decomposing relationships into functions mapping values to values. Thus all the notation and terminology of mathematical functional notation is available for use. The "properties" described in this paper have some similarities to this idea, but Shipman makes this the basis for the model.
Shoshani, A. CABLE: A Language Based on the Entity-Relationship Model, Lawrence Berkeley Lab, Berkeley, California, 1978.
CABLE is a query language for Chen’s Entity-Relationship model, based on chains of relationships between entities. For example, one might ask for all the people that are managers of departments that produce parts that are sold to Company X. Because the chains seem very natural for expression of queries, we are considering a similar kind of language for use in Cypress.
Smith, J.M., and Smith, D.C. Data Base Abstractions: Aggregation and Generalization, ACM Transactions on Database Systems 2, 2 (June) 1977a.
A discussion of the idea of hierarchies of types.
Smith, J.M., and Smith, D.C. Integrated Specifications for Abstract Systems, TR UUCS-77-112, Computer Science, University of Utah, September 1977b.
Concerned with combining structural and behavioral specifications.
Smith, J., Fox, S., Landers, T. Reference Manual for ADAPLEX, Technical Report, Computer Corporation of America, January 1981.
Describes ADAPLEX, embedding the DAPLEX (Shipman[1981]) language in the Ada programming language.
Stonebraker, M., et al. The Design and Implementation of INGRES, ACM Transaction on Database Systems 2, 3 (September 1976).
INGRES is one of the two most widely known implementations of the relational data model (the other is System R, Astrahan et al [1976]).
Stonebraker, M. Hypothetical Databases as Views, ACM Proceedings ACM SIGMOD 81, Ann Arbor (April 1981).
Further work on INGRES referenced above has suggested ways to define integrity constraints and hypothetical databases through the use of views, although there may be problems with doing this as an "add-on". Hypothetical databases are described in this reference.
Sundgren, B. Conceptual foundation of the infological approach to data bases, Data Base Management, J. Klimbie and K Koffeman, Eds, North Holland, 1974.
Early paper describing the infological data model, which has not been fleshed out to the degree of most of the other models discussed. The basic primitives are objects (entities) and their properties.
Tsichritzis, D.C. LSL - A link and selector language, Proceedings ACM SIGMOD 76, 1976.
A query language for a network model database.
Tsichritzis, D., and Klug, A. (Eds). The ANSI/X3/SPARC DBMS Framework. Report of the Study Group on Database Management Systems. Information Systems 3, 4 (1978).
A comprehensive data model in the Entity-Relationship family.
Tsichritzis, D., and Lochovsky, F. Data Models, Prentice-Hall, 1982.
This book is probably the most extensive and up-to-date discussion of data models currently available. It deals with conceptual models rather than physical models and complete systems, since many of the models described have not been implemented. The book covers the relational, network, hierarchical, entity-relationship, binary, semantic network, and infological data models.
Wiederhold, G. Database Design, McGraw-Hill, New York, 1977.
A good description of database systems from the point of view of implementation and physical access structures as opposed to the conceptual data model.
Wiederhold, G., El-Masri, R. The Structural Model for Database Design, Proceedings of the International Conference on the Entity-Relationship Approach to Systems Analysis and Design, Los Angeles, (December) 1979.
Describes the "structural" data model, further described in El-Masri’s PhD dissertation. The structural model classifies relations according to their semantic use, much as in Codd’s [1980] extensions of the relational model.
Wong, H., and Mylopoulos, J. Two Views of Data Semantics: A Survey of Data Models in Artificial Intelligence and Database Management. INFOR 15, 3 (October 1977).
Contrasts knowledge representation languages and data models.
Zloof, M. M. Query by Example: The Invocation and Definition of Tables and Forms. Proceedings First International Conference on Very Large Data Bases, 1975.
The first widely-referenced work on querying databases by filling out forms, an idea used in Squirrel queryer windows.