Page Numbers: Yes   X: 530   Y: 10.5"   First Page: 113
Columns: 1   Edge Margin: .6"   Between Columns: .4"
Margins:   Top: 1.3"   Bottom: 1"
Line Numbers: No   Modulus: 5   Page-relative
Even Heading:qk40(635)\g
DESIGN AND IMPLEMENTATION OF A RELATIONSHIP-ENTITY-DATUM DATA MODELy756qck40\g1f1 10f0 1f1 19f0 1f1 11f0 2f1 5f0 2f1 4f0 2f1 4f0 1f1
Odd Heading: Not-on-first-pageqk40\g
APPENDIXy756qck40\g1f1
10. Appendix:  Axioms and formal definitions	z18697x6e36jk48(2116)\f5b
The definition of a database includes a set of domains D (the domain domain), a set of relations R (the relation domain), a set of attributes A (the attribute domain), and a set of datatypes T (the datatype domain).  We also define a subdomain function sd mapping D to D.  The function sd must define a partial ordering of D.	z18697x6e6jk40\55b1B41b1B44b1B48b1B61b2B9b1B4b1B16b2B35b1B1f5b1f0B
We define the fundamental type constraint for a database:	z18697x6e6jk40\57f5b1f0
The Attribute Type Constraint.  (a) Every relationship in a relation R must have the same number of elements.  We assign identifiers for corresponding elements of the relationships belonging to R, the attributes a1, a2, a3, ... aN.  (b) For any of these attributes ai, the value associated with ai for every relationship in R must be an element of the same datatype or domain di, or of a domain si in the transitive closure of sd applied to di.	z18697l3712x6e8jk40\i29I40i1I124i1I17i1f1o252 1f0o0 3f1o252 1f0o0 3f1o252 1f0o0 7f1o252 1f0o0 1I34i1f1o252 1f0o0I28i1f1o252 1f0o0I27i1I51i1f1o252 1f0o0I17i1f1o252I1f0o0 30b2B12i1f1o252I1f0o0 1f5b1f0B
Because every relationship in a relation R has the same attributes, we may unambiguously refer to these as simply R's attributes.  Every relationship in R has a value of the same type associated with an attribute A, so we define a function at mapping A to the union of D and T, and call at(A) A's type.	     z18697x6e10jk40\41i1I72i15I24i1I59i1I26b2B9b1B17b1B5b1B11b2B1i1I2i1I3i4I1f5b1f0Bi1I
Relation keys	z18697x6e12jk80\i13f5bI1f0Bi
Each data schema includes a uniqueness function au mapping A to the set {none, keypart}.  If a relation R has M attributes, of which some subset a1, a2, ... aN (where N < M) have au(ai) = keypart, then no more than one relationship in R is permitted to have the same value associated with attributes a1, a2, ... aN..	z18697x6e6jk40\48b2B9b1B85i1f1o252 1f0o0 3f1o252 1f0o0 7f1o252 1f0o0I20b2B2f1o252 1f0o0 116i1f1o252 1f0o0 3f1o252 1f0o0 7f1o252 1f0o0I
Normalization		z18697x6e12jk80\i14f5bI1f0Bi
For a relation R of order N, denote the predicate whose truth in the represented world corresponds to the presence of a relationship in the relation by Rp[a1, a2, ... aN].  The arguments ai correspond to the attributes of R.  We then define:	z18697x6e6jk40\153f1o4 1f0o0 2f1o252 1f0o0 3f1o252 1f0o0 7f1o252 1f0o0 19f1o252 1f0o0 52i1I
A relation R is in irreducible form iff it cannot be split into relations R1, R2, ... Rk such that for all possible states of the represented world:	z18697l4269x6e8jk40\19i11I45f1o252 1f0o0 3f1o252 1f0o0 7f1o252 1f0o0 60i1I
Rp[x1, x2, ... xN] <-> R1p[xi1, ... xik] & ... & Rkp[xj1, ... xjl]z18697l5539x6e8jk40\1f1o4 1f0o0 2f1o252 1f0o0 3f1o252 1f0o0 7f1o252 1f0o0 2b3B2f1o252 1o4 1f0o0 2f1o252 2f0o0 7f1o252 2f0o0 2f3 1f0 5f3 1f0 2f1o252 1o4 1f0o0 2f1o252 2f0o0 7f1o252 2f0o0
wherez18697l5539x6e8jk40
{xi1, ... xik} I {x1, x2, ... xN}z18697l6809x6e6jk40\2f1o252 2f0o0 7f1o252 2f0o0 2f3 1f0 3f1o252 1f0o0 3f1o252 1f0o0 7f1o252 1f0o0 1f3
   ...z18697l6809x6e6jk40\6f3
{xj1, ... xjl} I {x1, x2, ... xN} z18697l6809x6e6jk40\2f1o252 2f0o0 7f1o252 2f0o0 2f3 1f0 3f1o252 1f0o0 3f1o252 1f0o0 7f1o252 1f0o0
A relation is in functionally irreducible form iff (1) it is in irreducible form or (2) it is the natural relational join on a key attribute of two or more binary relations, and there is a dependency between the other (non-joined) attributes a1, a2, ... aN such that the semantics of attribute ai is dependent upon the value of ai+1, for i = 1, 2, .. N-1.	z18697x6e12jk40\17i24I1i4I197f1o252 1f0o0 3f1o252 1f0o0 7f1o252 1f0o0 39f1o252 1f0o0 33f1o252 3f0o0 23i1I
Axioms	z18697x6e12jk80\i
Below are the beginnings of an equational specification of the DB interface developed by Jim Donahue of the Computer Science Lab.  Currently missing are complete descriptions of the schema operations (DeclareDomain, DeclareRelation, DeclareAttribute, . . .), some of the detailed description of the behavior of operations on erroneous arguments (the type-checking of RelationSubset, for instance), and any discussion of segments, transactions and initialization.  A complete description will appear in a forthcoming paper.	z18697x6e12jk40\522i1I
In this style of specification, we present the semantics of the operations in terms of behaviorally equivalent programs composed of sequences of Cypress operations.  Since the only way you can interrogate entities is through DomainSubset, the only important property of DeclareEntity is that it may affect the value of a later invocation of DomainSubset.  The equations specify this by stating that certain sequences of Cedar statements are equivalent.	z18697x6e12jk40\452i1I
In the following, we will use the abbreviation	z18697x6e18jk80\46i1I
	(s1; . . .; sn) THEN e1 ~ e2z18697x6e18jk80\3f1o252 1f0o0 10f1o252 1f0o0 8f1o252 1f0o0 1f3 1f0 2f1o252 1f0o0
where s1, ..., sn are Cedar statements and e1 and e2 are Cedar expressions to mean that	z18697x6e18jk80\7f1o252 1f0o0 8f1o252 1f0o0 27f1o252 1f0o0 6f1o252 1f0o0 35i1I
	{ s1; ...; sn; RETURN[e1] } ~ { s1; ...; sn; RETURN[e2] }
z18697x6e18jk80\4f1o252 1f0o0 8f1o252 1f0o0 10f1o252 1f0o0 4f3 1f0 4f1o252 1f0o0 8f1o252 1f0o0 10f1o252 1f0o0
(Quite often in what follows, the equivalences will be between Cedar procedure bodies; if Cedar were an expression language then the equivalences would be somewhat simpler to state.)	
z18697x6e18jk80\182i1I1i
Basic Operations on Entities	z18697x6e12jk40\i
The fundamental property of entities is that no two entities with the same name and same domain can exist (this is not true for relationships).  The operations that manipulate entities include:	
	DeclareEntity -- add (or look up) an entity in a particular domain
	DestroyEntity -- remove an entity from a domain
	NameOf -- give the name of an entity
	DomainOf -- give the domain of an entity
	Eq -- compare two entities
	Null -- has an entity been destroyed?
	DomainSubset -- produce the subset of a domain with names in a given range
	NextEntity -- sequence through an entity set
	ReleaseEntitySet -- free the storage used by entity set (affects performance only)
	DeclareEntityz18697x6e6jk40
DeclareEntity	z18697x6e12jk40\i13I1i
The basic operation on entities is DeclareEntity, which either creates a new entity in a particular domain or returns a previously existing one.  Its semantics is given in the following equations:	z18697x6e6jk40
1. Declare produces an entity with the right name and domain:	
(e: Entity = DeclareEntity[d, name, NewOnly]) THEN
 [ DomainOf[e], NameOf[e] ] ~ [ d, name ]z18697l3936d3424x3e6jk40\142f3 1f0
2. NewOrOld is only a convenience:	
DeclareEntity[d, name, NewOrOld] ~
{ e: Entity = DeclareEntity[d, name, OldOnly];
  IF e = NIL THEN RETURN[DeclareEntity[d, name, NewOnly]] ELSE RETURN[e] }z18697l3936d3424x3e6jk40\69f3 1f0
3. Declare OldOnly is the same as domain subset:	
DeclareEntity[d, name, OldOnly] ~
 { es: EntitySet = DomainSubset[d, name];
   e: Entity = NextEntity[es]; ReleaseEntitySet[es]; RETURN[e] }z18697l3936d3424x3e6jk40\82f3 1f0
4. Declare NewOnly fails if the entity already exists:	
IF DeclareEntity[d, name, OldOnly] # NIL THEN DeclareEntity[d, name, NewOnly] ~
IF DeclareEntity[d, name, OldOnly] # NIL THEN SIGNAL Error[AlreadyExists]z18697l3936d3424x3e6jk40\134f3 1f0
5. Declare doesn't work on system domains:	
DeclareEntity[DomainDomain, name] ~ SIGNAL Error[ImplicitSchemaUpdate]
DeclareEntity[RelationDomain, name] ~ SIGNAL Error[ImplicitSchemaUpdate]
DeclareEntity[AttributeDomain, name] ~ SIGNAL Error[ImplicitSchemaUpdate]
DeclareEntity[DataTypeDomain, name] ~ SIGNAL Error[ImplicitSchemaUpdate]
DeclareEntity[IndexDomain, name] ~ SIGNAL Error[ImplicitSchemaUpdate]
DeclareEntity[IndexFactorDomain, name] ~ SIGNAL Error[ImplicitSchemaUpdate]z18697l3936d3424x3e6jk40\78f3 1f0 72f3 1f0 73f3 1f0 72f3 1f0 69f3 1f0 75f3 1f0
6. DeclareEntity doesn't work for NIL or null arguments:	
DeclareEntity[NIL, name] ~ SIGNAL Error[NILArgument]
IF Null[d] THEN DeclareEntity[d, name] ~
IF Null[d] THEN SIGNAL Error[NullifiedArgument]z18697l3936d3424x3e6jk40\83f3 1f0 66f3 1f0
DestroyEntity	z18697x6e12jk40\i13I1i
Declare may put something in the database; Destroy removes it.	z18697x6e6jk40
1. An entity that is destroyed will not be found:
( d: Domain = DomainOf[e]; name: ROPE = NameOf[e]; DestroyEntity[e] ) THEN
DeclareEntity[d, name, OldOnly] ~ NILz18697l3936d3424x3e6jk40\157f3 1f0
2. All relships that reference an entity are destroyed when the entity is destroyed:	
(SetF[rship, attr, e]; DestroyEntity[e]) THEN Null[rship] ~ TRUEz18697l3936d3424x3e6jk40\144f3 1f0
3. Once destroyed, an entity becomes Null:	
(DestroyEntity[e]) THEN Null[e] ~ TRUE
(DestroyEntity[e1]) THEN Eq[e1, e2] ~ Null[e2]z18697l3936d3424x3e6jk40\76f3 1f0 42f3 1f0
4. Destroy doesn't work on NIL or null arguments (can't destroy the same entity twice):	
DestroyEntity[NIL] ~ SIGNAL Error[NILArgument]
IF Null[e] THEN DestroyEntity[e] ~
IF Null[e] THEN SIGNAL Error[NullifiedArgument]z18697l3936d3424x3e6jk40\108f3 1f0 60f3 1f0
DomainSubset	z18697x6e12jk40\i12I1i
DomainSubset returns an EntitySet that, if cycled through using NextEntity, contains all of the entities in the domain having names in the specified range, and only those entities.	z18697x6e12jk40
1. DomainSubset finds only those entities having names between low and high:	
( es: EntitySet = DomainSubset[d, low, high];
  e: Entity = DeclareEntity[d, name, NewOnly] ) THEN
DomainSubset[d, low, high] ~
IF name < low OR name > high THEN es ELSE DomainSubset[d, low, high]z18697l3936d3424x3e6jk40\204f3 1f0
2. DomainSubset finds all those entities having names between low and high:	
( e: Entity = DeclareEntity[d, name, NewOnly] ) THEN
name >= low AND name <= high ~
{ es: EntitySet = DomainSubset[d, low, high];
  FOR next: Entity _ NextEntity[es], NextEntity[es] UNTIL next = NIL DO
    IF Eq[next, e] THEN {ReleaseEntitySet[es]; RETURN[TRUE]}
  ENDLOOP;
  ReleaseEntitySet[es]; RETURN[FALSE] }z18697l3936d3424x3e6jk40\159f3 1f0
Equality of entities	z18697x6e12jk40\i20I
Two entities are equal iff they are both null or their names are the same and they are in the same domain.	z18697x6e12jk40
	Eq[e1, e2] ~
	{ IF Null[e1] OR Null[e2] THEN RETURN[ Null[e1] AND Null[e2] ];
	  RETURN[ Rope.Equal[NameOf[e1], NameOf[e2]] AND
	   Eq[DomainOf[e1], DomainOf[e2]]] }z18697x3e12jk40\12f3 1f0
Basic Operations on Relationships	z18697x6e12jk40\i33I
Relationships are tuples; the basic operations on relationships include setting and fetching the values of fields and searching the database for all tuples whose fields have values in specified ranges.  The operations that manipulate relationships include:	
	DeclareRelship -- add (or look up) a relationship in a particular relation
	DestroyRelship -- remove a relationship from a relation
	RelationOf -- give the relation of a relationship
	Eq -- compare two relationships
	Null -- has a relationship been destroyed?
	RelationSubset -- produce the subset of a relation with fields in a given range of values
	NextRelship -- sequence through a relationship set
	ReleaseEntitySet -- free storage used by a relationship set (affects performance only)z18697x6e6jk40
Unlike entities, it is possible to have the several tuples in the database with the same set of field values. (One can protect against this by declaring some of the attributes for a relation to be keys.  Then checking is performed when declaring new relationships or setting the fields of existing relationships to guarantee that no other tuple exists with the same value for a key attribute.  The equations given below ignore this additional complexity.)  Allowing multiple tuples with the same values appears in the lack of an equation of the form "DeclareRelship followed by DeclareRelship with the same arguments and version OldOnly fails."	z18697x6e6jk40
DeclareRelship	z18697x6e12jk40\i
Most of these equations closely parallel the specification of DeclareEntity.	z18697x6e6jk40\76i1I
1. Declare produces a relationship with the proper values for each specified field:	
( init: AttributeValueList = LIST[ [a1, v1], ..., [an, vn] ];
  rs: Entity = DeclareRelship[r, init] ) THEN GetF[ rs, ai ] ~ viz18697l3936d3424x3e6jk40\83i1I124f3 1f0
2. Declare NewOrOld is a convenience:	
DeclareRelship[r, list, NewOrOld] ~
{ rs: DeclareRelship[r, list, OldOnly];
  IF rs = NIL THEN RETURN[DeclareRelship[r, list, NewOnly]] ELSE RETURN[rs] }z18697l3936d3424x3e6jk40\37i1I35f3 1f0
3. Again, Declare OldOnly is the same as the subset operation    this time, though, it
may fail because of a multiple match:	
DeclareRelship[r, list, OldOnly] ~
{ rset: RelshipSet = RelationSubset[r, list];
  rs: Relship = NextRelship[rs];
   IF NextRelship[rset] = NIL THEN { ReleaseRelshipSet[rs]; RETURN[rs] }
   ELSE { ReleaseRelshipSet[rset]; SIGNAL Error[MultipleMatch] } }z18697l3936d3424x3e6jk40\62o4u2o0U60i1I34f3 1f0
4. Declare doesn't work on system domains:	
DeclareRelship[aRelation, list] ~ SIGNAL Error[ImplicitSchemaUpdate]
DeclareRelship[aType, list] ~ SIGNAL Error[ImplicitSchemaUpdate]
DeclareRelship[aUniqueness, list] ~ SIGNAL Error[ImplicitSchemaUpdate]
DeclareRelship[aLength, list] ~ SIGNAL Error[ImplicitSchemaUpdate]
DeclareRelship[aLink, list] ~ SIGNAL Error[ImplicitSchemaUpdate]
DeclareRelship[dSubType, list] ~ SIGNAL Error[ImplicitSchemaUpdate]z18697l3936d3424x3e6jk40\42i1I33f3 1f0 64f3 1f0 70f3 1f0 66f3 1f0 64f3 1f0 67f3 1f0
5. DeclareEntity doesn't work for NIL or null arguments:	
DeclareRelship[NIL, list] ~ SIGNAL Error[NILArgument]
IF Null[r] THEN DeclareRelship[r, list] ~
IF Null[r] THEN SIGNAL Error[NullifiedArgument]z18697l3936d3424x3e6jk40\56i1I27f3 1f0 67f3 1f0
DestroyEntity	z18697x6e6jk40\i14I
Because duplicates are allowed, the effect of Destroy is somewhat different.  Declaring a relship NewOnly and destroying it has no effect if the relation is in the schema (note that the initialization of the fields of the relship is described below as applications of SetF).	z18697x6e6jk40\274i1I
1. Destroying a newly created relationship has no effect:	
{ rs: Relship = DeclareRelship[r, [], NewOnly]; DestroyRelship[rs] } ~ 
[] _ DeclareRelation[ NameOf[r], SegmentOf[r], OldOnly ]z18697l3936d3424x3e6jk40\57i1I70f3 1f0
2. If an existing relationship is destroyed, then it will not be found:	
( rs: Relship = DeclareRelship[r, list, OldOnly]; DestroyRelship[rs] ) THEN
DeclareRelship[r, list, OldOnly] ~  NILz18697l3936d3424x3e6jk40\71i1I110f3 1f0
3. Once destroyed, an relationship becomes Null:	
(DestroyRelship[rs]) THEN Null[rs] ~ TRUE
(DestroyRelship[rs1]) THEN Eq[rs1, rs2] ~ Null[rs2]z18697l3936d3424x3e6jk40\48i1I36f3 1f0 46f3 1f0
4. Destroy doesn't work on NIL or null arguments (can't destroy the same entity twice):	
DestroyRelship[NIL] ~ SIGNAL Error[NILArgument]
IF Null[rs] THEN DestroyRelship[rs] ~
IF Null[rs] THEN SIGNAL Error[NullifiedArgument]z18697l3936d3424x3e6jk40\109f3 1f0 63f3 1f0
RelationSubset	z18697x6e6jk40\i14I
RelationSubset returns a RelshipSet that, if cycled through using NextRelship, contains all of the relationships in the relation having field values in the specified ranges.	z18697x6e6jk40
1. RelationSubset finds only relships satisfying the AttributeValueList:	
( init: AttributeValueList = LIST[ [a1, v1], . . ., [an, vn] ]
  search: AttributeValueList = LIST[ [a1, l1, h1], . . ., [an, ln, hn] ];
  rset: RelshipSet = RelationSubset[ r, search ];
  [] _ DeclareRelship[r, init, NewOnly ] ) THEN
  RelationSubset[ r, search ] ~
  IF v1 < l1 OR v1 > h1 OR . . . vm < lm OR vm > hm
  THEN rset ELSE RelationSubset[ r, search ]z18697l3936d3424x3e6jk40\339f3 1f0
2. And RelationSubset finds all relships satisfying the AttributeValueList:	 
( init: AttributeValueList = LIST[ [a1, v1], . . ., [an, vn] ]
  search: AttributeValueList = LIST[ [a1, l1, h1], . . ., [an, ln, hn] ];
  rs: DeclareRelship[r, init, NewOnly];
  rset: RelshipSet = RelationSubset[ r, search ] ) THEN
  v1 >= l1 AND v1 <= h1 AND . . . vm >= lm AND vm <= hm ~
   { FOR next: Relship _ NextRelship[rs], NextRelship[rs] UNTIL next = NIL DO
    IF Eq[ next, rs ] THEN { ReleaseRelshipSet[rs]; RETURN[TRUE] }
    ENDLOOP;
   ReleaseRelshipSet[rs]; RETURN[FALSE] }z18697l3936d3424x3e6jk40\367f3 1f0
SetF and GetF	z18697x6e6jk80\i13I
SetF changes the fields of a tuple, GetF reads them.  Here are also the axioms that describe the type-checking performed on assignment.	z18697x6e6jk40
1. Setting the field of one relship changes its value for all equal relships (Eq for relships is essentially alias):	
{ SetF[rship1, attr, val]; RETURN[ GetF[rship2, attr] ] } ~
{ oldVal: Value = GetF[rship2, attr];
   SetF[rship1, attr, val];
   RETURN[ IF Eq[rship1, rship2 ] THEN val ELSE oldVal ] }z18697l3936d3424x3e6jk40\176f3 1f0
2. Setting a field with its current value is a no-op (except for errors):	
SetF[ rship, attr, GetF[rship, attr] ] ~ 
{ IF Eq[RelationOf[rship], aRelation] THEN SIGNAL Error[ImplicitSchemaUpdate];
  IF Eq[RelationOf[rship], aType] THEN SIGNAL Error[ImplicitSchemaUpdate];
  IF Eq[RelationOf[rship], aLength] THEN SIGNAL Error[ImplicitSchemaUpdate];
  IF Eq[RelationOf[rship], aUniqueness] THEN SIGNAL Error[ImplicitSchemaUpdate];
  IF Eq[RelationOf[rship], aLink] THEN SIGNAL Error[ImplicitSchemaUpdate];
  IF Eq[RelationOf[rship], ifIndex] THEN SIGNAL Error[ImplicitSchemaUpdate];
  IF Eq[RelationOf[rship], ifAttribute] THEN SIGNAL Error[ImplicitSchemaUpdate];
  [] _ GetF[rship, attr] }z18697l3936d3424x3e6jk40\114f3 1f0
3. Declare NewOnly can be defined in terms of setting the fields one at a time:	
DeclareRelship[ r, LIST[ [a1, v1], . . ., [an, vn] ], NewOnly ] ~
{ rship: Relship = DeclareRelship[ r, [], NewOnly ];
   SetF[ rship, a1, v1 ]; . . .; SetF[ rship, an, vn ]; RETURN[rship] }z18697l3936d3424x3e6jk40\145f3 1f0
4. GetF fails if the attribute belongs to the wrong relation:	
[] _ GetF[rship, attr] ~
{ IF rship = NIL OR attr = NIL THEN SIGNAL Error[NILArgument];
  IF Null[rship] OR Null[attr] THEN SIGNAL Error[NullifiedArgument];
  { rel1: Relation = RelationOf[rship];
     rel2: Relation = V2E[ GetP[ e: attr, aIs: aRelationIs, aOf: aRelationOf ] ];
     IF NOT Eq[rel1, rel2] THEN SIGNAL Error[ IllegalAttribute ] } }z18697l3936d3424x3e6jk40\86f3 1f0
The type-checking that goes on when a SetF is performed is fairly straightforward:  If the value to be assigned is from one of the primitive types, then the type of the attribute (found in the aType relation) must be identical.  In the case of assigning entity values, the domain of the value must be a subtype of the domain that is the type of the attribute.  We define this by a set of similar equations for each of the primitive types and one for the entity-valued case.	z18697x6e6jk40
5. Integer type-checking:	
{ rship: Relship = DeclareRelship[r, [], NewOnly];
   SetF[ rship, attr, I2V[integer] ]; DestroyRelship[rship] } ~
{ [] _ GetF[rship, attr];
  { type: Entity = V2E[ GetP[ e: attr, aIs: aTypeIs, aOf: aTypeOf ] ];
     IF NOT Eq[type, IntType] THEN SIGNAL Error[MismatchedAttributeValueType] }}z18697l3936d3424x3e6jk40\140f3 1f0
6. Boolean type-checking:	
{ rship: Relship = DeclareRelship[r, [], NewOnly];
   SetF[ rship, attr, B2V[boolean] ]; DestroyRelship[rship] } ~
{ [] _ GetF[rship, attr];
   { type: Entity = V2E[ GetP[ e: attr, aIs: aTypeIs, aOf: aTypeOf ] ];
     IF NOT Eq[type, BoolType] THEN SIGNAL Error[MismatchedAttributeValueType] }}z18697l3936d3424x3e6jk40\140f3 1f0
 7. String type-checking:	
{ rship: Relship = DeclareRelship[r, [], NewOnly];
   SetF[ rship, attr, S2V[string] ]; DestroyRelship[rship] } ~
{ [] _ GetF[rship, attr];
   { type: Entity = V2E[ GetP[ e: attr, aIs: aTypeIs, aOf: aTypeOf ] ];
     IF NOT Eq[type, StringType] THEN SIGNAL Error[MismatchedAttributeValueType] }}z18697l3936d3424x3e6jk40\139f3 1f0
 8. Time type-checking:	
{ rship: Relship = DeclareRelship[r, [], NewOnly];
   SetF[ rship, attr, T2V[time] ]; DestroyRelship[rship] } ~
{ [] _ GetF[rship, attr];
   { type: Entity = V2E[ GetP[ e: attr, aIs: aTypeIs, aOf: aTypeOf ] ];
     IF NOT Eq[type, TimeType] THEN SIGNAL Error[MismatchedAttributeValueType] }}z18697l3936d3424x3e6jk40\135f3 1f0
9. Entity type-checking (AnyDomainType is a wild card):	
{ rship: Relship = DeclareRelship[r, [], NewOnly];
   SetF[ rship, attr, E2V[entity] ]; DestroyRelship[rship] } ~
{ [] _ GetF[rship, attr];
   { type: Entity = V2E[ GetP[ e: attr, aIs: aTypeIs, aOf: aTypeOf ] ];
     IF NOT (Eq[type, AnyDomainType] OR SubType[DomainOf[entity], type])
     THEN SIGNAL Error[MismatchedAttributeValueType] }}z18697l3936d3424x3e6jk40\169f3 1f0
RelationOf	z18697x6e6jk40\i10I
RelationOf simply gives the relation of a relationship.	z18697x6e6jk40
    RelationOf[ DeclareRelship[ r, list ], NewOrOld ] ~
    { [] _ DeclareRelship[ r, list, NewOrOld ]; RETURN[r] }z18697x2e6jk40\54f3 1f0
Operations on the database schema	z18697x6e12jk40\i33I
The database schema is stored in a set of system domains and relations.  The operations on these objects include:	
	DeclareDomain -- add (or look up) a domain
	DeclareRelation -- add (or look up) a relation
	DeclareAttribute -- add (or look up) a field name of a relation
	DestroyDomain -- destroy a domain (and all of its entities)
	DestroyRelation -- destroy a relation (and all of its relationships)
	DeclareSubType -- define one domain to be a subtype of another
	DestroySubType -- remove the two domains from the dSubType relationz18697x6e6jk40
These operations behave much like DeclareEntity, DeclareRelship, DestroyEntity and DestroyRelship; it's just that they work on the system domains and relations.	z18697x6e6jk40
DeclareDomain/DestroyDomain	z18697x6e12jk40\i27I1i
1. DeclareDomain adds a new (empty) domain:	
( d: Domain = DeclareDomain[ name, segment, NewOnly ] ) THEN
{ es: EntitySet = DomainSubset[d, NIL];
   e: Entity = NextEntity[es];
   ReleaseEntitySet[es]; RETURN[s] } ~ NILz18697l3936d3424x3e6jk40\214f3 1f0
2. Again, NewOrOld is a convenience:	
DeclareDomain[name, segment, NewOrOld] ~
{ d: Domain = DeclareDomain[name, segment, OldOnly];
  IF d = NIL THEN RETURN[DeclareDomain[name, segment, NewOnly]]
  ELSE RETURN[d] }z18697l3936d3424x3e6jk40\77f3 1f0
3. Declare OldOnly is the same as domain subset on DomainDomain:	
DeclareDomain[name, segment, OldOnly] ~
{ es: EntitySet = DomainSubset[d: DomainDomain,
       lowName: name, searchSegment: segment];
   e: Entity = NextEntity[es]; ReleaseEntitySet[es]; RETURN[e] }z18697l3936d3424x3e6jk40\104f3 1f0
4. Declare NewOnly fails if the entity already exists:	
([] _ DeclareDomain[name, segment, NewOrOld]) THEN
DeclareDomain[name, segment, NewOnly] ~ SIGNAL Error[AlreadyExists]z18697l3936d3424x3e6jk40\145f3 1f0
5. Declare NewOnly changes DomainDomain:	
(d: Domain = DeclareDomain[name, segment, NewOnly]) THEN
DeclareDomain[name, segment, OldOnly] ~ dz18697l3936d3424x3e6jk40\137f3 1f0
6. A domain that is destroyed will not be found:	
(name: ROPE = NameOf[d]; seg: Segment = SegmentOf[d]; DestroyDomain[d]) THEN
DeclareDomain[name, segment, OldOnly] ~ NILz18697l3936d3424x3e6jk40\165f3 1f0
7. Destroying a domain causes all of the entities in the domain to be destroyed:	
( es: EntitySet = DomainSubset[d, NIL]; DestroyDomain[d] ) THEN
{ e: Entity = NextEntity[es]; ReleaseEntitySet[es]; RETURN[e] } ~ NILz18697l3936d3424x3e6jk40\210f3 1f0
8. Destroying a domain causes entities to become Null:	
( e: Entity = DeclareEntity[d, name]; DestroyDomain[d] ) THEN
Null[e] ~ TRUEz18697l3936d3424x3e6jk40\126f3 1f0
9. Destroying a domain causes relationships that reference it to be destroyed:	
( SetF[rship, attr, e]; DestroyDomain[d] ) THEN Null[rship] ~ TRUEz18697l3936d3424x3e6jk40\140f3 1f0
10. Destroy doesn't work on NIL or null arguments (can't destroy the domain twice):	
DestroyDomain[NIL] ~ SIGNAL Error[NILArgument]
IF Null[d] THEN DestroyDomain[d] ~
IF Null[d] THEN SIGNAL Error[NullifiedArgument]z18697l3936d3424x3e6jk40\104f3 1f0 60f3 1f0
DeclareRelation/DestroyRelation	z18697x6e12jk80\i31I1i
1. DeclareRelation adds a new (empty) relation:	
( r: Relation = DeclareRelation[ name, segment, NewOnly ] ) THEN
{ rs: RelshipSet = RelationSubset[r, NIL]; rship: Relation = NextRelship[rs];
   ReleaseRelshipSet[rs]; RETURN[rship] } ~ NILz18697l3936d3424x3e6jk40\234f3 1f0
2. Again, NewOrOld is a convenience:	
DeclareRelation[name, segment, NewOrOld] ~
{ r: Relation = DeclareRelation[name, segment, OldOnly];
  IF r = NIL THEN RETURN[DeclareRelation[name, segment, NewOnly]]
  ELSE RETURN[r] }z18697l3936d3424x3e6jk40\79f3 1f0
3. Declare OldOnly is the same as domain subset on RelationDomain:	
DeclareRelation[name, segment, OldOnly] ~
{ es: EntitySet = DomainSubset[d: RelationDomain,
  lowName: name, searchSegment: segment];
  e: Entity = NextEntity[es]; ReleaseEntitySet[es]; RETURN[e] }z18697l3936d3424x3e6jk40\108f3 1f0
4. Declare NewOnly fails if the entity already exists:	
([] _ DeclareRelation[name, segment, NewOrOld]) THEN
DeclareRelation[name, segment, NewOnly] ~ SIGNAL Error[AlreadyExists]z18697l3936d3424x3e6jk40\149f3 1f0
5. Declare NewOnly changes RelationDomain:	
(r: Relation = DeclareRelation[name, segment, NewOnly]) THEN
DeclareRelation[name, segment, OldOnly] ~ rz18697l3936d3424x3e6jk40\145f3 1f0
6. A relation that is destroyed will not be found:	
(name: ROPE = NameOf[r]; seg: Segment = SegmentOf[r]; DestroyDomain[r]) THEN
DeclareRelation[name, segment, OldOnly] ~ NILz18697l3936d3424x3e6jk40\169f3 1f0
7. Destroying a domain causes all of the relships in the domain to be destroyed:	
( rs: RelshipSet = RelationSubset[r, NIL]; DestroyRelation[r] ) THEN
{ rship: Relation = NextRelship[rs]; ReleaseRelshipSet[rs]; RETURN[rship] } ~ NILz18697l3936d3424x3e6jk40\227f3 1f0
8. Destroying a domain causes relships to become Null:	
( rship: Relation = DeclareRelship[r, [], NewOnly]; DestroyRelation[r] ) THEN
  Null[rship] ~ TRUEz18697l3936d3424x3e6jk40\148f3 1f0
9. Destroy doesn't work on NIL or null arguments (can't destroy the relation twice):	
DestroyRelation[NIL] ~ SIGNAL Error[NILArgument]
IF Null[r] THEN DestroyRelation[r] ~ IF Null[r] THEN SIGNAL Error[NullifiedArgument]z18697l3936d3424x3e6jk40\107f3 1f0 62f3 1f0
DeclareAttribute	z18697x6e12jk40\i16I1i
The important properties of DeclareAttribute are the changes made to the system relations aType, aLength, aUniqueness and aLink when a new attribute is declared.  If a type, length, uniqueness or link is specified when the attribute is looked up (Declare with version OldOnly), then these additional arguments are checked for consistency with the values stored in the relations.  Note that there is no corresponding DestroyAttribute.	z18697x6e6jk40
1. DeclareAttribute adds a new attribute:	
( a: Attribute = DeclareAttribute[r, name, type, uniqueness, length, link, NewOnly] )
THEN DeclareAttribute[r: r, name: name, version: OldOnly] ~ az18697l3936d3424x3e6jk40\187f3 1f0
2. DeclareAttribute changes the aType relation:	
( a: Attribute = DeclareAttribute[r, name, type, uniqueness, length, link, NewOnly] ) THEN
V2E[ GetP[ e: a, aIs: aTypeIs, aOf: aTypeOf ] ] ~ typez18697l3936d3424x3e6jk40\188f3 1f0
3. DeclareAttribute changes the aUniqueness relation:	
( a: Attribute = DeclareAttribute[r, name, type, uniqueness, length, link, NewOnly] ) 
THEN V2I[ GetP[ e: a, aIs: aUniquenessIs, aOf: aUniquenessOf ] ] ~
 LOOPHOLE[uniqueness]z18697l3936d3424x3e6jk40\207f3 1f0
4. DeclareAttribute changes the aLength relation:	
( a: Attribute = DeclareAttribute[r, name, type, uniqueness, length, link, NewOnly] ) 
THEN V2I[ GetP[ e: a, aIs: aLengthIs, aOf: aLengthOf ] ] ~ lengthz18697l3936d3424x3e6jk40\195f3 1f0
5. DeclareAttribute changes the aLink relation:	
( a: Attribute = DeclareAttribute[r, name, type, uniqueness, length, link, NewOnly] ) 
THEN V2B[ GetP[ e: a, aIs: aLinkIs, aOf: aLinkOf ] ] ~ linkz18697l3936d3424x3e6jk40\189f3 1f0
6. Again, NewOrOld is a convenience:	
DeclareAttribute[r, name, type, uniqueness, length, link, NewOrOld] ~
{ a: Attribute = DeclareAttribute[r, name, type, uniqueness, length, link, OldOnly];
  IF a = NIL
  THEN RETURN[DeclareAttribute[r, name, type, uniqueness, length, link, NewOnly]]
  ELSE RETURN[a] }z18697l3936d3424x3e6jk40\106f3 1f0
7. Declare OldOnly is the same as domain subset on AttributeDomain:	
DeclareAttribute[r: r, name: name, version: OldOnly] ~
{ es: EntitySet = DomainSubset[d: AttributeDomain,
   lowName: name, searchSegment: SegmentOf[r]];
   e: Entity = NextEntity[es]; ReleaseEntitySet[es]; RETURN[e] }z18697l3936d3424x3e6jk40\122f3 1f0
8. Declare OldOnly checks any supplied type, length, link, uniqueness:	
( a: Attribute = DeclareAttribute[r, name, type, uniqueness, length, link, NewOnly] ) 
THEN DeclareAttribute[r: r, name: name, type: type', version: OldOnly] ~
IF NOT Eq[type', type] THEN SIGNAL Error[MismatchedExistingAttribute]
ELSE DeclareAttribute[r: r, name: name, version: OldOnly]

( a: Attribute = DeclareAttribute[r, name, type, uniqueness, length, link, NewOnly] ) 
THEN DeclareAttribute[r: r, name: name, uniqueness: uniqueness', version: OldOnly] 
~ IF NOT uniqueness = uniqueness' THEN
  SIGNAL Error[MismatchedExistingAttribute]
  ELSE DeclareAttribute[r: r, name: name, version: OldOnly]

( a: Attribute = DeclareAttribute[r, name, type, uniqueness, length, link, NewOnly] ) 
THEN DeclareAttribute[r: r, name: name, length: length', version: OldOnly] ~
IF NOT length = length' THEN SIGNAL Error[MismatchedExistingAttribute]
ELSE DeclareAttribute[r: r, name: name, version: OldOnly]

( a: Attribute = DeclareAttribute[r, name, type, uniqueness, length, link, NewOnly] ) 
THEN DeclareAttribute[r: r, name: name, link: link', version: OldOnly] ~
IF NOT link = link' THEN SIGNAL Error[MismatchedExistingAttribute]
ELSE DeclareAttribute[r: r, name: name, version: OldOnly]z18697l3936d3424x3e6jk40\230f3 1f0 301f3 1f0 305f3 1f0 289f3 1f0
9. Declare NewOnly fails if the entity already exists:	
([] _ DeclareAttribute[r, name, type, uniqueness, length, link, NewOrOld]) THEN
DeclareAttribute[r, name, type, uniqueness, length, link, NewOnly] ~
SIGNAL Error[AlreadyExists]z18697l3936d3424x3e6jk40\203f3 1f0
10. Declare doesn't work on NIL or null arguments:	
DeclareAttribute[NIL, name, type, uniqueness, length, link] ~
SIGNAL Error[NILArgument]
IF Null[r] THEN DeclareAttribute[r, name, type, uniqueness, length, link] ~
IF Null[r] THEN SIGNAL Error[NILArgument]
z18697l3936d3424x3e6jk40\112f3 1f0 101f3 1f0

Index of common terms	z18697x6e36jk48\f5b23f0B1f5b

attribute:  column of relation	6, 34, 57, 59
augments:  mechanism for encapsulating updates	21, 69
basic operations:  DeclareEntity, GetF, etc.	10, 68, 81
caching data schema:  used in implementation	77
changing entity names	16, 39
conceptual data model	5
data independence	5
data model:  type mechanism DBMS provides	1, 5
data schema:  types in a particular database	1, 11
datatype:  type of datum	6, 27
datum:  string, integer, etc.	5, 27
domain:  type of entity	6
entity:  database representative of an object	5, 27, 57, 75
entity/relationship distinction	59, 60
entity/datum distinction	5, 57
errors:  generated by illegal operations	45
external entity:  real world object	8
functionally ireducible:  normal form	18, 65
indices, B-tree:  used in implementation	35, 48
internal entity:  we use "entity" to mean this	9
irreducible:  normal form	18, 65
key:  unique attributes of a relation	9, 34, 64
links and colocation:  connecting entities & relationships	35, 78
lists and sets:  representation in our model	49, 62
name:  of an entity	9, 63
normalization:  of relations	16, 51, 65
physical data model	5, 74
properties:  simulated "attributes" of entities	14, 9, 36, 39, 59
query operations:  DomainSubset, RelationSubset	11, 39, 68, 83
referential integrity:  reason for entities	57
relation:  type of relationship	6, 34, 57
relational data model	1, 9
relationship:  a tuple of entity and datum values	6, 7, 27, 60, 75
schema declaration operations:  DeclareDomain, etc.	12, 32
segments:  mechanism for separating databases	18, 69
simplicity and utility:  criteria for data model choice	4
surrogate relation optimization	80
system entities, domains, relations	11, 43
transaction and segment operations	29
translucent attributes:  accessing attributes as strings	15, 38
type hierarchy:  domains and subdomains	6, 28, 66
undefined values:  attributes never assigned	38
update anomaly:  reason for normalization	17
value:  an entity or datum	6, 76
views:  relations that are not stored	24, 69
z18697x2e6jk40(0,12224)\31u1U60u1U51u1U55u1U24u1U28u1U19u1U43u1U49u1U30u1U35u1U29u1U47u1U45u1U31u1U46u1U38u1U39u1U47u1U53u1U27u1U44u1U68u1U51u1U26u1U34u1U30u1U53u1U65u1U58u1U34u1U31u1U54u1U68u1U52u1U62u1U33u1U38u1U41u1U59u1U46u1U54u1U44u1U29u1U43u1U
z18697x6e6jk40(2116)