Fact-Based Data Analysis and Design

1 INTRODUCTION

By focusing on the facts to be maintained in a database, we obtain a methodology for data analysis and design which is at once simpler and more powerful than other methodologies.

The methodology is made simple by:

• Shifting our focus from entities to facts about entities, i.e., relationships.
• Using a simplified form of entity-relationship model.
• Deferring problems of identification and representation until late in the process.

In addition, we provide extended capabilities to deal with more difficult representation situations, and to examine alternative data designs.

We focus on the middle portion of the analysis and design process: translating entities and relationships into record designs. This paper does not describe procedures for identifying the entities and relationships, nor does it deal with physical data design.

We go a little beyond what might ordinarily be considered "logical data design". While this methodology can produce records in third or even fifth normal forms [K4], our aim is to produce the actual record designs that will be implemented in a database, even if they might be inelegant or redundant in some ways. What we do not deal with are the other aspects of resource and access path management, such as storage mappings and index schemes.

We deal only with flat files. The methodology applies to relational databases, to other "flat file" data management systems, and to the design of the segment types in a hierarchical database or the record types in a network database. Non-flat data models (e.g., hierarchies and networks) will require additional design steps to replace some fields with structural paths (pointers).

The methodology has not yet been developed to the point of a detailed procedure. This paper describes the concepts on which the methodology is based, and the major steps in the methodology.

The first step is to identify the facts that are to be maintained, in terms of entities and relationships. Thereafter, the methodology essentially

• Collects all single-valued facts about the same thing into one record.
• Provides a separate record for each many-to-many relationship, including all single-valued facts about the relationship.

These two results are accomplished together, in the following steps:

• Generate a "pseudo-record" for each fact.
• Identify "pseudo-keys" for each pseudo-record.
• Merge pseudo-records having compatible keys.

Other steps in the methodology include:

• Assign representations.
• Consider alternative designs.
• Name the fields and the record types.

While the approach is fundamentally simpler than others, it sometimes appears more elaborate because it deals with more complex and realistic situations, including:

• Imperfect identifiers, including multi-field and embedded representations.
• N-ary relationships.
• Multi-valued attributes, attributes of relationships, and attributes of attributes.
• Entity subtypes.
• Partial relationships (i.e., optional, not required for all occurrences of an entity type).
• Variations in record format to accommodate data processing requirements, e.g., denormalization.

In the following sections, we will:

• Begin with a simple example.
• Concisely describe the steps of the methodology.
• Develop some background concepts.
• Explain the methodology in greater detail.

1.1 Introductory Example

1.1.1 Specify the Facts to be Maintained

The facts:

• Employees have employee numbers (1:1).
• Employees have names (n:1).
• Departments have department numbers (1:1).
• Departments have names (n:1).
• Employees are assigned to departments (n:1).
• Employees earn money (n:1).
• Employees manage departments (1:1).

We present the same facts in diagram form:

has-emp# has-name has-dept# has-name ........ ........ ......... ........ : : : : : : : : EMP EMP# EMP NAME DEPT DEPT# DEPT NAME assigned earns manages ........ ....... ....... : : : : : : EMP DEPT EMP MONEY EMP DEPT

1.1.2 Generate a "Pseudo-Record" For Each Fact

has-emp# has-name has-dept# has-name ........ ........ ......... ........ : : : : : : : : -------------- -------------- ---------------- --------------- | EMP | EMP# | | EMP | NAME | | DEPT | DEPT# | | DEPT | NAME | -------------- -------------- ---------------- --------------- 1 2 3 4 5 6 7 8 assigned earns manages ........ ....... ....... : : : : : : -------------- --------------- -------------- | EMP | DEPT | | EMP | MONEY | | EMP | DEPT | -------------- --------------- -------------- 9 10 11 12 13 14

Representations will be dealt with in a general way at a later step. But when some of the facts serve to assign obvious unique identifiers to things, then we can take a shortcut at this point by replacing such things with their identifiers. We do this now for employees and departments:

has-name has-name ........ ........ : : : : --------------- ---------------- | EMP# | NAME | | DEPT# | NAME | --------------- ---------------- 3 4 7 8 assigned earns manages ........ ....... ....... : : : : : : ---------------- ---------------- ---------------- | EMP# | DEPT# | | EMP# | MONEY | | EMP# | DEPT# | ---------------- ---------------- ---------------- 9 10 11 12 13 14

1.1.3 Identify "Pseudo-Keys" For Each Pseudo-Record

The concept: if we merely assume that each of these "fields" actually contains a unique identifier, then what would be the keys in each pseudo-record?

We use "====" to indicate the pseudo-keys.

has-name has-name ........ ........ : : : : --------------- ---------------- | EMP# | NAME | | DEPT# | NAME | --====--------- --=====--------- 3 4 7 8 assigned earns manages ........ ....... ....... : : : : : : ---------------- ---------------- ---------------- | EMP# | DEPT# | | EMP# | MONEY | | EMP# | DEPT# | --====---------- --====---------- --====---=====-- 9 10 11 12 13 14

1.1.4 Merge Pseudo-Records Having Compatible Keys

For this example, key fields involving the same entity types are compatible. Merging all the pseudo-records having EMP# as the key yields:

manages ..................................... : : : earns : : ........................... : : : : : : : assigned : : : : ................. : : : : : : : : : : : has-name : : : : : : ........ : : : : : : : : : : : --------------------------------- - - - - | EMP# | NAME | DEPT# | MONEY | DEPT# | --======------------------------- - - - - 3 9 11(13) 4 10 12 (14)

Merging all the pseudo-records having DEPT# as the key yields:

manages ................ : : : has-name : : ........ : : : : : ----------------------- | DEPT# | NAME | EMP# | --=====----------====-- 7 14 8 13

1.1.5 Assign Representations

In the general case, some restructuring could occur at this point to deal with representation problems. In the present simple example, however, we observe that all fields except MONEY (12) already contain character strings that can serve as representations in the data. All that remains here is to specify a representation for field (12). We assume here that it will be expressed in dollars, in integers.

earns ........................... : : : assigned : : ................. : : : : : : : has-name : : : : ........ : : : : : : : : --------------------------------- | EMP# | NAME | DEPT# | MONEY | --======------------------------- 3 9 11 4 10 12 Representations: EMP# NAME DEPT# INTGR-DLR manages ................ : : : has-name : : ........ : : : : : ----------------------- | DEPT# | NAME | EMP# | --=====----------====-- 7 14 8 13 Representations: DEPT# NAME EMP#

1.1.6 Name the Fields and the Record Types

---------------------------------- "EMPLOYEE RECORD": | EMPNUM | ENAME | DEPT | SALARY | --======-------------------------- 3 9 11 4 10 12 Representations: EMP# NAME DEPT# INTGR-DLR ------------------------- "DEPARTMENT RECORD": | DEPTNUM | DNAME | MGR | --=======-----------===-- 7 14 8 13 Representations: DEPT# NAME EMP#

1.1.7 Consider Alternatives

This step would actually precede the prior one, since there is little point in naming fields until the final field configuration is chosen. However, it is easier to illustrate the design alternatives using the unique and mnemonic field names we just chose.

We show a number of alternative record designs which could be considered for representing the same set of facts:

1. The current design:

-------------------------- ------------------- |EMPNUM|ENAME|DEPT|SALARY| |DEPTNUM|DNAME|MGR| -======------------------- -=======-------===-

2. Subdivide the employee name field:

----------------------------------- ------------------- |EMPNUM|FIRST|MID|LAST|DEPT|SALARY| |DEPTNUM|DNAME|MGR| -======---------------------------- -=======-------===-

3. Keep the "manages" fact in the employee record, i.e., identify the department which the employee manages (possibly none):

----------------------------------- --------------- |EMPNUM|ENAME|DEPT|SALARY|MGS-DEPT| |DEPTNUM|DNAME| -======-------------------========- -=======-------

MGS-DEPT contains a department number or a blank. This design alternative is only valid if all departments have managers, or null values are permitted in the EMPNUM key field.

4. Put all the department information into the record of the department's manager, eliminating the separate department record (subject to the same restriction):

----------------------------------------- |EMPNUM|ENAME|DEPT|SALARY|MGS-DEPT|DNAME| -======-------------------========-------

5. If we have the additional constraint that a manager belongs to the department he manages, then the "manages" fact could be kept by a simple flag in the employee record:

----------------------------------- --------------- |EMPNUM|ENAME|DEPT|SALARY|MGR-FLAG| |DEPTNUM|DNAME| -======---------------------------- -=======-------

MGR-FLAG is a simple binary flag indicating whether the employee manages his department.

6. We could create a separate record type for employees of each department, eliminating the need for a DEPT field:

--------------------- ------------------- D01 EMPLOYEES: |EMPNUM|ENAME|SALARY| |DEPTNUM|DNAME|MGR| -======-------------- -=======-------===- --------------------- D02 EMPLOYEES: |EMPNUM|ENAME|SALARY| -======--------------
.
.
.

1.2 A Skeleton of the Methodology

Subsequent descriptions of the methodology will be interspersed with definitions and explanations of background concepts, perhaps making it appear more elaborate then it really is. We present here a complete skeleton of the methodology, without benefit of definitions or explanations, to keep its overall extent in perspective.

• Specify the facts to be maintained, in terms of relationships among entities.
  • For each fact, specify:

    A fact identifier (arbitrary).

    The relationship name, or sequence of composed relationships.

    The entity type occurring in each role, if more restrictive than that defined for the relationship.

    Least and most participations, if more restrictive than in the relationship definitions.

  • For each relationship, specify:

    Relationship name.

    Degree (number of roles).

    Role names.

    The entity types permitted in each role.

    Least and most participation for each role, and also for selected sequences of roles.

  • For each entity type, specify:

    Entity type name.

    Whether it is a subtype of another entity type.

    Whether it is a symbol type and, if so, whether it is structured.

• Generate a "pseudo-record" for each fact.

  Representations may optionally be assigned at this point.

• Identify "pseudo-keys" for each pseudo-record.
• Optionally merge pseudo-records having compatible keys.
  • Merge on compatible keys having the same population.
  • Merge on compatible keys having different populations if null values are acceptable in other fields.
  • Merge on subtypes of a common supertype.
• Assign representations.
  • For each field in a pseudo-record:

    If the entity type in the field is itself a structured symbol type, replace by multiple fields, and exit.

    If the entity type is a simple symbol type, leave it alone, and exit.

    If the entity type needs no representation, delete the field, and exit.

    If the representation is derivable from another field (including indirect representation), delete this field, and exit.

    Find a set of facts whose combination provides a representation having the required qualities of completeness, uniqueness, and/or singularity (as well as other qualities). Introduce new facts if needed.

    If several suitable sets of facts are available, choose one.

    "Import" such facts into the record, if not already there.

    Delete the field.

    Repeat the assignment of representations for any imported facts.

  • Compress fields, if desired.
  • Re-merge if needed to eliminate redundancies.
• Consider alternative designs.
• Name the fields and the record types.

2 THE UNDERLYING IDEAS

2.1 Facts

We have used the term "fact" to mean something like "employees are assigned to departments". Strictly speaking, we should use a term like "fact type" or "fact pattern" here, and reserve the term "fact" for a specific item of information, such as "Joe Smith is assigned to the Sales department". However, wherever the intent is clear, we will continue to use the term "fact" in the broader sense.

A data record usually contains a number of facts, such as an employee's department, salary, etc. In our approach to data analysis, we first identify the facts to be maintained, then aggregate them into data records.

Most methodologies suggest that data represents two kinds of facts: facts about things (attributes) and facts that connect things (relationships). Facts about an employee might include his salary, department, birthdate, and birthplace. Connecting facts might connect an employee to a project, or to his/her spouse.

If you're paying attention, you should be confused at this point. How did we decide that an employee's department was a fact about the employee, rather than a fact connecting two things? Why did we also decide that about his birthplace? I don't know the answer to that, and I don't think anyone else can give you a really effective answer either.

2.1.1 Facts Connect Things

We can avoid the question altogether by treating all facts as connections between things. This may seem surprising at first, and it does take a bit of getting used to. But it simplifies things. Why shouldn't we think of some money as a thing, with the salary fact connecting that thing to an employee? We can just as easily think of dates or distances as things; then birthdays and heights become facts connecting such things to employees. Later on we shall see that identifiers can also be treated in the same way.

----- earns -------------- | |----------->| money | | | -------------- | | assigned -------------- | |----------->| department | | | -------------- | | born on -------------- | e |----------->| date | | m | -------------- | p | born at -------------- | l |----------->| place | | o | -------------- | y | works on -------------- | e |----------->| project | | e | -------------- | | married to -------------- | |----------->| person | | | -------------- | | height -------------- | |----------->| distance | ----- --------------

We seem to have the idea in mind already, in some of the ways we talk about things. When we say that "6 feet" and "72 inches" mean "the same thing", what do we mean? It isn't the character strings that are the same. Rather, there is some other thing that those character strings both stand for. The thing happens to be a distance, and the "height" fact connects that thing to some people.

2.1.2 How Many Things?

2.1.3 Why They're Connected

We usually have to say what kind of connection the fact represents. It's not enough to say that a fact connects an employee to a department, or to a date, or to a distance. We have to say whether he's assigned to or loaned to or manages the department, whether the date is his birthdate or hire date, and whether the distance is his height or something else.

2.1.4 The Roles They Play

Sometimes we have to clarify a third thing about a fact: what role each thing plays in the fact. This is particularly necessary when the fact connects several things of the same kind. We may have two employees connected by a "manages" relationship, or two parts connected by a "contains" relationship, but that's not enough information. We have to know who manages who, or which part contains which. One way to do this is to assign a sense of direction to the connection. We can say that the "manages" relationship goes from the manager to the employee, and the "contains" relationship goes from the assembly to the component.

However, direction is difficult to deal with when the fact involves more than two things. When John buys a computer from Sears, which is the "from" and which is the "to"?

A more general approach is to use role names, like "manager" and "managee", or "component" and "assembly", or "buyer", "seller", and "commodity". The use of role names actually covers directed relationships as well, since we can always use "from" and "to" as role names.

2.1.5 Example

Let's put this all together into an example that illustrates various aspects of a fact. In today's complex economic world, some companies own other companies, and they might sell such companies to each other. If we wanted to keep track of which sold which to which, we might need this form of the "sale" relationship:

relationship: SALE ................... : : : roles: BUYER SELLER COMMODITY : : : entity types: COMPANY COMPANY COMPANY

2.2 Entities and Relationships

We have identified the following things to say about a fact:

• The kinds of things it connects.
• The nature of the connection.
• The role each thing plays in the connection.
• How the things are represented.

2.2.1 Entities

The "kind" of thing involved in a fact is what we mean by the term entity type.

This term gets used in several ways, which can be confusing. It is sometimes expected that employees and departments are entities, but money and colors and dates are not. We don't make that distinction. It gets to be too troublesome in many cases. Children and birthplaces, for example, are often not considered entities, but we're hard pressed to explain why.

2.2.1.1 Instances and Types

The term entity, as we use it, refers to an individual instance, or occurrence. You and I are entities, being occurrences of the entity type "person".

In general, database design and description deal with types, e.g., "employee" and "department", while the database itself mentions the individual occurrences, namely the individual employees and departments.

As with most such generalizations, there are exceptions. Sometimes individuals are mentioned in the database description, when constraints specify the allowed values for a field, such as the set of valid colors, or the valid sexes. Furthermore, as we shall mention later, when the population happens to consist of a single individual, it may not be mentioned anywhere at all.

2.2.1.2 Subtypes

Later on, when we discuss the merging of pseudo-records, we will be interested in entity subtypes. For example, we might be interested in merging data about salesmen with general records about employees. Therefore it will be useful to specify which entity types are subsets of which others. One entity type is a subtype (or subset) of another entity type whenever all members of the first are always members of the second.

One important aspect of subtypes is the inheritance of properties. Any fact involving a type automatically applies to a subtype. For example, if employees have employee numbers and departments, then salesmen have employee numbers and departments.

2.2.2 Relationships

The kind of connection that binds entities together in a fact is what is meant by a relationship type.

A relationship type has a name, and a fixed number of things that it can connect together. That number is called its degree. A relationship between two things has degree 2, and is called a binary relationship. A relationship among three things has degree 3, and is called a ternary relationship. In general, a relationship connecting n things has degree n; however, the term n-ary is often reserved for relationships of degree greater than 2.

2.2.2.1 Participation

To determine pseudo-keys, it is necessary to know whether a relationship is one-to-one, one-to-many, or many-to-many. Furthermore, we may have to know this about combinations of roles in n-ary relationships. Consider an inventory relationship, involving part types, warehouses, and quantities on hand (QOH). Though each part type and each warehouse are likely to occur several times, the combination of a given part type and a given warehouse should occur only once.

We will use a notion of "participation" to express such characteristics.

For each role in a relationship, we will specify whether an entity can play that role in more than one occurrence of the relationship. E.g., an employee can occur in at most one occurrence of the relationship of being assigned to a department. We will also identify sets of roles in which such participation is limited to one. E.g., the combination of a part type and a warehouse may occur at most once in the inventory relationship.

Since we are mainly interested in whether the maximum participation is one or many, we will say that a role, or set of roles, has a maximum participation (MP) of 1 or n. 1 would signify a single-valued relationship, n a multi-valued one. E.g., for employees assigned to departments, MP for employees is 1 (each employee can have at most one such assignment), while MP for departments is n (a department could have many such assignments.)

In a similar way, when we plan to merge records, we will have to know whether all entities of a given type will necessarily participate in a relationship. That is, we have to know whether the relationship involves all or only some of the entities.

We will specify whether or not an eligible entity has to participate at least once by saying that a role, or set of roles, has a least participation (LP) of 0 or 1. 0 would signify an optional relationship, 1 a required one. E.g., for employees assigned to departments, LP for employees is 1 (each employee must have at least one such assignment), while LP for departments is 0 (a department might have no such assignments).

We combine the two concepts into a compact notation of the form LP*MP specified for each role in a relationship. In addition, it is useful to specify participations for sets of roles when the maximum participation is 1 for the set but not for all of the roles in the set.

The possible values of LP*MP are:

• 0*1 ("at most one")
• 1*1 ("exactly one")
• 0*n ("some", "many")
• 1*n ("at least one")

We illustrate the notation:

assigned inventory ........ ...................... : : : : : EMP DEPT PART-TYPE WAREHOUSE QUANTITY 1*1 0*n 0*n 0*n 0*n ---------------------- 0*1

2.2.2.2 Unary Relationships

Although we have been treating facts as connections or relationships among things, there is a limited sense in which it might be useful to think of facts involving single things as well. This would be like a simple list of things which are of interest for some reason. We might have the list of all employees, or the list of all products, etc.

For this reason, it also makes sense for us to allow unary relationships, i.e., relationships of degree one. Thus, by analogy with the binary relationship "assigned(Smith,Sales)", we could have the unary relationship "employee(Smith)".

2.2.2.3 Attributes of Relationships (Facts About Facts)

So-called "attributes of relationships", such as the dates when people started working for companies, can sometimes be handled conveniently as n-ary relationships (in this case, a relationship among three things). But it is necessary to recognize the case when we have several attributes of the same relationship (e.g., if we also had the dates when people stopped working for companies), so that we can merge them into the same record.

For that purpose we can treat relationships and facts as entities themselves, able to participate in other relationships and facts. As a result, we can have "facts about facts", such as:

• Fact 1: people have worked for companies.
• Fact 2: fact 1 began on date.
• Fact 3: fact 1 ended on date.

2.2.3 The Distinction Between Facts and Relationships

In most cases, facts and relationships are the same, as we have been treating them until now. However, it is convenient to let facts sometimes take on a richer structure, using relationships as a basic building block.

In the more general case, we can let facts be compositions or restrictions of relationships.

In composition, a fact is composed of several relationships. This is useful when the underlying relationships are known in the semantic model of the enterprise, but perhaps not all of the supporting details are to be maintained in the database. For example, we may have the relationships "employees have secretaries" and "secretaries have phone numbers", but the only facts we want to store in the database are "employees can be reached at phone numbers", i.e., "X is the phone number of the (unspecified) secretary of Y".

Restrictions are useful when the same relationship is to be maintained separately for different subsets of the possible entity types involved. For example, we might have "owns" as a relationship, but the facts "employees own stock" and "departments own projects" might be maintained separately. Or, we might want to separately maintain the facts "domestic employees are assigned to departments" and "foreign employees are assigned to departments". Or we might wish to use the "sales" relationship twice, once for a company's sales records and once for its purchasing records.

Facts and relationships are much the same thing, especially if we extend the concept of "relationship" to include derivable relationships, defined in terms of others. However, we tend to use "relationship" for the primitive associations, and "fact" for the more general notion of any association, primitive or derived.

2.3 Representation

We turn now to the fourth aspect of a fact: how things are represented. As we shall see, representation of entities can turn out to be a complex and difficult topic. One of the advantages of our methodology is that we do not allow this complexity to overshadow the whole design process. By deferring this to the end, we can first design for the facts we want maintained in the data, and then work out questions of representation.

2.3.1 Why Represent?

So far, we have really been discussing facts in the real world, not how they are expressed in data. When we said that an employee is assigned to a department, we had in mind a real flesh-and-blood employee, and a real working department. We didn't say that a certain person's name was assigned to a certain department name, nor did we say that a certain employee number was assigned to a certain department number.

Unfortunately, we can't put people and departments into the machine. We have to let symbols -- typically, character strings -- serve as surrogates. To represent a fact which connects two things, we create some conjunction of surrogates for those two things, generally by putting the symbols into the same record. To do that we exploit certain kinds of facts, namely those which relate things to symbols. When we put an employee number and a department number into the same record, representing the employee's assignment to that department, we are really dealing with three facts:

• Some employee has that employee number.
• Some department has that department number.
• The represented employee is assigned to the represented department.

2.3.2 How Represent?

An ideal representation would provide every entity with a uniquely corresponding symbol (character string) to serve as its surrogate.

We use "symbol" and "representation" in a very general way to mean any character string, particularly as it is used to stand for some other thing. The terms include the general ideas of naming, identifying, denoting, etc. "Bill Kent" is one of the symbols that can represent me, as well as several other people. "6", "6 feet", "72", "72 inches", are some of the symbols that can represent my height.

We know that idealized representation doesn't exist in a universal sense. Most entities don't have a single simple symbol that stands exclusively for them and nothing else in the whole world. For most things, we have to resort to some sort of descriptive phrase, such as "the IBM employee with employee number 999999". The best we can provide is that for some types of entities, there are some types of symbols which can serve as surrogates. Under these conditions, a symbol serves as a surrogate for an entity -- provided that we know what symbol type it belongs to, and what type of entity it is representing. Thus, "999999" represents a certain entity -- if we know whether the symbol is a social security number or an IBM employee number or an IBM part number or perhaps something else.

Representations fit into our general structure of facts. "Employees are represented by employee numbers", "people have names", and "heights are represented in inches with picture 99.9" are facts. Corresponding to this, we acknowledge that symbols are entities, and they are collected into entity types which we will also call symbol types. Employee numbers and people's names are two such symbol types. We can also think of all symbols collectively as one large type. Then, in terms of subtypes, we can say:

• "Employee number" is a subtype of "symbol", and
• "Symbol" is a subtype of "entity".

2.3.2.1 Symbol Types

A precise treatment of symbol types quickly becomes complex, and too esoteric for our purposes. We take a pragmatic approach, adequate for a practical data design methodology.

As a first approximation, we think of a symbol type as the set of character strings permitted to occur in a data field. (It is comparable to the "domain" concept in relational database theory.) Any characteristic which determines which actual character string can represent a given entity in a given field will also serve to distinguish different symbol types. For example, a given data field will probably accept exactly one of the following as a representation of my height: "6", "06", " 6", "6.0", "6.00", "6 feet", "110", "VI", "72", etc. Each of those belongs to a different symbol type. That is, there are at the very least nine different symbol types that can represent lengths (the reader can surely identify a great many more). All of the following properties might be involved in the description of a symbol type, and might serve to distinguish one symbol type from another:

• Identifier type (e.g., employee number vs. social security number), or unit of measure.
• Number system (decimal, octal, binary, hex).
• Scale and precision.
• String length.
• Other editing characteristics, often captured in a "picture" clause, including such things as embedded decimal points, leading dollar signs, padding characters, etc.

In an elegant theory, each of those properties could be expressed as a distinct "fact" about a symbol type. For the purposes of our methodology, we will simply let those be part of the informal description of distinctly named symbol types.

Different sets of character strings necessarily constitute different symbol types. But we don't force the converse. That is, different symbol types might contain the same character strings. E.g., employee numbers and part numbers might both consist of six-digit integers. It is acceptable to either treat this as one symbol type ("six digit integers"), or as two symbol types ("employee numbers" and "part numbers").

2.3.2.2 Symbol Facts

We will refer to a fact in which one of the entity types is a symbol type as a "symbol fact".

Not all symbol facts are used for representation. Some of them simply provide information, such as maiden names of employees, or a table of abbreviations (connecting two symbol types).

2.3.3 Other Representation Techniques

2.3.3.1 Structured Symbols

Some representations are structured in a form that requires multiple fields to represent a single entity. Examples:

• Dates (month, day, year).
• Addresses (number, street, city, etc.).
• Names (first, middle, last).
• Mixed-unit measurements (feet, inches).

Quite often, it is an arbitrary design decision whether such things are represented in single or multiple fields. It has little to do with the nature of the facts being maintained. Addresses may get split into multiple fields to facilitate formatting for letters and labels.

It is sometimes argued that in such situations we ought to describe components of things, or relationships among things (e.g., a date is a "relationship" between a month, a day, and a year), but that can be quite artificial. For the purposes of this design methodology, we bypass such considerations, and simply allow a symbol type to be specified as structured, along with an informal description of its structure.

Various situations can give rise to multi-field representations, including:

• Arbitrary design decision, e.g., addresses.
• The entity is a relationship.

  E.g., in expressing a fact about a marriage, the marriage might be represented by the identifiers of the two people involved.

• Additional entities are introduced as qualifiers to provide unique identification.

  E.g., state or country names are introduced to provide unique identification for cities. This is especially significant when such facts are introduced purely for identification purposes. E.g., there may have been no desire to record which state or country a city is located in.

• Multi-unit measurements.

  E.g., separate fields for feet and inches.

• Self-describing representations.

  E.g., auxiliary fields for the field length, unit of measure, scale, etc.

• Multiple entity types.

  E.g., when holders of company assets can be either departments or employees. There are two possible treatments:

  • When the representations are compatible, then there might be an auxiliary field to indicate the entity type which is present.
  • When the representations are incompatible, a separate field may be provided for each entity type. All but one are blank in each record. And there still might be one more field indicating which entity type is present.

2.3.3.2 Derived and Indirect Representations

Sometimes an entity will not have a distinctly visible representation in the data. Such an entity will not (directly) correspond to any field.

For example, an entity might be inferable from a related entity, or from its representation. Dates are sometimes embedded in the identifiers of things (date of claim is part of claim number, birth date is part of some European person numbers). A great deal of information may be embedded in part serial numbers: part type, place of manufacture, certain technical characteristics, etc.

In some cases the inference is more computational. Part numbers in certain ranges, or employee numbers in certain ranges, imply certain company locations. In some countries, person numbers are odd or even according to sex. Day of week can be computed from a date. Winners of elections can be computed from vote counts.

2.3.3.3 Non-Representation

The representation of some entities is derivable from the "context". Such entities are constant over all occurrences of the record type, and hence don't have to be identified via any data field. A given company is always the "seller" in its own sales records, and always the "buyer" in its own purchasing records. The playing schedule for a particular team will not list both teams for each game.

Sometimes the identity of an implicit entity is included in the record name. E.g., if we have separate employee records for each job type, then we don't need a field for the employee's job. If we have separate employee records for each company location, then we don't need a field for the employee's location.

2.3.3.4 Compressed Representations

The derived and indirect representations mentioned above essentially compress several entities into one field. In effect, one field represents a sales territory and its headquarters city. Another field represents a person (via his person number) and also his date of birth and his sex.

In practice, this is sometimes carried to the extreme of compressing several entities into one field simply because their representations are "too short"; letting them each occupy a single field would be inefficient.

For example, if sex and marital status were each representable by a single-character code, they might be combined into a "personal status" field containing the two characters. Even more extreme are computational forms of encoding: e.g., digits 1-4 represent the marital status of males, 5-8 the marital status of females.

2.3.3.5 Mapping Techniques

While some representations can be expressed in terms of symbol facts, we don't require that for all cases. It makes the methodology too cumbersome.

In effect, we will simply allow any entity to be replaced by a suitable representation. This representation might cause the introduction of multiple fields, or it might cause several entities to be represented in the same field, or the representation might occupy no fields at all. Sometimes additional facts will have to be "imported" in order to achieve suitable representation.

2.3.4 "Quality" of the Representation

We have so far described some assorted techniques for representing entities, e.g., by simple symbols, structured symbols, indirect reference, etc. We haven't yet said that such representations are necessarily unique. Uniqueness is just one of a number of qualities that a representation might have.

The qualities are not always all required. The overall process of selecting representations involves three distinct steps:

• Determine the quality of representation required.
• Determine what representation techniques are available.
• Select an appropriate one, or introduce something new if needed.

2.3.4.1 Existence

The first desirable quality of a representation is that one should in fact exist. Most things in the world around us don't have simple identifying labels. We refer to most things by a combination of pointing, complex noun phrases involving relationships to other things, and default assumptions regarding context and implicit qualifiers.

Entity types without direct representations include the earlier examples of elections or sales territories, and the individual pieces produced by some assembly lines. Animals are another example (though pets usually have representations, while wild animals usually don't).

2.3.4.2 Completeness

A complete representation provides a representation for every member of an entity type. Employee numbers are complete for employees (of a given company), but not for people in general. Maiden names are incomplete representations.

2.3.4.3 Uniqueness

A unique representation meets the common requirement for identification: a representation corresponds to at most one of the entities. People's names are generally non-unique; the same string can correspond to several people.

Non-unique representations commonly occur in data, and can still be quite useful to human users. Such users frequently make use of subtle default assumptions and local conventions. It is a natural and useful device, not to be rejected automatically as poor design.

Uniqueness is mainly required when the agent that will retrieve or interpret the data won't take advantage of such assumptions or conventions. Such an agent might be a computer (database manager) or a file clerk. In order for such an agent to retrieve a record about an employee, the employee's identifier must lead only to his record and nobody else's. If we want the agent to follow a path, perhaps to go from a department record to the employee record of its manager, then the manager's identifier must lead only to his record and nobody else's.

Uniqueness is especially important when the simple-minded agent is only able to cope with one record at a time. Non-uniqueness will disrupt the processor, if it retrieves several records when it was prepared to receive only one.

2.3.4.4 Singularity

A singular representation provides each entity with at most one corresponding representation. This is inverse to the notion of uniqueness. Social security numbers, though unique, are not singular: a given person might have several of them.

Singularity is not always required, and is sometimes undesirable. Measurable quantities often need different representations in different contexts -- at the very least, different units of measure. Sometimes it is important to represent people by employee numbers in one context and by social security numbers in another.

Lack of singularity could lead to:

• Failing to find an entity's involvement in a fact, by virtue of using the wrong representation. This could occur either in retrieval, or in path following. Some constraint enforcement also involves a form of path following. E.g., to be able to check that a department's manager is a real employee, the manager should be represented in the same way in the department file and in the employee file.
• Inadvertent violation of uniqueness, by allowing the same entity to participate several times, once under each of several representations.

Lack of singularity could be compensated if the processing agent could recognize the equivalence of several representations of the same thing, and perform conversions. Such conversions might be computational, as for measured quantities, or supported by other stored facts, such as the mappings between social security numbers and employee numbers. Current data processing agents rarely provide such capabilities, making singularity all the more important. The ability to navigate through non-singular identifiers is beyond the capability of current query processors (relational or otherwise) [K2].

While uniqueness is a widely recognized requirement for identifiers, singularity is little mentioned in the literature. This might be for several reasons:

• The distinction between uniqueness and singularity is not recognized, and people really mean both when they say "uniqueness".
• There is a historical bias towards machine requirements as opposed to human factors. Non-unique identifiers confuse the data management system, while non-singular identifiers only confuse the users, not the system. As long as the identifier leads to a single record, the system is content. It's not the system's problem if a person has two social security numbers, so that some facts about him go in one record while others go in another.
• There is no mechanical way to enforce singularity, so why bother talking about it.

We mention in passing that there are at least three ways to violate singularity:

• An entity might correspond to two symbols within the same symbol type, as with social security numbers.
• An entity type might have several different symbol types for its representation, as with social security numbers and employee numbers.
• An entity might belong to two different entity types, each having its own identifying symbol type, as with employees and military personnel.

2.3.4.5 Other Qualities

We mention some other qualities of representations that need to be considered. The importance of such criteria is a matter of judgement to be exercised during the design process.

A representation should be stable. If it were subject to change, then it would have to be updated wherever the entity was mentioned. This applies to "direct" representations, e.g., names, and also to indirect and qualified representations. It would be inadvisable to name sales territories after their headquarters cities, if the headquarters are likely to move. It is only reasonable to qualify city names with their states because we don't expect state boundaries to shift, transferring cities from one state to another.

It is sometimes held that the ideal identifier contains no information. E.g., embedding dates into serial numbers is considered undesirable. However, it would seem that embedded information is acceptable provided that (1) the information is stable, and (2) the embedding of information can be documented in the dictionary or other data description.

Mnemonic identifiers are generally easier for humans to deal with.

Simplicity is generally preferable. Direct and simple representation is preferable to indirect, derived, or structured representations.

Length is a factor. Anything can be uniquely identified if we can write enough paragraphs about it. Representations that are too long, or too variable in length, are undesirable. Even representations that are too short can sometimes create problems, leading to the kind of compression discussed earlier.

2.3.5 Using Combinations of Facts

Completeness, uniqueness, and singularity can be described in terms of participations in a fact which provides representation:

represented-by ................ : : THING REPRESENTATION x*y z*w | | | | 1 if complete, else 0- | | --1 if unique, else n | | 1 if singular, else n--- -don't care (usually 0: some names aren't used)

By representations here we mean one or more related things. Normally they would be symbols, but they might not be if we are dealing with indirect or qualified representations. If they are not symbols, then they in turn will have to be provided with representations. E.g., cities can be identified by a combination of city names and states, where the states in turn have to be provided with some representation. For the unique identification of the cities, it doesn't matter whether the states are identified by full names or abbreviations; we don't have to specify that as part of the city representation.

Very often, as in the case of qualified names, the representations will be obtained from combinations of relationships, such as:

is-in ..................... :1*1 1*n: : : : has-name : : .......... : : :1*1 0*n: : : : : : CITY NAME STATE : --------------- : : :1*1 0*1: :..............: identifies

2.4 Other Design Concepts

2.4.1 Entities and Records

Choosing the record types is an essential part of data analysis and design. In the present methodology, records are chosen in an objective and systematic way, based largely on the pattern of one-to-many and many-to-many relationships in the facts to be maintained.

Earlier methodologies choose records on the basis of a more restrictive "entity" concept (which we will call "major entities"), on the assumption that a record corresponds to an entity type. There are several difficulties with this approach:

• It is not always obvious which are the major entities. While various guidelines are offered, they tend to be vague and subjective (e.g., "the things which are important to the business, about which data is to be kept"). In practice, choosing the major entities often inverts the design process: users develop an ability to choose major entities that will correspond to the records they want in the data design.
• The correspondence tends to break down in the design process anyhow. Records corresponding to the major entities are taken to be a first approximation. The design process will sometimes remove some of these records, and add others. In the end, the records in the database don't correspond to the initial set of major entities. Very often, users are implicitly directed to alter their views of the business, by documenting major entities corresponding to the final set of records.
• A corollary decision is often forced, namely a distinction between "relationships" and "attributes". This decision is sometimes equally difficult to make, and depends somewhat on the choice of (major) entities. One guideline is that a relationship is an association among entities, while an attribute associates entities with "values" (an ill-defined concept).
• Major entities can't overlap, e.g., can't be subsets of one another, because record types can't. Users are forced to specify either "employees" or "clerks" and "salesmen". Whichever they specify will determine the records in the data design. Users are unable to say that they perceive clerks and salesmen as subtypes of employees, leaving the choice of records to the data design tool.

2.4.2 Existence Management

Sometimes another significant characteristic of "major entities" is that their existence needs to be explicitly managed. Some entities can come and go freely in the database, without any particular announcement of their arrival or departure. We are usually willing to mention a length, or a color, as a fact about something, without announcing that that particular length or color exists. On the other hand, we don't want to refer to an employee without prior assurance that such an employee exists. That is, for some entities it is necessary to have some mechanism for announcing their existence, and also their erasure from our sphere of interest. This can be a criterion for identifying major entities.

Although we try to treat this as a high-level semantic concept, the only mechanism for such announcements in conventional database systems is to insert and delete records. Therefore, it becomes important to have a record type corresponding to an entity type for which such announcements are required.

This is rarely significant, in practice. It almost invariably turns out that single-valued facts will be maintained about anything whose existence needs to be managed, so they will have records anyhow. Exceptions to the rule almost have to be contrived. One case might occur if all the facts we wanted to maintain about something happened to be multi-valued. E.g., if projects had multiple managers and multiple completion dates and multiple goals and multiple budgets, then we might have many "intersection" records for these m:n relationships, but no one record keyed on project numbers. An explicit "announcement" specification would be needed in this case.

2.4.3 Complex Situations

Other methodologies, based on earlier concepts of entities, relationships, and attributes, tend to have difficulty with:

• N-ary relationships.

  E.g., buyer X bought item Y from seller Z.

• Attributes of relationships.

  E.g., people started working for companies on dates.

• Entity subtypes.

  E.g., employees and salesmen.

• Multi-valued attributes.

  E.g., multiple colors of an object.

• Attributes of attributes.

  E.g., what percent of the object has each color.

• Complex identifiers

  E.g., multi-field or imbedded.

2.4.4 Normal Forms and Normalization

Normal forms [K4] are valuable as a design objective, yielding designs with minimal redundancy and minimal exposure to update anomalies, sometimes with attendant performance penalties for retrieval operations.

However, some methodologies apply normalization as a process, in which badly-designed records get decomposed (normalized) into better records. Ours is a "synthetic" approach [B], constructing records in normal form directly.

2.4.5 Derivable Facts

We are implicitly assuming that the specified facts are independent of each other, in the sense that one can't be derived from the others. This might be violated, for example, if we specified the facts:

• Employees are assigned to departments.
• Departments have managers.
• Employees have managers.

These facts are redundant. If implemented unintentionally, we would have a badly designed database. At the very least, we should require that derivable facts be separated from the others. If it is necessary that they be made available from the database, there are two major design alternatives:

• Store them redundantly. This should be augmented with some facility for checking the consistency of the redundant data.
• Derive the data on request from the underlying primary data. This option does not allow for updating the derivable information.

A similar assumption is that the specified facts have been decomposed into independent components as much as possible. For example, the fact that

• Employees have managers in departments

is not, in itself, redundant. But this should (assuming a normal company policy) be presented in the more elementary form:

• Employees are assigned to departments.
• Departments have managers.

3 THE DESIGN PROCESS

3.1 Specify the Facts to be Maintained

These will be specified in terms of relationships among entity types. In practice, we expect that the facts, relationships, and entity types will get defined in an iterative, concurrent fashion. Sometimes it may be easier to start listing the entities first, and then to collect the facts about them. New facts and relationships may in turn give rise to new entity types.

The set of entity types and relationships should be useful beyond a single application or database. The design of subsequent databases will probably involve many of the entities and relationships established in previous designs, although some new ones will undoubtedly be added.

In the following, we indicate the information needed for each construct. Implementations of this methodology can provide various mechanisms for specifying this information, including possible default rules.

For each fact, specify:

• A fact identifier (arbitrary).
• The relationship name, or sequence of composed relationships.
• The entity type occurring in each role, if more restrictive than that defined for the relationship.
• Least and most participations, if more restrictive than in the relationship definitions.

For each relationship, specify:

• Relationship name.
• Degree (number of roles).
• Role names.
• The entity types permitted in each role.
• Least and most participation for each role, and also for selected sequences of roles.

For each entity type, specify:

• Entity type name.
• Whether it is a subtype of another entity type.
• Whether it is a symbol type and, if so, whether it is structured.

3.1.1 Examples

We will follow two example situations: employees taking courses, and people winning elections. We treat them as an extension to the introductory example, so that the facts presented there are also available, particularly if needed for representations.

For brevity's sake (though it's probably too late for that), we will not illustrate all aspects. We present the facts immediately in diagram form, with role names defaulting to entity type names:

covers has-off located begins ......... .......... ............ ......... : : : : : : : : COURSE SUBJECT COURSE OFFERING OFFERING LOCATION OFFERING DATE 1*1 0*n 0*n 1*1 1*1 0*n 1*1 0*n gets-grade-in ................... : : : EMP OFFERING GRADE 0*n 0*n 0*n ---------------- 0*1 held-in won-by ......... .......... : : : : ELECTION YEAR ELECTION PERSON 1*1 0*1 1*1 0*n

3.2 Generate a "Pseudo-Record" for Each Fact

A pseudo-record is just a fact in disguise. It contains one field for each role associated with the fact. When actually carrying out the methodology, we would record how each field relates to the fact, i.e., the field's corresponding relationship, role, and entity type. The least and most participations for each role or set of roles are inherited by the corresponding fields or sets of fields.

We do not as yet care anything about representations. If the role actually involves a symbol type, then we expect symbols to be in the field. Otherwise, we pretend that whatever thing is playing the role is actually sitting in the field. For example, in the pseudo-record corresponding to the fact that employees have employee numbers,

has-emp# ........ -------------- | EMP | EMP# | --------------

we imagine that the second field contains employee numbers, while the actual employees are sitting in the first field. It may be difficult to imagine some things in the fields, such as colors or days or weights (the actual heaviness, not any numerical measurement of it), but that's the appropriate mental picture at this point.

Pseudo-records could be candidate records for the final design, but they are likely to have two undesirable characteristics at this point:

• Most fields don't contain machine-processable representations.
• The records are very fragmented. There is essentially a separate record for each "attribute" of an entity.

Example:

covers has-off located begins ........ ......... ........... ........ : : : : : : : : ---------------- ----------------- ------------------- --------------- |COURSE|SUBJECT| |COURSE|OFFERING| |OFFERING|LOCATION| |OFFERING|DATE| ---------------- ----------------- ------------------- --------------- 15 16 17 18 19 20 21 22 1*1 0*n 0*n 1*1 1*1 0*n 1*1 0*n gets-grade-in ................... : : -------------------------- | EMP | OFFERING | GRADE | -------------------------- 23 24 25 0*n 0*n 0*n ------------------ 0*1 held-in won-by ......... .......... : : : : ------------------- --------------------- | ELECTION | YEAR | | ELECTION | PERSON | ------------------- --------------------- 26 27 28 29 1*1 0*1 1*1 0*n

3.2.1 A Shortcut

Representations will be dealt with at a later step, making allowances for a large variety of difficult situations. However, we can take a shortcut at this point which will keep the methodology simple for simple cases, and which brings our methodology more in line with others.

When an obvious and adequate representation is available for an entity type (e.g., employee numbers), then we can use that representation immediately as a "surrogate" for such entities, as follows:

• Eliminate the pseudo-record expressing that representation fact.

  E.g., eliminate the pseudo-record corresponding to "employees have employee numbers".

• Substitute the symbol type for the entity type in all other pseudo-records.

  E.g., substitute EMP# for EMP everywhere.

In our imaginary picture, we have now actually let employee numbers occupy the fields, replacing the employees themselves.

3.3 Identify "Pseudo-keys" For Each Pseudo-record

A pseudo-key is a sequence of fields that could be an actual key if all entity types involved had simple unique identifiers. A key is a set of one or more fields that provides uniqueness of records. A given entity or sequence of entities may only occur once in these fields. More precisely, we are only interested in minimal sets: a set of fields will not be considered a key if any subset is a key.

The main value of keys in record structures is that they enforce single-valuedness of facts, i.e., maximum participations of 1. If an employee's number is only permitted to occur in one employee record, he is thereby limited to having only one entry for his salary, his department, etc.

A pseudo-key corresponds to a role or set of roles in a fact having maximum participation of 1 (participations of 0*1 or 1*1).

Example (we use "====" to designate the pseudo-keys):

covers has-off located begins ........ ......... ........... ........ : : : : : : : : ---------------- ----------------- ------------------- --------------- |COURSE|SUBJECT| |COURSE|OFFERING| |OFFERING|LOCATION| |OFFERING|DATE| -======--------- --------========- -========---------- -========------ 15 16 17 18 19 20 21 22 1*1 0*n 0*n 1*1 1*1 0*n 1*1 0*n gets-grade-in ................... : : : --------------------------- | EMP# | OFFERING | GRADE | --===============---------- 23/2 24 25 0*n 0*n 0*n ------------------- 0*1 held-in won-by ......... .......... : : : : ------------------- --------------------- | ELECTION | YEAR | | ELECTION | PERSON | --========---=====- --========----------- 26 27 28 29 1*1 0*1 1*1 0*n

3.4 Merge Pseudo-records Having Compatible Keys

The natural thing to do at this point is to merge records wherever possible. Such merging is analogous to a join in the relational model:

--------- --------- ------------- | X | Y | + | X | Z | => | X | Y | Z | --------- --------- -------------

3.4.1 Merging on Simple Keys

3.4.1.1 Ideal Merges

Merging is most likely to occur on simple keys. Two pseudo-records may only be merged if their corresponding keys are going to contain the same occurrences of the same kinds of things. The strictest way to assure this is to require that the corresponding keys contain the same entity types, and that they will both contain the full population of the entity type. In other words, the least participation for each key should be 1. Since all keys have an MP of 1, these keys will have LP*MP = 1*1.

An "ideal" merge is thus possible when the two keys involve the same entity type and both have LP*MP = 1*1.

Example:

covers ........... : : -------------------- | COURSE | SUBJECT | (Record R1) --======------------ 15 16 begins ................................ : : : located : : ..................... : : : : : : : has-off : : : : ......... : : : : : : : : --------------------------------------- | OFFERING | COURSE | LOCATION | DATE | (Record R2) --========----------------------------- 18 19 21 17 20 22 gets-grade-in ................... : : : --------------------------- | EMP# | OFFERING | GRADE | (Record R3) --===============---------- 23/2 24 25 won-by .................... : : : held-in : : ......... : : : : : ---------------------------- | ELECTION | YEAR | PERSON | (Record R4) --========---====----------- 26 28 27 29

3.4.1.2 Unequal Populations

The restrictions can be weakened when we can "pad" the populations. In many cases, a pseudo-record whose key has a least participation of 0 can be "padded" to include the missing entities, with some sort of "null" values for the related entity. For instance, instead of excluding employees who have no departments from the "assignment" pseudo-record, we might include them with a blank department, or some other indication of null. Such padded pseudo-records will then have a full population of values in their keys, and they can be merged with other pseudo-records having either 1*1 keys or similarly padded keys.

3.4.1.3 Subtypes

The padding concept can be extended to allow merging of entity subtypes. The entity type in any key field can be "promoted" to some supertype, with the key having a least participation of 0. For example, the fact that "salesmen serve territories" can be promoted to "some employees serve territories".

The resulting pseudo-records can then be merged as above for unequal populations. Either one or both of the pseudo-records might be promoted. Thus this technique might be used to merge facts about salesmen with facts about employees, or it might be used to merge facts about salesmen with facts about clerks by treating them both as employees.

As before, the feasibility of such merges depends on the acceptability of null values. In practice, such promotions will generally be limited to those cases where suitable identifiers are available for the supertypes.

3.4.1.4 Summary

Merging pseudo-records having simple keys is possible if:

• The entity types in the keys are the same, or one is a subtype of the other, or they are subtypes of a common supertype.
• The key fields will have the same populations, or the populations can be equalized by padding the fields outside these keys with null values.

3.4.2 Merging on Compound Keys

A compound key contains more than one field.

In pseudo-records, ordinary entities always correspond to single fields. Compound keys correspond to facts. Merging on compound keys requires that the keys represent the same fact, which is a stronger requirement than that the keys contain matching entity types. Matching entity types could be involved in different relationships. Merging compound keys is, in effect, merging attributes of relationships, and we should only merge attributes of the same relationship. For example, we can merge pseudo-records corresponding to the following facts, all of which would have compound keys consisting of people and companies:

• Fact 1: people have worked for companies.
• Fact 2: fact 1 began on date.
• Fact 3: fact 1 ended on date.

It would not be appropriate to merge these with some other facts involving people and companies, such as which people own which companies.

3.4.3 Pseudo-Records With Multiple Keys

A pseudo-record with multiple keys corresponds to a one-to-one relationship, e.g., between department and manager (employee), or between employee and spouse. This creates an opportunity for several entities to be "subjects" in the same record, which is sometimes desirable and sometimes not. We probably wouldn't object to combining the facts

• Employee born-on date
• Employee married-to spouse
• Spouse born-on date

into the record:

------------------------------------------------ | EMPLOYEE | BIRTHDATE | SPOUSE | SP-BIRTHDATE | --========---------------======-----------------

But the same process allows us to merge all department information into the employee records, by putting all such data into the records of the employees who manage departments. That option appears undesirable.

Extensive merging on both subjects becomes inadvisable if the connection between the subjects is likely to change. That's one reason not to maintain information about a department in the employee record of its manager.

Another concern has to do with nulls. If one of the pseudo-keys has 0*1 participation, and the record is merged on that key, then all other fields in the record must admit null values -- including the other pseudo-keys. We can call a pseudo-key that has to admit null values a soft key. Further merging on a soft key is generally undesirable, since softness is propagated. Whenever a record is merged on a soft key, all the fields in the other record must be able to accept nulls, including the key in the resulting merged record.

For example, consider the following pseudo-records, in which we use "=-=-=" to indicate keys with 0*1 participation:

has-name earns manages ........ ....... ....... : : : : : : ---------------- ---------------- ---------------- | DEPT# | NAME | | EMP# | MONEY | | EMP# | DEPT# | --=====--------- --====---------- -=-=-=---=-=-=-- 7 8 11 12 13 14 1*1 0*n 1*1 0*n 0*1 0*1

Suppose we merge the first and third of these on the DEPT# field in order to combine information about departments. Since 14 is a 0*1 key, all other fields in that record must admit nulls after the merge, making 13 a soft key (indicated by ":"):

----------------------- ---------------- | DEPT# | NAME | EMP# | | EMP# | MONEY | --=====---------:-:-:-- --====---------- 7 14 8 13 11 12

3.4.4 Merging is Optional

The natural and appropriate inclination is to merge as far as possible. It is preferable to aggregate all facts about an entity into a single record, creating a model in which that record "represents" that entity. That minimizes problems of "population management", e.g., making sure that the set of employees who earn salaries is the same as the set of employees assigned to departments. It provides a "master file" concept, i.e., a central list of all the currently existing entities of that type.

However, merging to the maximum degree is not always desirable. Some considerations are logical, others physical.

Merging can be carried to absurd extremes via supertypes. Almost any pair of types can be perceived as subsets of a larger type (resources, assets, products, physical objects, priced things, etc.). Theoretically, these could drive some designs to a single monstrous record with nulls permitted in most fields. In practice, such merging is limited to cases where suitable identifiers are available for the supertypes. Occasionally, new identifiers will be invented to facilitate such merges.

Other considerations are more physical, and probably should not be considered in a purely logical design. Possibly wasted space for null values is one consideration. Or, merging might be undesirable if different facts are used exclusively by different applications, or on different systems, or at different locations.

3.4.5 Merge vs. Join

The merge step of this methodology is quite similar to the join operations of the relational model. There are a few distinctions to keep in mind.

In the first place, merging is a design step, rather than a database operation. That is, we only manipulate data descriptions, not actual data.

3.5 Assign Representations

At this point, our pseudo-records are a mixture of symbols and non-symbols. In order to convert these to proper records, we have to eliminate the non-symbol fields, making sure they are adequately represented via symbolic fields. Most of the time, this simply means replacing an entity type with a suitable identifier type. But sometimes other things happen.

We repeat an earlier note: Most methodologies assume that a simple representation is available for all entities. What we deal with in this section goes beyond the capabilities of other methodologies. The reader who wishes to deal with the simple case first, or who wishes simply to compare this with other methodologies, is encouraged to skip this section on first reading.

To assign representations, do the following steps for each field in the pseudo-record, including any additional fields introduced in the process:

1. If the entity type in the field is a structured symbol type, replace by multiple fields, and exit.
2. If the entity type is a symbol type, leave it alone, and exit.
3. If the entity type needs no representation, delete it, and exit.
4. If the representation is derivable from another field (including indirect representation), delete this field, and exit.
5. Find a set of facts whose combination gives the required qualities of completeness, uniqueness, and/or singularity (as well as other qualities).

   In the vast majority of cases, this will consist of just one simple symbol fact.

   Introduce new facts if needed.

   Facts suitable for representing a supertype may be employed. E.g., in seeking identifiers for salesmen, identifiers for employees may be used.

   If the related things are not symbols, the process may later have to be repeated for their representation.

6. If several suitable sets of facts are available, choose one.
7. "Import" such facts into the record, if not already there.
8. Delete the field.
9. Repeat the assignment of representations for any imported facts.

3.5.1 Example

3.6 Alternative Designs

This step of the methodology is not fully developed as yet. The kinds of design alternatives to be considered are described in [K3] and [K5]. [K3] has a preliminary proposal for transforms to systematically generate some of the alternatives mechanically.

Each alternative design corresponds to some different way of specifying the facts. Fact specifications are not particularly unique. Even using entity/relationship concepts, there are many ways to describe a given situation. Our objectives are:

• To allow the user flexibility in how he chooses to provide his application description.
• To let the final design be driven more by the processing requirements than how the user happened to phrase his application description.

A variation of the first goal is to allow application descriptions to be standardized without necessarily imposing a corresponding rigidity on the data designs. It is very useful to be able to document that similar information has been implemented in different ways in different databases.

3.7 Naming Fields and Record Types

In general practice, there is no systematic discipline for the naming of fields and records. Hence there is nothing predictable about what such names signify. At best, there might be various guidelines and local standards.

Often, a field name includes indications of some or all of the following things, abbreviated and concatenated in various ways:

• The entity type represented in the field.
• The form of representation used.
• The relationship in which it is involved.
• The role played in that relationship.
• An arbitrary label.

The only uniform requirement seems to be that field names be unique within a record. This precludes the use of any one of those constructs consistently as the field name. Even role names may not be unique enough. In fact, the same relationship might occur twice in one record, definitely rendering the role names non-unique within the record. Example: a record containing two birthdays, the employee's and the spouse's.

We give arbitrary names to our fields:

--------------------- "COURSE RECORD" (R1): | COURSE# | SUBJECT | --=======------------ ------------------------------------ "OFFERING RECORD" (R2): | OFF# | COURSE# | LOCATION | DATE | --==============-------------------- --------------------------------- "EDUCATION RECORD" (R3): | EMP# | COURSE# | OFF# | GRADE | --=====================---------- ----------------- "ELECTION RECORD" (R4): | DATE | WINNER | --====-----------

3.8 Iteration

The whole database doesn't have to be designed at once. You can start with any initial set of facts, relationships, and entities, and then come back and add more later, as many times as needed. The key steps in subsequent iterations are:

• Specify a new pseudo-record type for each new fact introduced.
• Specify representations and keys.
• Merge with previously generated record types.

4 CONCLUSION

4.1 Highlights of This Approach

We focus more on what facts are to be maintained, rather than on what the facts are about. We start with one record per fact, rather than one record per entity.

The user isn't forced to make distinctions between such things as "relationships" and "attributes" (or was that "entities" and "attributes"?). While there are times when he might feel more comfortable making that distinction, there are too many cases where it is hard to decide (e.g., birthplace).

Neither is the user forced to choose between entity types and subtypes.

Other design schemes have one stage for handling relationships, another for handling attributes. But they do practically the same thing in both stages. We don't distinguish between them, and use one process for handling both.

Some design schemes ask the user to proceed in two stages, first for "important" things and later for "details". There is no criterion for deciding what's important. But such methods really expect "important" things to be entities for which there will be corresponding records. We don't have any such expectations. Our design scheme is homogeneous. The user can deal with everything at once if he wants to. Or he can iterate in as many stages as he likes; if appropriate, he can view these as increasing degrees of detail.

Some methods feel that "keys" are the key (pun intended) to entities. If something has a unique identifier, then it is an entity and should have a corresponding record. But that doesn't always hold in practice. Even if cities had unique names, we wouldn't necessarily want a distinct record type for cities just because we happened to be recording people's birthplaces. Our approach defers treatment of unique identifiers until later, after we've determined when they are needed.

We provide a rational and objective basis for choosing the record types.

We use a simplified form of entity-relationship model. It conforms more closely to the way the user perceives his enterprise, rather than to the way the data is structured. He can therefore express his requirements more easily, without being forced to make premature data design decisions.

We go beyond other methodologies in suggesting alternative designs for the application.

4.2 Indirect Benefits

4.2.1 Conceptual Models

Facts are specified in terms of entities and relationships, which themselves ought to be documented. There are various approaches to developing the necessary collection of entities and relationships:

• Develop as needed for a database design, and then augment it for subsequent databases.
• Document the meanings of existing data.
• Do a top-down analysis of the business.

4.2.2 Data Documentation

4.2.3 Understanding the Application

Data elements inherently do represent facts, in terms of entities and relationships, in the form we have developed. If you have trouble organizing your requirements in the form of such facts, then either the application is not suitable for implementation in a database, or you do not adequately understand the application.

4.3 Convergence With Other Work

This work is an outgrowth of entity/relationship theory [C] and its semantics [K1], and traces at least back to the "irreducible relations" of [HOT]. It is also an extension of "synthetic" design methodologies [B]. The aims of our work are close to those of Imielinski and Lipski [IL]: "...we believe that the atomic, self-explainable relations, in terms of which all other relations considered are explained, should constitute the input of the design process. The design process should construct more complex database relations in terms of the semantics of input relations."

The work also converges with recent developments in the universal relation branch of relational database theory. Our facts and pseudo-records approximate the objects, associations, basic facts, and base relations of [FMU, MU, MW].

The principal differences between our work and the others:

• We are based on a deeper semantic structure, which distinguishes facts, relationships, roles, entities, and representations. In particular, we deal with entities and facts rather than representations and unlabeled dependencies, which don't always correspond well to these deeper semantics.
• We allow a more realistic set of transformations to the final data configurations to be used.
• We recognize that a variety of data structures might be used to represent the same facts. We let the user specify the required facts in a flexible way, and we generate a variety of suitable designs, not restricted by the form in which the user chose to describe the facts.

5 REFERENCES

[ANSI] The ANSI/X3/SPARC DBMS Framework, Report of the Study Group on Data Base Management Systems, (D. Tsichritzis and A. Klug, editors), AFIPS Press, 1977. Also Information Systems 3(4), 1978.

[B] P.A. Bernstein, "Synthesizing Third Normal Form Relations From Functional Dependencies", ACM Transactions on Database Systems 1 (4), Dec. 1976, pp. 277-298.

[C] P.P. Chen, Entity-Relationship Approach to Information Modelling and Analysis, North Holland, 1981.

[D] C.J. Date, "The Outer Join", IBM Technical Report TR03.181, Jan. 1982.

[FMU] R. Fagin, A.O. Mendelzon, and J.D. Ullman, "A Simplified Universal Relation Assumption and its Properties", ACM Transactions on Database Systems 7(3), Sept. 1982, pp. 343-360.

[HOT] P.A.V. Hall, J. Owlett and S.J.P. Todd, "Relations and Entities", in G.M. Nijssen, Modelling in Data Base Management Systems, North Holland, 1976.

[IL] Tomasz Imilienski and Witold Lipski, Jr., "A Systematic Approach to Relational Database Theory", ACM SIGMOD International Conference on Management of Data, June 1982, Orlando, Florida.