Cypress Database System DocumentationR. G. G. CattellLast updated June 13, 1983This document describes the Cypress system, and is aimed at potential writers of databaseapplications in the Cedar programming environment. It should be accurate as of the dateabove, and is recommended as better documentation than CSL Report 83-4, from which itwas derived. Suggestions are welcomed on both the design of Cypress and its exposition inthis document. We will assume little knowledge of database systems, and little knowledge ofCedar. We will not explain the motivation for this particular design of Cypress; see the CSLReport for that. You should also consult the documentation for database tools not describedhere; see a database wizard for details.TABLE OF CONTENTS1.Introduction12.Cypress data model concepts32.1Data independence2.2Basic primitives2.3Names and keys2.4Basic operations2.5Aggregate operations2.6Convenience operations2.7Normalization2.8Segments3.Model level interface193.1Types3.2Transactions and segments3.3Data schema definition3.4Basic operations3.5Query operations3.6System domains and relations3.7Errors4. Application example394.1A database application4.2Schema design4.3Example program ^p% Y)qX W rF Rs; QL O`6 M)1 LY JjY H!; G(!BBti>u 8@<X8@;! 9! 8! 6! 5! 3! 2! 0! .8@,! +i! )! (`! &! %X! #! " 8@ ? ` ` 7 ` >QC@11. IntroductionCypress was motivated by the need for database management facilities in Cedar. Its goals are (1)convenience, making it easy to build new database applications in Cedar, and (2) reasonableperformance for a wide class of applications. If you are unsure whether an application you have inmind is appropriate, talk to someone who has built one. You should also consult others to see whatauxiliary documentation and folklore is available.The conceptual data structure provided by a database system, analogous to the Mesa type system, iscalled a data model. The data model specifies how data may be structured and accessed; thus thedata model is what you need to know in order to use the system. The Cypress data modeldescribed herein includes features that are accepted in some form in a number of models in theliterature, particularly those that seemed most useful for database applications we envision in CSL.The data model is described conceptually in Section 2. In Section 3 we describe the Cedar interfaceto Cypress: DB.mesa. Finally, Section 4 provides a simple example of Cypress use. We cover onlythe abstract model and the DB interface, not its implementation or rationale. The reader interestedin these should consult CSL Report 83-4. A set of formal axioms for the model can also be foundthere.Clients interested in tools for examining or modifying databases, either as an end-user or fordebugging an application program, should consult the database tools documentation:[Indigo]Documentation> SquirrelDoc.tioga, .press.HYfp \Tq XxpS VD= TM QO O2 K&< Ir pK GbD E-M B#A ?T <F : X 8R 6K 2p^ 0; F .; -=:K32. Cypress data model conceptsIn this section, we give an informal description of the Cypress data model. We describe theparticulars of the Cedar interface in Section 3. 2.1 Data independenceWe deal here with the conceptual data model: the logical primitives for data access and data typedefinition. This should be carefully distinguished from the physical data storage and accessmechansisms. The physical representation of data is hidden as much as possible from the databaseclient to facilitate data independence, the guarantee that a user's program will continue to work(perhaps with a change in efficiency) even though the physical data representation is redesigned. For any particular database using our conceptual data model, the actual specification of the types ofdata in the database, using the primitives the model provides, is termed the data schema. Note thata mapping must be provided between the conceptual data model and the physical representation,either automatically or with further instruction from the client; we will do some of both. Thelogical to physical mapping is intimately associated with the performance of the database system asviewed by the user performing operations at the conceptual level.2.2 Basic primitivesThree basic primitives are defined in the model: an entity, datum, and relationship.An entity represents an abstract or concrete object in the world: a person, an organization, adocument, a product, an event. In programming languages and knowledge representation entitieshave variously been referred to as atoms, symbols, and nodes. A datum, unlike an entity, representsliteral information such as times, weights, part names, or phone numbers. Character strings andintegers are possible datum types.It is a policy decision whether something is represented as an entity or merely a datum: e.g., anemployee's spouse may be represented in a database system as a datum (the spouse's name), or thespouse may be an entity in itself. The database system provides a higher level of logical integritychecking for entities than for datum values, as we will see later: unique entity identifiers, checks onentity types, and removal of dependent data upon entity deletion. We shall discuss theentity/datum choice further in Section 4.2.We will use the term value to refer to something that can be either a datum or an entity. In manyprogramming languages, there is no reason to distinguish entity values from datum values. Indeed,<\OpT-qPQp?N1GrCpspA<!? tpP=Msp;;a7=505Ms p 2";0T .k`,7A%r"p5s ps p(A<");EV"{spSFD  Z hEt+sp <d?# =]iCYPRESS DOCUMENTATION4most of the Cypress operations deal with any kind of value, and some make it transparent to thecaller whether an entity or datum value is involved. The transparent case makes relationaloperations possible in our model, as we will see in Section 2.5.A relationship is a tuple whose elements are [entity or datum] values. We refer to the elements(fields) of relationships by name instead of position. These names for positions are called attributes.Note that we have separated the representatives of unique objects (entities) from the representationof information about objects (relationships), unlike some object-oriented programming languagesand data models. Therefore an entity is not an "object" (or "record") in the programming languagesense, although entities are representatives of real-world objects. We also define entity types, datum types, and relationship types. These are called domains,datatypes, and relations, respectively. We make use of these three types through one fundamentaltype constraint: every relationship in a relation has the same attributes, and the values associatedwith each attribute must be from a pre-specified domain or datatype. One might think of a relationas a "record type" in a programming language, although relations permit more powerful operationsthan record types.As an example, consider a member relation that specifies that a given person is a member of a givenorganization with a given job title, as in the following figure. The person and organization might beentities, while the title might be a string datum. We relax the fundamental type constraintsomewhat in allowing a lattice of types of domains: a particular value may then belong to the pre-specified domain or one of its sub-domains. For example, one could be a member of a University,a Company, or any other type of Organization one chooses to define. Other relations, e.g. an"offers-course" relation, might apply only to a University.<==BBpB-.C@CtlJeC)+zRD@:p Cǿ`3dDs?Cc`EufdDpC0tCCC6@C?9C|+5޽ yBDrCtlGbpEd\Dm"CPмa@B@CBÐueCClDhC,B"BP;>%}%~Dq#Cڂ%|-d CZBCW2D@D@CQ2@/ CEDrClC -RdC`CQ2+ACh"ClCCBCK27AD@D`-d CZ,B"3>BmCڂ%~@|CڂCڃCHB";>B] Cl@DbC -cCHBhpBClB CECClG,CZBPB%}CڂDq"CZ%~%|-cBBDD@D@C`0/BCCDrl -cw+ABD $DbCBCZ7ABDD@D`-c:,BmB%}%~Dq#Cڂ%|CHCH*B]BClBCCg ClG-co BBm CEDrClC CZB BB]CڂCڂCZ%~Cڃ-b,BBAD@D`C`A_BBACClDhC-RbBBB Cl@DbC CZ,BBB/D@D@-bBBpB%}CڂDq"CZ%~%|CH*BpBCh"ClCC,cCHCBBm3?CDrl BBB];@Cڂ%~@|CڂCڃ,c:,CZCW4AD@D`A_CQ3AClB CECClGJohn Smith]EϕEu Bk@BBpB-.CCtlLeC)+zRD@:p Cǿ`3dDs?C`#a4EufdDpC0tCCC6@C?9C|+5޽ yBDrCtl"bEd\Dm"CPмa@B@CBÐueCClDhC,B"BP;>%}%~Dq#Cڂ%|&ud)CZBCW2D@D@CQ2@/ CEDrClC &d7C`CQ2+ACh"ClCCBCK27AD@D`&d)CZ,B"3>BmCڂ%~@|CڂCڃCHB";>B] Cl@DbC '!dCHBhpBClB CECClG,CZBPB%}CڂDq"CZ%~%|'DcBBDD@D@C`0/BCCDrl 'Rc+ABD $DbCBCZ7ABDD@D`'DcZ,BmB%}%~Dq#Cڂ%|CHCH*B]BClBCCg ClG'!c(o BBm CEDrClC CZB BB]CڂCڂCZ%~Cڃ&c,BBAD@D`C`A_BBACClDhC&bBBB Cl@DbC CZ,BBB/D@D@&ucBBpB%}CڂDq"CZ%~%|CH*BpBCh"ClCC&Cc(CHCBBm3?CDrl BBB];@Cڂ%~@|CڂCڃ& cZ,CZCW4AD@D`A_CQ3AClB CECClG0aD`D`@@D`@CCCD`C@0aC`BCQ4Cl@CCg ClG,BCK4/D@D@0bBCZBpB 3@CڃCڂCZ%~CڃBpB ;@ "DbC0bFCHCHCBBh3>CClDhC,B$BP;>%}%~Dq#Cڂ%|0biCZBCW2D@D@CQ2@/ CEDrClC 12bwC`CQ2+ACh"ClCCBCK27AD@D`1obiCZ,B$3>BmCڂ%~݀|CڂCڃCHB$;>B] Cl@DbC 1bFCHBhpBClD CECClG,CZBPB%~CڂDq"CZ%~%|1bBBDD@D@C`@/BCCDrl 1a+ABD "DbCBCZ7ABDD@D`1a,BmB%}%~Dq#Cڂ%|CHCH*B]BCl@CCg ClG1ahn BBm CEDrClC CZB BB]CڃCڂCZ%~Cڃ1oaE,BBAD@D`C`A_BBACClDhC12a7BBB Cl@DbC CZ,BBB/D@D@0aEBBpB%~CڂDq"CZ%~%|CH*BpBCh"ClCC0ahCH CBBm3?CDrl B BB];@Cڂ%~݀|CڂCڃ0a,CZCW4AD@D`A_CQ3AClD CECClGJohnMaryJohnTom#[D`D`@@D`@CCCD`C@#[C`BCQ4ClBCCg ClG,BCK4/D@D@#\4BCZBrB 3@CڂCڂCZ%} CڃBrB ;@ $DbC#\fCHCHCBBh3=CClDgC,B$BP;=%}%~}Dq#Cڂ%|$\CZBCW2D@D@CQ2@/ CEDrClB $R\C`CQ2+ACh"ClBCBCK27AD@D`$\CZ,B$3=BmCڂ%~|CڂCڃCHB$;=B] Cl@DbC $\fCHBhpBClB CECClG,CZBPB%}CڂDq#@CZ%} %|$\4BBDD@D@C`0/BCCDrl $[+ABD $DbCBCZ7ABDD@D`$[,BmB%}%~}Dq#Cڂ%|CHCH*B]BClBCCg ClG$[n BBm CEDrClB CZB BB]CڂCڂCZ%} Cڃ$[e,BBAD@D`C`A_BBACClDgC$R[WBBB Cl@DbC CZ,BBB/D@D@$[eBBpB%}CڂDq#@CZ%} %|CH*BpBCh"ClBC#[CHCBBm3?CDrl BBB];@Cڂ%~|CڂCڃ#[,CZCW4AD@D`A_CQ3AClB CECClG-r\D`D`@@D`@CCCD`C@-R\C`BCQ4ClBCCg ClG,BCK4/D@D@-`\TBCZBtB 3@CڂCڂCZ%~CڃBtB ;@ $DbC-\CHCHCBBh3>CClDhC,B"BP;>%}%~Dq#Cڂ%|-\CZBCW2D@D@CQ2@/ CEDrClC -\C`CQ2+ACh"ClCCBCK27AD@D`./\CZ,B"3>BmCڂ%~@|CڂCڃCHB";>B] Cl@DbC .a\CHBhpBClB CECClG,CZBPB%}CڂDq"CZ%~%|.\TBBDD@D@C`0/BCCDrl .\+ABD $DbCBCZ7ABDD@D`.[,BmB%}%~Dq#Cڂ%|CHCH*B]BClBCCg ClG.a[o BBm CEDrClC CZB BB]CڂCڂCZ%~Cڃ./[,BBAD@D`C`A_BBACClDhC-[wBBB Cl@DbC CZ,BBB/D@D@-[BBpB%}CڂDq"CZ%~%|CH*BpBCh"ClCC-[CHCBBm3?CDrl BBB];@Cڂ%~@|CڂCڃ-`[,CZCW4AD@D`A_CQ3AClB CECClG7[D`D`@@D`@CCCD`C@7[C`BCQ4Cl@CCg ClG,BCK4/D@D@7\4BCZBpB 3@CڃCڂCZ%~CڃBpB ;@ "DbC8\fCHCHCBBh3>CClDhC,B$BP;>%}%~Dq#Cڂ%|85\CZBCW2D@D@CQ2@/ CEDrClC 8r\C`CQ2+ACh"ClCCBCK27AD@D`8\CZ,B$3>BmCڂ%~݀|CڂCڃCHB$;>B] Cl@DbC 8\fCHBhpBClD CECClG,CZBPB%~CڂDq"CZ%~%|9\4BBDD@D@C`@/BCCDrl 9[+ABD "DbCBCZ7ABDD@D`9[,BmB%}%~Dq#Cڂ%|CHCH*B]BCl@CCg ClG8[n BBm CEDrClC CZB BB]CڃCڂCZ%~Cڃ8[e,BBAD@D`C`A_BBACClDhC8r[WBBB Cl@DbC CZ,BBB/D@D@85[eBBpB%~CڂDq"CZ%~%|CH*BpBCh"ClCC8[CH CBBm3?CDrl B BB];@Cڂ%~݀|CڂCڃ7[,CZCW4AD@D`A_CQ3AClD CECClG&pc+޻OH@0>Ba .Dd^CKDmD잒Ba$B*ɀC]C&DAZC]%aiA/+B@CSPH|FD]C}DYDCރd\B7Cs@CLC Cs@$_ڲ=ĪCC%Au34/-DNCV`-C^PD+BWAu M0 CZCDC+@2ECZ$^C޻B~tAw!0 ,DCC,BNGdDx BmDhC>DEHCR(tBG CqCC|R@Cp/N_G"PDCX=༠kBOXD\`CDzEVLAB×CJ~xPCACC뀻CC1aEQ滃:By@ 0ߨC>@CCD:UJA{@CVVbC[D]DBြc4B`rDS߾=ؽBxPCy)HC\C{#cDԩ ,' ?Ȗ,CDh8C>C.5_DDo!໚hN7p4A`C!ြ CCDn벾0Mp.AU@!C\DpCn)!6^lD'H bBdBsC̀C_C$D|NA /ǰ)`*CDrCC!*ZaptFpt pjRajPQsp@jN GjK<%jIj;_3j7+5j5OVspj3Jj0X j.?!j,}_j*I$j&m9j$84(` ]j+7jLEjspC jsp,spjJj{Bj Aspj jBj 6djRj Zj&sp%jd$ M >[{ [w$x 77777777777777777x7777777777777777777777_x77777777777777777x77777777777777777rcr\W/[w9[Wx 77777777777777777x77777777777777777x777777777777777777777777 _%^/r^w6_7#####%[W'd2a 777777 Q;78'sp"5 I37(1sR/>s p"- W*G()1&m r:p&3T[ /+hG/ upup( |tupupClupup+dup% v=\CYPRESS DOCUMENTATION8Five basic operations are defined for relationships:1.DeclareRelationship[relation, list of attribute values]: Returns a relationship with thegiven attribute values in the given relation.2.DestroyRelationship[relationship]: Destroys a relationship.3.RelationOf[relationship]: Returns a relationship's relation.4.GetF[relationship, attribute]: Returns the value associated with the given attribute of thegiven relationship.5.SetF[relationship, attribute, value]: Sets the value of the given relationship attribute.The operations upon relationships recognize a specially-distinguished undefined value for anattribute. Unassigned attributes of a newly-created relationship have this value. A client of the datamodel may retrieve a value with GetF and test whether it equals the distinguished undefined value,and may set a previously defined value to be the distinguished undefined value with SetF.Other "convenience" operations are built on top of the basic operations on entities andrelationships: properties and translucent attributes. They are described in Section 2.6. Althoughthese operations are not essential to the basis of the Cypress model, they do furnish a fundamentallydifferent perspective on the model. They provide a mechanism to associate information directlywith entities (instead of through relationships) and to write programs largely independent ofattribute types.The reader will also note that we have ignored issues of concurrent access and protection in thebasic operations. We will see later that an underlying transaction, file, and protection is associatedwith the relation and domain handles used in the basic operations. This convenience allows us totreat concurrency, protection, and data location orthogonally.2.5 Aggregate operationsThere are two kinds of operations upon domains and relations, the aggregate types in our model:the definition of domains and relations, and queries on domains and relations. We first discusstheir definitions.Schema definitionAs in other database models and a few programming languages, the Cypress model is self-representing: the data schema is stored and accessible as data. Thus application-independent toolscan be written without coded-in knowledge of the types of data and their relationships.ZaptFpt pjR4N`u:p`Lu-Im`u$pFe`up"C]`up+`A)>!`u'p( j:E Fsp j8Sj5upj3)+upj/ !Dj-s psp" j+cQj).3,j&!<j$j CjgjEjL>jrjpBspj 4,j jsjp<jMjdW M >[{CYPRESS DATA MODEL CONCEPTS9Client-defined domains, relations, and attributes are represented by entities. These entities belong tospecial built-in domains, called the system domains:the Domain domain, with one element (entity) per domainthe Attribute domain, with one element per attributethe Relation domain, with one element per relationThere is also a predefined Datatype domain, with pre-defined elements StringType, BoolType, andIntType, called built-in types. We do not allow client-defined datum types at present.Information about domains, relations, and attributes are represented by system relations in which thesystem entities participate. The pre-defined SubType relation is a binary relation between domainsand their subdomains. There are also predefined binary relations that map attributes to informationabout the attributes:aRelation: maps an attribute entity to its relation entity.aType: maps an attribute to its type entity (a domain or a built-in type)aUniqueness: maps an attribute entity to {TRUE, FALSE}, depending whether it is partof a key of its relation. We are assuming only one key per relation, here; our implementation relaxes thisassumption in the case of single-attribute keys. The following diagram graphically illustrates a segment of a data schema describing the memberrelation and several domains. The left side of the figure shows two subdomains of Organization,(Company and University), and the right shows the types and uniqueness properties of the memberrelation's attributes memberOf, memberIs, and memberAs.<==CClDhC,B$BP;>%}%~Dq#Cڂ%|CYiCZBCW2D@D@CQ2@/ CEDrClC CRYwC`CQ2+ACh"ClCCBCK27AD@D`CYiCZ,B$3>BmCڂ%~݀|CڂCڃCHB$;>B] Cl@DbC CYFCHBhpBClD CECClG,CZBPB%~CڂDq"CZ%~%|CYBBDD@D@C`@/BCCDrl CX+ABD "DbCBCZ7ABDD@D`CX,BmB%}%~Dq#Cڂ%|CHCH*B]BCl@CCg ClGCXhn BBm CEDrClC CZB BB]CڃCڂCZ%~CڃCXE,BBAD@D`C`A_BBACClDhCCRX7BBB Cl@DbC CZ,BBB/D@D@CXEBBpB%~CڂDq"CZ%~%|CH*BpBCh"ClCCBXhCH CBBm3?CDrl B BB];@Cڂ%~݀|CڂCڃBX,CZCW4AD@D`A_CQ3AClD CECClG+dWD`D`@@D`@CCCD`C@+dWC`BCQ4ClBCCg ClG,BCK4/D@D@+dBCZBtB 3@CڂCڂCZ%~CڃBtB ;@ $DbC,dCHCHCBBh3>CClDhC,B"BP;>%}%~Dq#Cڂ%|,5dCZBCW2D@D@CQ2@/ CEDrClC ,rdC`CQ2+ACh"ClCCBCK27AD@D`,dCZ,B"3>BmCڂ%~@|CڂCڃCHB";>B] Cl@DbC ,dCHBhpBClB CECClG,CZBPB%}CڂDq"CZ%~%|-dBBDD@D@C`0/BCCDrl -dW+ABD $DbCBCZ7ABDD@D`-d,BmB%}%~Dq#Cڂ%|CHCH*B]BClBCCg ClG,co BBm CEDrClC CZB BB]CڂCڂCZ%~Cڃ,c,BBAD@D`C`A_BBACClDhC,rcBBB Cl@DbC CZ,BBB/D@D@,5cBBpB%}CڂDq"CZ%~%|CH*BpBCh"ClCC,cCHCBBm3?CDrl BBB];@Cڂ%~@|CڂCڃ+d,CZCW4AD@D`A_CQ3AClB CECClGmember,RUD`D`@@D`@CCCD`C@,2UC`BCQ4ClBCCg ClG,BCK4/D@D@,@V4BCZBtB 3@CڂCڂCZ݀%~CڂBtB ;@ $DbC,cVfCHCHCBBh3>CClDhC,B"BP;>%}%~Dq"Cڂ%},VCZBCW2D@D@CQ2@/ CEDrClC ,VC`CQ2+ACh"ClCCBCK27AD@D`-VCZ,B"3>BmCڂ%}@CڂCځCHB";>B] Cl@DbC -AVfCHBhpBClB CECClG,CZBPB%}CڃDq"CZ%~%~-dV4BBDD@D@C`0/BCCDrl -rU+ABD $DbCBCZ7ABDD@D`-dU,BmB%}%~Dq"Cڂ%}CHCH*B]BClBCCg ClG-AUo BBm CEDrClC CZB BB]CڂCڂCZ݀%~Cڂ-Ue,BBAD@D`C`A_BBACClDhC,UWBBB Cl@DbC CZ,BBB/D@D@,UeBBpB%}CڃDq"CZ%~%~CH*BpBCh"ClCC,cUCHCBBm3?CDrl BBB];@Cڂ%}@CڂCځ,@U,CZCW4AD@D`A_CQ3AClB CECClG*r]7D`D`@@D`@CCCD`C@*R]7C`BCQ4ClBCCg ClG,BCK4/D@D@*`]tBCZBtB 3@CڂCڂCZ%~CڃBtB ;@ $DbC*]CHCHCBBh3>CClDhC,B"BP;>%}%~Dq#Cڂ%|*]CZBCW2D@D@CQ2@/ CEDrClC *]C`CQ2+ACh"ClCCBCK27AD@D`+/]CZ,B"3>BmCڂ%~@|CڂCڃCHB";>B] Cl@DbC +a]CHBhpBClB CECClG,CZBPB%}CڂDq"CZ%~%|+]tBBDD@D@C`0/BCCDrl +]7+ABD $DbCBCZ7ABDD@D`+\,BmB%}%~Dq#Cڂ%|CHCH*B]BClBCCg ClG+a\o BBm CEDrClC CZB BB]CڂCڂCZ%~Cڃ+/\,BBAD@D`C`A_BBACClDhC*\BBB Cl@DbC CZ,BBB/D@D@*\BBpB%}CڂDq"CZ%~%|CH*BpBCh"ClCC*\CHCBBm3?CDrl BBB];@Cڂ%~@|CڂCڃ*`\,CZCW4AD@D`A_CQ3AClB CECClG2`D`D`@@D`@CCCD`C@`C`BCQ4ClBCCg ClG,BCK4/D@D@ `BCZBrB 3@CڂCڂCZ%} CڃBrB ;@ $DbCCa&CHCHCBBh3=CClDgC,B$BP;=%}%~}Dq#Cڂ%|uaICZBCW2D@D@CQ2@/ CEDrClB aWC`CQ2+ACh"ClBCBCK27AD@D`aICZ,B$3=BmCڂ%~|CڂCڃCHB$;=B] Cl@DbC !a&CHBhpBClB CECClG,CZBPB%}CڂDq#@CZ%} %|D`BBDD@D@C`0/BCCDrl R`+ABD $DbCBCZ7ABDD@D`D`z,BmB%}%~}Dq#Cڂ%|CHCH*B]BClBCCg ClG!`Hn BBm CEDrClB CZB BB]CڂCڂCZ%} Cڃ`%,BBAD@D`C`A_BBACClDgC`BBB Cl@DbC CZ,BBB/D@D@u`%BBpB%}CڂDq#@CZ%} %|CH*BpBCh"ClBCC`HCHCBBm3?CDrl BBB];@Cڂ%~|CڂCڃ `z,CZCW4AD@D`A_CQ3AClB CECClG;r`7D`D`@@D`@CCCD`C@;R`7C`BCQ4Cl@CCg ClG,BCK4/D@D@;``tBCZBpB 3@CڃCڂCZ%~CڃBpB ;@ "DbC;`CHCHCBBh3>CClDhC,B$BP;>%}%~Dq#Cڂ%|;`CZBCW2D@D@CQ2@/ CEDrClC ;`C`CQ2+ACh"ClCCBCK27AD@D`BmCڂ%~݀|CڂCڃCHB$;>B] Cl@DbC 00BDC,DMB@+1aaC0^)`1O@`dC*C@@&7EI9B@hABs)_@BވCDRa3@Bކ+ ^AQ=n`AҤ5\"ZAv2@CjCAvD8 @̀@n1CD`@1aRelation+dW5НA@܀@!)-CD`@pEɡ:B^BR8pjA޶C@R@RD@&dW>TxB<B`=e8C7DlBEu|DtC8ؼ!PC}/7C@Ҁ]-C#c1Ҽ2nBJн;.@p  CIDqCj/@ DǪrDAV6BX?CCB1t4CD!c+'CKu1W*M4xPDsDCˈ DZDnΗB> 𽡦PCxCj0WCx bj#,CZ?p7!8Bgx"ր(8DqC"ԀDBfD{5BIsAAߓ CVCˈBO4w`CTaRelationDiB/^DGslA%17`?mC=B7CB[A+p3(@W.A DED\u-0]D9Acs9𑽡BoCvtPJCVCwZDP%>7DhECH>$cgC CC@=Cۀ ` ^mDYC `CMCDHECM ^t ZtkdDHCqt ^zB_CpDYpSB_ Z UB"@CnCB sZoCDl3` dSubType R[[D@D@ R[D@D``~]>/H)DrCз`CWCиB"/H`CX ]BZ*_@ DoC$`*`]lCՠC$Cr,6 ۠CՠZYDg3C"ZCC"C2@`C)cm `mCؐ@#h`$CjCؐcA'oCjDqCP#'p`n^Cݓ@(CVpCݔ`@"lCVDpJ`Cj("l^.\FCw;=BXCECw=^CDDr€ 0\CXC` vC\0CC`\+iCDq ` uh+YptpXtptptQZ 2Q$x 77777777777777777x77777777777777777-cx77777777777777777x77777777777777777x77777777777777777x77777777777777777x77777777777777777x77777777777777777RWcW ####5Z ####DRX7 777=2b Ia773bw 7777+R_ 77777!bw 77?r\W 777772] 77,2X ####2Vw 77Z Z__+[=_W##########x77777777777777777rT #### 2\########vVtuCYPRESS DOCUMENTATION10DeclareSubType[superdomain, subdomain]DeclareRelation[name], and for each attribute:DeclareAttribute[name, relation, type, uniqueness].QueriesThe operation RelationSubset[relation, attribute value list] enumerates relationships in a relationsatisfying specified equality constraints on entity-valued attributes and/or range constraints ondatum-valued attributes. For example, RelationSubset might enumerate all of the relationshipsthat reference a particular entity in one attribute and have an integer in the range 23 to 52 inanother.The operation DomainSubset[domain, name range] enumerates entities in a domain. Theenumeration may optionally be sorted by entity name, or restricted to a subset of the entities with aname in a given range.More complex queries can be implemented in terms of DomainSubset and RelationSubset. Afuture implementation will provide a MultiRelationSubset operation to efficiently enumerate singlequeries spanning more than one relation. MultiRelationSubset operates upon a parsedrepresentation of the query language, and produces the same kind of enumeration asRelationSubset. See CSL-83-4 for more details. 2.6 Convenience operationsSome more convenient specialized operations are built upon the basic operations described in theprevious two sections. They implement what we call properties and translucent attributes. Althoughtheoretically speaking these operations add no power to the model, they permit a significantlydifferent perspective on the data access and so should be thought of as part of the model.PropertiesProperties allow the client to treat entities as if they, like relationships, had "attributes." Theyprovide the convenience of treating attributes of relationships that reference an entity as if theywere attributes (or properties) of the entity itself. The property operations are: 1.GetPList[entity, attribute1, attribute2]: Attribute1 and attribute2 must be from the samerelation. Returns the values of attribute1 for all relationships in the relation that referencethe entity via attribute2. Attribute2 may be omitted, in which case it is assumed to be theonly other entity-valued attribute of the relation.[ptFpt p VSu&`Pp VMu3jIsjEp u.p&jCDjA'u p)j?^Jj=)j9M u!p j7Kj4j054u pu pj.%up j+7(8upj)MCNj'cu p"j! rj1pOj4s ps p jP j9!js jpej [j ss p6`upu tu  tu  tpu tp`!utp5`uutuu tup, `d3 M S=\CYPRESS DATA MODEL CONCEPTS112.GetP[entity, attribute1, attribute2]: this is identical to GetPList except exactly onerelationship must reference the entity via attribute2; otherwise an error is generated. GetPalways returns one value.3.SetPList[entity, attribute1, value list, attribute2]: Attribute1 and attribute2 must be fromthe same relation. Destroys any existing relationships whose attribute2 equals the entity,and creates new ones for each value in the list, with attribute1 equal to the value, andattribute2 equal to the entity. Attribute2 can be defaulted as in GetPList.4.SetP[entity, attribute1, value, attribute2]: this is identical to SetPList except it simplyadds a new relationship referencing the entity instead of destroying any existing ones(unless attribute1 is a key of its relation, in which case the existing one must be replaced).Thus the property operations allow information specified through relationships to be treated asproperties of the entity itself, in single operations. The property operations and the operationsdefined in earlier sections may be used interchangeably, as there is only one underlyingrepresentation of information: the relationships. As an example of the use of properties, considerthe following database:<==CClDhC,B"BP;>%}%~Dq#Cڂ%|-[)CZBCW2D@D@CQ2@/ CEDrClC -[7C`CQ2+ACh"ClCCBCK27AD@D`.[)CZ,B"3>BmCڂ%~@|CڂCڃCHB";>B] Cl@DbC .A[CHBhpBClB CECClG,CZBPB%}CڂDq"CZ%~%|.dZBBDD@D@C`0/BCCDrl .rZ+ABD $DbCBCZ7ABDD@D`.dZZ,BmB%}%~Dq#Cڂ%|CHCH*B]BClBCCg ClG.AZ(o BBm CEDrClC CZB BB]CڂCڂCZ%~Cڃ.Z,BBAD@D`C`A_BBACClDhC-YBBB Cl@DbC CZ,BBB/D@D@-ZBBpB%}CڂDq"CZ%~%|CH*BpBCh"ClCC-cZ(CHCBBm3?CDrl BBB];@Cڂ%~@|CڂCڃ-@ZZ,CZCW4AD@D`A_CQ3AClB CECClGB`D`D`@@D`@CCCD`C@A`C`BCQ4Cl@CCg ClG,BCK4/D@D@Ba4BCZBpB 3@CڃCڂCZ%~CڃBpB ;@ "DbCB#afCHCHCBBh3>CClDhC,B$BP;>%}%~Dq#Cڂ%|BUaCZBCW2D@D@CQ2@/ CEDrClC BaC`CQ2+ACh"ClCCBCK27AD@D`BaCZ,B$3>BmCڂ%~݀|CڂCڃCHB$;>B] Cl@DbC CafCHBhpBClD CECClG,CZBPB%~CڂDq"CZ%~%|C$a4BBDD@D@C`@/BCCDrl C2`+ABD "DbCBCZ7ABDD@D`C$`,BmB%}%~Dq#Cڂ%|CHCH*B]BCl@CCg ClGC`n BBm CEDrClC CZB BB]CڃCڂCZ%~CڃB`e,BBAD@D`C`A_BBACClDhCB`WBBB Cl@DbC CZ,BBB/D@D@BU`eBBpB%~CڂDq"CZ%~%|CH*BpBCh"ClCCB#`CH CBBm3?CDrl B BB];@Cڂ%~݀|CڂCڃB`,CZCW4AD@D`A_CQ3AClD CECClGJohn Smith.[1EϕEu BkDBBpB-.CCtlHeC)+zRD@:pנCǿ`3lDs?C3C^EufdDpC0tCCC6C?9C|+5޽ yBDrCtl7'`Ed\Dm"CPмa@B@CBÐte@CJİBRCDs@8\CdPm'~B hAS# `C.x=CъCLC~:DBpA|)C޶DrCD!H@)9F\PDnj,zAACPZxBGȽC+hCwC.DB# B BfB8<UCшDn}C|.vR:.[EE?6GCZC\@3CCMtC3DaA BBHCwDepCeCi[)=6pB\ZpЀCDnCLGЀER DfqCJm輧5@<CrB_0gwCs^}^BPl4 B68 y\C\DqC` xEZ,DɆA*AWAMO&)C/CLD?K@C0$^! E{BW\`9ڨ`l\C[D]DB@[EнI,&ȴC[dCC2: @%*CC1]benB@ Pn ?ϸCWD]@DDJYCm/@ĀPp?G@CC[C'by_DN0# Ax@B`DM DU:2xEtP-P-e6]@5CCXCW@CFcWPCT)@AJM ApDB D^6TE_щ,bB`C(`@C2:B\CcB{k"y@ёAHClD`@EH{AA|߀cWKCg໡AoCr]r[[]r]][D@D@R]D@D`r[[D@D@r[wD@D`[]D@D`[D@D@]wr]wD@D`]D@D@professormembermemberOfmemberIsmemberAs-Z =ucgý?s`C =BODsDCV@EE]5D|%C=1TPCCCM_A(&C)#VN3&0@HTAP@BҸDrCzXDA\C##@lu@AT @ CxCVH=@Cw(V;\0sCllpBDA^JC}DnCKEQ'Ddr4C`8A@A@CpCzX-HCp&0U6VhTPCB՝%C&DeBfoEmDAC⏼@C-AtACFCK>]HCG"TdG3ý}PCuFBxӠHADDD]*'E` RCe8AfA],C[BfpـC\Tw"CBu_D`쿟?'c@B<DO DS'Eo0@`B;@C~;Cှ'ACUwWwWwUwUwUwWwD@D`2UwD@D@WWWWD@D`WD@D@WwUwD@D@WwD@D`UUD@D@UWD@D`34ageageIsageOf$S&SD@D@$SWD@D`2r`7r`D@D@2r`WD@D`$_)_D@D@$_WD@D`+[4ptpXtptpt;[pS6uRtS6u RtS6upupupQ%+uPtQ%p uOpK8uJtK8uJtK8u JK8puJtK8p I>uHvtIpF"uFetFpDuDTtDrpuDTtDpupA(u@tA(u@tA(upup?.(<ugFj<39j9j6"\j3) up%j1u pupj/up3j-QNj+)-j( Rj&Nj" s p>j 1upup jojupupj^$Dj*IspjNu&p%jVj $up(j GjsjpKjup3jd05 M ?Q]#CYPRESS DATA MODEL CONCEPTS13one did. See the description of ChangeName in Section 3.4 for precise semantics in our implementation, however. 2.7 NormalizationA few comments on relational normalization are included here for users who must do their own dataschema design. Others may skip to the next section.A relation is normalized by breaking it into two or more relations of lower order (fewer attributes)to eliminate undesirable dependencies between the attributes. For example, one could define a"publication" relation with three attributes:Publication:PersonBookDateGeorgeBackgammon for Beginners1978JohnBackgammon for Beginners1978MaryHow to Play Chess1981MaryHow to Cheat at Chess1982This relation represents the fact that John and George wrote a book together entitled "Backgammonfor Beginners," published in 1978, and Mary wrote two books on the subject of chess, in 1981 and1982. Alternatively, we could encode the same information in two relations, an author relation and apublication-date relation:Author:PersonBookGeorgeBackgammon for BeginnersJohnBackgammon for BeginnersMaryHow to Play ChessMaryHow to Cheat at ChessPublication-date:BookDateBackgammon for Beginners1978How to Play Chess1981How to Cheat at Chess1982Although the second two relations may seem more verbose than the first one, they are actuallyrepresentationally better in some sense, because the publication dates of books are not representedredundantly. If one wants to change the publication date of "Backgrammon for Beginners" to 1979,for example, it need only be changed in one place in the publication-date relation but in two placesin the publication relation. If the date were changed in only one place in the publication relation,+[5ptpXtptpt;pSZt&BpMrIp s p7G4DX B^@U- "*%@' #s !g!p!g!  U    s pi i si >i 6JFaKd9, >Q\OCYPRESS DOCUMENTATION14the database would become inconsistent. This kind of behavior is called an update anomaly. Thesecond two relations are said to be a normalized form (as it happens, third normal form) of the firstrelation, and thereby avoid this particular kind of update anomaly. Relational normalization is not strictly part of the Cypress data model. However the model'soperations (and the tools we will develop in the implementation) encourage what we will callfunctionally irreducible form, in which relations are of the smallest order that is naturally meaningful. A relation is in irreducible form if it is of the smallest order possible without introducing newartificial domain(s) not otherwise desired (all relations can be reduced to binary by introducingartificial domains). We will allow a slight weakening of irreducible form, functionally irreducibleform, which permits combining two or more irreducible relations only when their semantics aremutually dependent (and therefore all present or absent in our world representation). For example,a birthday relation between a person, month, day, and year can be combined instead of using threerelations. Another example would be an address relation between a person, street, city, and zip code.Combining an age and phone relation would not result in functionally irreducible form, however, astheir semantics are not mutually dependent. The functionally irreducible relations seen by the user are independent of the physical representationchosen by the system for efficiency, so we are concerned only with the logical data access. Note thatin addition to avoiding update anomalies, functionally irreducible form provides a one-to-onecorrespondence between the relationships in the database and the atomic facts they represent, acanonical form that is in some sense more natural than any other form. 2.8 SegmentsWe would like a mechanism to divide up large databases, to provide different perspectives or subsetsof the data to different users or application programs. In this section we discuss a mechanism toprovide this separation: segments. A segment is a set of entities and relationships that a databaseclient chooses to treat as one logical and physical part of a database.In introducing segments, we will slightly change the definition of an entity, previously defined to beuniquely determined by its domain and name. We will treat entities with the same name anddomain in different segments as different entities, although they may represent the same externalentity. The unique identifier of an internal entity is now the triple[segment, domain, name]. A consequence of this redefinition of entities is that relations and domains do not span segments,either. Application programs must maintain any desired correspondence between entities, domains,or relations with the same name in different segments. We will return to this later. In the nextsection, we will discuss a more powerful but more complex and expensive mechanism, augments, inwhich the database system itself maintains the correspondence.]"ptFpt pjUG:spjSHjPDjMHjKJjImsp8jFes psp@jD0IjAdj?Ij=V j;^sp0'j9*!sp7j6 spsp< j4,j1Vj/aj-PR j+(7j(Gj"r jp:*jTbjspCjGjNjL jzEjFF` =j 56,jNj7rp jSspjd=s  M ?Q^< CYPRESS DATA MODEL CONCEPTS15We introduce three new operations to the data model in conjunction with segments:DeclareSegment[segment, file]: opens a segment with the given name, whose data isstored in the given file.GetSegments[] returns a list of all the segments which have been opened.SegmentOf[entity or relationship] returns the segment in which a given entity orrelationship exists. It may also be applied to relations or domains, since they are entities.With the addition of segments to the data model, we redefine the semantics of the basic accessoperations as follows:1.DeclareDomain and DeclareRelation take an additional argument, namely the segment inwhich the defined domain or relation will reside. The entity representing a domain orrelation now represents data in a particular segment.2.DeclareEntity and DeclareRelationship are unaffected: they implicitly refer to thesegment in which the respective domain or relation was defined. By associating a segment(and therefore a transaction and underlying file) with each relation or domain entityreturned to the database client, we conveniently obviate the need for additional argumentsto every invocation of the basic operations in the data model.3.DestroyEntity, DestroyRelationship, GetF, SetF, DomainOf, RelationOf, and Eq aresimilarly unaffected: they deal with entities and relationships in whatever segment they aredefined. Note that by our definition, entities in different segments are never Eq. Also notethat nothing in our definition makes a SetF across a segment boundary illegal (i.e.SetF[relationship, attribute, entity] where the relationship and entity are in differentsegments). Our current implementation requires that special procedures GetFR and SetFR be used onattributes that can cross segment boundaries, see Section 3.4.DomainSubset and RelationSubset are unchanged when applied to client-defined domainsor relations, i.e., they enumerate only in the segment in which the relation or domain wasdeclared. However an optional argument may be used when applied to one of the systemdomains or relations (e.g. the Domain domain), allowing enumeration over a specificsegment or all segments. RelationSubset's attribute-value-list arguments implictly indicate the appropriatesegment even for system relations, so a segment is not normally needed unless the entire relation isenumerated.Note that the data in a segment is stored in an underlying file physically independent from othersegments, perhaps on another machine. Introducing a file system into the conceptual data modelmay seem like an odd transgression at this point. From a practical point of view, however, we+]"ptpXtptpt;pUGQQkup!O6K[u p:Gu"p #EJT @M>g:u pup8V66"52Fu pup.0)0-+*+K)t>%u9 pup#dB!0=up @u&p2 tA^<pu pu p5N?@ J tT X p?"_d7' f >Q^<CYPRESS DOCUMENTATION16believe it better to view certain problems at the level of file systems. This point of view allowssegments to be used for the following purposes:1.Physical independence: Different database applications typically define their data inseparate segments. As a result one application can continue to operate although the datafor another has been logically or physically damaged. One application can entirely rebuildits database without affecting another, or an application can continue to operate in adegraded mode missing data in an unavailable segment.2.Logical independence: Different database applications may have information which pertainsto the same external entity, e.g. a person with a particular social security number. Whenone application performs a DestroyEntity operation, however, we would like the entity todisappear only from that application's point of view. Information maintained by otherapplications should remain unchanged. 3.Protection: Clients can trust the protection provided by a file system more easily than acomplex logical protection mechanism provided by the database system. An even higherassurance of protection can be achieved by physical isolation of the segment at a particularcomputer site. A more complex logical protection mechanism would be desirable for somepurposes, but was deemed beyond the scope of Cypress.4.Performance: Data may be distributed to sites where they are most frequently used. Forexample, personal data may reside on a client's machine while publicly accessed data resideon a file server. If the file system provides replication, it can be used to improveperformance for commonly accessed data.Concurrency control is handled by the file system. As noted earlier, information about an external entity may be distributed over multiple segments.One or more database applications may cooperate in maintaining the illusion that entities, domains,and relations span segment boundaries. This illusion may be used in at least two ways:1.Private additions may be added to a public segment by adding entities or relationships in aprivate segment. The new relationships may reference entities in the public segment bycreating representative entities with the same name in the private segment. An examplewould be personal phone numbers and addresses added to a public database of phonenumbers and addresses: an application program would make the two segments appear tothe user as one database.2.If two applications use separate segments A and B, they may safely reference each other'sdata yet remain physically independent. One of the applications may destroy andreconstruct its segment if it uses the same unique names for its entities. If both applications\ptFpt pjTcjR/N`sp@`LuF`JAJ`H I `E5A`sp"$`?L `=s p`;_&0`9*&5N`s p1`3F`0O `. I`,}5(`s pH`&l/,`$8E`"'j3jNj!BjW`*1`zF`FB` 6` 4``*spsp'` P`d@ M \?Q]CYPRESS DATA MODEL CONCEPTS17have relationships referencing an entity e, and application A does a DestroyEntity operationon e, the entity and relationships referencing it disappear from application A's point ofview, but application B's representative entity and relationships remain.5 ptpXtptpt6p)spspsp-sp dsp2ZI3 :193. Model Level InterfaceWe now describe the Cedar interface to the implementation of the Cypress data model. We assumethat the reader is familiar with the basic conceptual data model, i.e., has read the previous section.Our presentation is therefore slightly different in this section: we describe the procedures in thedatabase interface in roughly the order that a client will want to use them in a program. We presenttypes and initialization, schema definition, the basic operations, and then queries. It should be emphasized that the interface we are about to describe is only one possibleimplementation of the abstract data model described in Section 2. For example, we have chosen toimplement a procedural interface called by Cedar programs, and to do type checking at run-time.3.1 TypesIn this subsection we describe the most important types in the interface. Less pervasive types aretreated at the point where they are first used.Entity: TYPE;Relship: TYPE;An Entity or Relship is not the actual database entity or relationship; they are handles for the actualdatabase objects. All accesses to database objects are performed by calling interface procedures withthe handles as parameters. Even comparisons of two entities for equality must be done in this way.The Entity and Relship handles are allocated from storage and automatically freed by the garbagecollector when no longer needed.Value: TYPE = REF ANY;ValueType: TYPE;Datatype: TYPE;StringType, IntType, BoolType, AnyDomainType: DataType;Storing Cedar data values in tuples presents several problems. First, since we would like to define asingle operation to store a new value into a specified attribute of a Relship (for instance), there mustbe a single type for all values that pass through this "store-value" procedure. This is the type Valueabove, represented as untyped REFs in Cedar. The DataTypes will be discussed in the next section.Entities, strings, integers, and booleans are the types of values the system currently recognizes andallows as attribute values. More precisely, these four types are Entity, ROPE, REF INT, and REFBOOL. In the case of an entity-valued attribute, an attribute's type may be AnyDomainType or aspecific domain may be specified. The latter is highly preferred, as AnyDomainType is a loopholein the type mechanism and limits the kinds of operations that can be performed automatically by theGfp ^q Zp&9 XF V8, TVF R"U NF  < L># I*5 Cr ?pY =v/ 9sX 7f 3pspsp:tp 1UT /!30 ,spsp'# * &sX $ "s ?7 cpL /Fsp ^s pspsp' a ]Bspspsps )p@s p Fs p c h y?Q]CYPRESS DOCUMENTATION20database system or associated tools. We currently provide no mechanism to store compound Cedardata structures such as arrays, lists, or records in a database; the database system's data structuringmechanisms should be used instead. Cypress query operations such as RelationSubset cannot becomposed upon data that appears as uninterpreted bits in the database.Note that a Value may be either an Entity or a Datum. Some operations accept any Value, e.g.SetF; others require an Entity, e.g. NameOf. Others may require an Entity from a particular client-defined domain, e.g. a Person. We might think of the hierarchy of built-in and client defined typesand instances of values like this:Value type hierarchyDatabase representative of typeValue (REF ANY)ValueType Datum DatumType ROPE StringType INT IntType BOOL BoolType Entity AnyDomainType person Entity Person domain employee Entity Employee domain ... other client-defined entities ... ... other client-defined domains ...As Cedar doesn't have a good mechanism for defining type hierarchies or new types for client-defined domains, most Cypress operations simply take a REF ANY or an Entity as argument,performing further type checking at run-time.3.2 Transactions and segmentsIn this section we describe the basic operations to start up a database application's interaction withCypress. The client application's data is stored in one or more segments, accessed undertransactions. The Cypress system currently runs on the same machine as the client program,however transactions are implemented by the underlying file system which may reside on anothermachine. Data in remote segments may therefore be concurrently accessed by other instances ofCypress on other client machines.A transaction is a sequence of read and write commands. The system supports the property that theentire sequence of commands executes atomically with respect to all other data retrieval and updates,that is, the transaction executes as if no other transactions were in progress at the same time.Because there may in fact be other transactions accessing the same data at the same time, it ispossible that two transactions may deadlock, in which case one of them must be aborted. So the"fpuFpu Mp _%: \M ZZ XxF T spspspsp Rhspspspsp P4sp6 M"H% YH|r%H%H|r+`H%H|FHs%D% A% ?% =v% ;A%9 p s%psp6s%psp4)%( 0A .(spsp ,_- &r #pf  S  I cF /K ! D %t p1 *6 F MF M ?Q]<MODEL LEVEL INTERFACE21price paid for concurrent access is that programs be prepared to retry aborted transactions.The database system provides the capability of accessing a database stored on the same machine asthe database client, using the Pilot file system or on Alpine file servers. We currently permit onlyone transaction per segment per instance of the database software on a client machine. That is, datain remote segments may concurrently be updated by application programs under separatetransactions, but on the same machine transactions are used simply to make application transactionson their respective segments independent. This transaction-per-segment scheme is a majorsimplification of the Cypress package. In addition, as we shall see presently, nearly all Cypressprocedures can automatically infer the appropriate segment and transaction from the procedurearguments, avoiding the need to pass the transaction or segment for every database operation. Calls to Initialize, DeclareSegment, and OpenTransaction start the database session. Atransaction is either passed in by the client, or created by the database package (the latter is just aconvenience feature). The operation MarkTransaction below forms the end of a databasetransaction and the start of a new one. The operation AbortTransaction may be used to abort atransaction. Data in a database segment may not be read or updated until the segment andtransaction have been opened. Clients must decide when to tell the system that a transaction iscomplete (with CloseTransaction), and must be prepared to deal with unsolicited notification thatthe current transaction has been aborted because of system failure or lock conflict.The client's interaction with the database system begins with a call to Initialize:Initialize: PROC[ nCachePages: CARDINAL_ 256, nFreeTuples: CARDINAL_ 32, cacheFileName: ROPE_ NIL ];Initialize initializes the database system and sets various system parameters: nCachePages tells thesystem how many pages of database to keep in virtual memory on the client's machine,nFreeTuples specifies the size to use for the internal free list of Entity and Relship handles, andcacheFileName is the name of the disk file used for the cache backing store. Any or all of thesemay be omitted in the call; they will be given default values. Initialize should be called before anyother operation; the schema declaration operations generate the error DatabaseNotInitialized if thisis violated.Before database operations may be invoked, the client must open the segment(s) in which the dataare stored. The location of the segment is specified by using the full path name of the file, e.g."[MachineName]SubDirectory>SegmentName.segment". Each segment has a uniquename, the name of a Cedar ATOM which is used to refer to it in Cypress operation. The name ofthe Cedar ATOM is normally, though not necessarily, the same as that of the file in which it is"SfpuFpupuGp _\ [:^ Y$A VF T'L( RhJ P4Q MD KS I? E!spsp" C` AR  sp" ?7sp <3& :?! 8sp 4 6KT 2pHs .X ,_ *+ ' $ p&s p ! J s p#spsp }s pK I.s p Fsp  N 8+ O gsp4 3 sp%, >Q^(CYPRESS DOCUMENTATION22stored, except the extension ".segment" and the prefix specifying the location of the file is omitted inthe ATOM. If the file is on the local file system, its name is preceded by "[Local]". For example,"[Local]Foo" refers to a segment file on the local disk named Foo.database;"[Alpine]Baz" refers to a segment named Baz.segment on the directory onthe Alpine server. It is generally a bad idea to access database segments other than through thedatabase interface. However, because segments are physically independent and contain no referencesto other files by file identifier or explicit addresses within files, the segment files may be movedfrom machine to machine or renamed without effect on their contents. If a segment file in a set ofsegments comprising a client database is deleted, the others may still be opened to produce adatabase missing only that segment's entities and relationships. A segment is defined by theoperation DeclareSegment:DeclareSegment: PROC[ filePath: ROPE, segment: Segment, number: INT_ 0, readOnly: BOOL_ FALSE, version: Version_ OldOnly, nBytesInitial, nBytesPerExtent: LONG CARDINAL_ 32768] RETURNS [Segment];Segment: TYPE = ATOM;Version: TYPE = {NewOnly, OldOnly, NewOrOld};The version parameter to DeclareSegment defaults to OldOnly to open an existing file. The signalIllegalFileName is generated if the directory or machine name is missing from fileName, andFileNotFound is generated at the time a transaction is opened on the segment if the file does notexist. If version NewOnly is passed, a new segment file will be created, erasing any existing one. Inthis case, a number assigned to the segment by the database administrator must also be passed. Thisnumber hack is necessitated by our current implementation of segments (it specifies the section of the database addressspace in which to map this segment). Please bear with us. Finally, the client program can passversion=NewOrOld to open a new or existing segment file; in this case the segment number mustalso be passed, of course.The other parameters to DeclareSegment specify properties of the segment. If readOnly=TRUE,then writes are not permitted on the segment; any attempt to invoke a procedure which modifiesdata will generate the error ProtectionViolation. nBytesInitial is the initial size to assign to thesegment, and nBytesPerExtent is the incremental increase in segment size used when more space isrequired for data in the file.For convenience, a call is available to return the list of segments that have been declared in thecurrent Cypress session: "fpuFpu Mp _+= \sp N Z7 XxZ VDK TM Q V O*9 Mr<! K>] I  s p E-sX B3 @3 >7 <\ 8 6K- 2ppsp s p sp 0;sp.sp .s p1$ +spM ) sp6u '"U %|p& #Gsp9 ! 7s p s p 9% sps p  spA e .4 U > M?QYMODEL LEVEL INTERFACE23GetSegments: PROC RETURNS[LIST OF Segment ];A transaction is associated with a segment by using OpenTransaction: OpenTransaction: PROC[ segment: Segment, userName, password: ROPE_ NIL, useTrans: Transaction_ NIL ];If useTrans is NIL then OpenTransaction establishes a new connection and transaction with thecorresponding (local or remote) file system. Otherwise it uses the supplied transaction. The sametransaction may be associated with more than one segment by calling OpenTransaction with thesame useTrans argument for each. The given user name and password, or by default the logged inuser, will be used if a new connection must be established.Any database operations upon data in a segment before a transaction is opened or after a transactionabort will invoke the Aborted signal. The client should catch this signal on a transaction abort,block any further database operations and wait for completion of any existing ones. Then the clientmay re-open the aborted transaction by calling OpenTransaction. When the remote transaction issuccessfully re-opened, the client's database operations may resume.Note that operations on data in segments under different transactions are independent. Normallythere will be one transaction (and one or more segments) per database application program. A clientmay find what transaction has been associated with a particular segment by callingTransactionOf: PROC [segment: Segment] RETURNS [Transaction];Transactions may be manipulated by the following procedures:MarkTransaction: PROC[trans: Transaction];AbortTransaction: PROC [trans: Transaction];CloseTransaction: PROC [trans: Transaction];MarkTransaction commits the current database transaction, and immediately starts a new one. Uservariables which reference database entities or relationships are still valid.AbortTransaction aborts the current database transaction. The effect on the data in segmentsassociated with the segment is as if the transactions had never been started, the state is as it was justafter the OpenTransaction call or the most recent MarkTransaction call. Any attempts to usevariables referencing data fetched under the transaction will invoke the NullifiedArgument error. A"SfpuFpupuGp _sX, [:p4sp W^sX U* R P Lpspwpsp J7, H|5sp FHspR D; @7X >spsp sp0 ;d 9/sp 7fD 3E 1U"B /!R +EsX= 'ip< #sX* , , pL M spM W spsp M,sp  >Q]CYPRESS DOCUMENTATION24call to OpenTransaction is necessary to do more database operations, and all user variablesreferencing database items created or retrieved under the corresponding transaction must be re-initialized (they may reference entities or relationships that no longer exist, and in any case they aremarked invalid by the database system).A simple client program using the database system might have the form, then:Initialize[];DeclareSegment["[Local]Test", $Test];OpenTransaction[$Test];...... database operations, including zero or more MarkTransaction calls ......CloseTransaction[TransactionOf[$Test]];3.3 Data schema definitionThe definition of the client's data schema is done through calls to procedures defined in this section.The data schema is represented in a database as entities and relationships, and although updates tothe schema must go through these procedures to check for illegal or inconsistent definitions, theschema can be read via the normal data operations described in the next section. Each domain,relation, etc., has an entity representative that is used in data operations which refer to that schemaitem. For example, we pass the domain entity when creating a new entity in the domain. The typesof schema items are:Domain, Relation, Attribute, Datatype, Index, IndexFactor: TYPE = Entity;Of course, since the schema items are entities, they must also belong to domains; there are pre-defined domains, which we call system domains, in the interface for each type of schema entity:DomainDomain, RelationDomain, AttributeDomain, DatatypeDomain, IndexDomain: Domain;There are also pre-defined system relations, which contain information about sub-domains, attributes,and indices. Since these are not required by the typical (application-specific) database client, wedefer the description of the system relations to Section 3.6. In general, any of the data schema may be extended or changed at any time; i.e., data operationsand data schema definition may be intermixed. However, there are a few specific orderingconstraints on schema definition we will note shortly. Also, the database system optimizes for betterperformance if the entire schema is defined before any data are entered. The interactive schema editing"fpuFpu Mp _spD \5* ZO Xx' TLPs N%LXJ#GpIEsC' =/r 9TpV 7,-tp 4] 2 tpL 0g .Mb , (=sXI $apE "-t p2 QsXS upY AG  =u 1pN P 60 Ju M L?Q\MODEL LEVEL INTERFACE25tool described in the database tools documentation allows the schema to be changed regardless of ordering constraints andexisting data, by recreating schema items and copying data invisibly to the user when necessary.All the data schema definition operations take a Version parameter which specifies whether theschema element is a new or existing one. The version defaults to allowing either (NewOrOld): i.e.,the existing entity is returned if it exists, otherwise it is created. This feature avoids separateapplication code for creating the database schema the first time the application program is run. DeclareDomain: PROC [name: ROPE, segment: Segment, version: Version_ NewOrOld, estRelations: INT_ 5] RETURNS [d: Domain];DeclareSubType: PROC[sub, super: Domain];DeclareDomain defines a domain with the given name in the given segment and returns itsrepresentative entity. If the domain already exists and version=NewOnly, the signal AlreadyExistsis generated. If the domain does not already exist and version=OldOnly, then NIL is returned.The parameter estRelations is used to estimate the largest number of relations in which entities ofthis domain are expected to participate.The client may define one domain to be a subtype of another by calling DeclareSubType. Thispermits entities of the subdomain to participate in any relations in which entities of thesuperdomains may participate. All client DeclareSubType calls should be done before declaringrelations on the superdomains (to allow some optimizations). The error MismatchedSegment isgenerated if the sub-domain and super-domain are not in the same segment.DeclareRelation: PROC [ name: ROPE, segment: Segment, version: Version_ NewOrOld] RETURNS [r: Relation];DeclareAttribute: PROC [ r: Relation, name: ROPE, type: ValueType_ NIL, uniqueness: Uniqueness _ None, length: INT_ 0, link: {Linked, Unlinked, Colocated, Remote}_ yes, version: Version_ NewOrOld] RETURNS[a: Attribute];Uniqueness: TYPE = {NonKey, Key, KeyPart, OptionalKey};DeclareRelation defines a new or existing relation with the given name in the given segment andreturns its representative entity. If the relation already exists and version=NewOnly, the signalAlreadyExists is generated. If the relation does not already exist and version=OldOnly, then NILis returned."SfpuFpupuGp _9u2G ](` YLp.sp& WM TQ RP NsX2 LH H) D psp sp Bup 0s @~p7spspsp >J s pI <( 89>s p 6J 3s p& 1up x sp /hI +sX )WR %| #G0 !1 O  7 p"sp sp W s p;spsps Up  & @QYCYPRESS DOCUMENTATION26DeclareAttribute is called once for each attribute of the relation, to define their names, types, anduniqueness. If version=NewOrOld and the attribute already exists, Cypress checks that the newtype, uniqueness, etc. match the existing attribute. The error MismatchedExistingAttribute isgenerated if there is a discrepancy. The attribute name need only be unique in the context of itsrelation, not over all attributes. Note this is the only exception to the data model's rule that names be unique in adomain. Also note that we could dispense with DeclareAttribute altogether by passing a list into the DeclareRelationoperation; we define a separate procedure for programming convenience.The attribute type should be a ValueType, i.e. it may be one of the pre-defined types (IntType,StringType, BoolType, AnyDomainType) or the entity representative for a domain. For pre-defined types, the actual values assigned to attributes of the relationship instances of the relationmust have the corresponding type: REF INT, ROPE, REF BOOL, or Entity. If the attribute has adomain as type, the attribute values in relationships must be entities of that domain or some sub-domain thereof. The type is permitted to be one of the pre-defined system domains such as theDomainDomain, thereby allowing client-defined extensions to the data schema (for example, acomment for each domain describing its purpose). The attribute uniqueness indicates whether the attribute is a key of the relation. If its uniquenessis NonKey, then the attribute is not a key of the relation. If its uniqueness is OptionalKey, then thesystem will ensure that no two relationships in r have the same value for this attribute (if a value hasbeen assigned). The error NonUniqueKeyValue is generated if a non-unique key value results froma call to the SetP, SetF, SetFS, or CreateRelship procedures we define later. Key acts the same asOptionalKey, except that in addition to requiring that no two relationships in r have the same valuefor the attribute, it requires that every entity in the domain referenced by this attribute must bereferenced by a relationship in the relation: the relationships in the relation and the entities in thedomain are in one-to-one correspondence. Finally, if an attribute's uniqueness is KeyPart, then thesystem will ensure that no two relationships in r have the same value for all key attributes of r,though two may have the same values for some subset of them.The length and link arguments to DeclareAttribute have no functional effect on the attribute, butare hints to the database system implementation. For StringType fields, length characters will beallocated for the string within the space allocated for a relationship in the database. There is noupper limit on the size of a string-valued attribute; if it is longer than length, it will be storedseparately from the relationship with no visible effect except for the performance of databaseapplications. The link field is used only for entity-valued fields; it suggests whether the databasesystem should link together relationships which reference an entity in this attribute. In addition, itcan suggest that the relationships referencing an entity in this attribute be physically co-located aswell as linked. Again, its logical effect is only upon performance, not upon the legal operations."fpuFpu Mp _spU \sp$ Z5 sp XxP VD$uN T3U R"F NFp sp sp&s L#p I>' G#xpxp EtE C@spE A s pM >1 : s p D 8sp3s p 60sp 4^sp 2) sps psp /s pDsp -L +26 )W(+sp '# %sptpsp $< !spsp sp0 6s psp X u =sp AK  sp9 U R oM : M(>QXPMODEL LEVEL INTERFACE27DestroyRelation: PROC[r: Relation];DestroyDomain: PROC[d: Domain];DestroySubType: PROC[sub, super: Domain];Relations, domains, and subdomain relationships may be destroyed by calls to the above procedures.Destroying a relation destroys all of it relationships. Destroying a domain destroys all of its entitiesand also any relationships which reference those entities. Destroying a sub-domain relationship hasno effect on existing domains or their entities; it simply makes entities of domain sub no longereligible to participate in the relations in which entities of domain super can participate. Existingrelationships violating the new type structure are allowed to remain. Existing relations and domains may only bemodified by destroying them with the procedures above, with one exception: the operationChangeName (described in Section 3.4) may be used to change the name of a relation or domain.DeclareIndex: PROC [ relation: Relation, indexedAttributes: AttributeList, version: Version];DeclareIndex has no logical effect on the database; it is a performance hint, telling the databasesystem to create a B-Tree index on the given relation for the given indexedAttributes. The indexwill be used to process queries more efficiently. Each index key consists of the concatenated valuesof the indexedAttributes in the relationship the index key references. For entity-valued attributes,the value used in the key is the string name of the entity. The version parameter may be used as inother schema definition procedures, to indicate a new or existing index. If any of the attributes arenot attributes of the given relation then the signal IllegalIndex is generated.The optimal use of indices, links, and colocation, as defined by DeclareIndex and DeclareAttribute,is complex. It may be necessary to do some space and time analysis of a database application tochoose the best trade-off, and a better trade-off may later be found as a result of unanticipatedaccess patterns. Note, however, that a database may be rebuilt with different links, colocation, orindices, and thanks to the data independence our interface provides, existing programs will continueto work without change.If a relation is expected to be very small (less than 100 relationships), then it might reasonably bedefined with neither links nor indices on its attributes. In the typical case of a larger relation, oneshould examine the typical access paths: links are most appropriate if relationships that pertain toparticular entities are involved, indices are more useful if sorting or range queries are desired.B-tree indices are always maintained for domains; that is, an index contains entries for all of theentities in a domain, keyed by their name, so that sorting or lookup by entity name is quick. Stringcomparisons are performed in the usual lexicographic fashion."SfpuFpupuGp _sX# [: W^) SpL QNE$ O X LTsp JEspu H|Ep) FHO Ds p1" @7sX >J :' p-) 7-spsp 5Q 3sp"+ 1UAsp /!H ,5s p )As psp &H $P "s04 ? X   /U :. U Y _ G M= > ?Q]CYPRESS DOCUMENTATION28DeclareProperty: PROC [ relationName: ROPE, of: Domain, type: ValueType, uniqueness: Uniqueness_ None, version: Version_ NewOrOld] RETURNS [property: Attribute];DeclareProperty provides a shorthand for definition of a binary relation between entities of thedomain "of" and values of the specified type. The definitions of type and uniqueness are the sameas for DeclareAttribute. A new relation relationName is created, and its attributes are given thenames "of" and "is". The "is" attribute is returned, so that it can be used to represent the propertyin GetP and SetP defined in the next section.3.4 Basic operations on entities and relationshipsIn this section, we describe the basic operations on entities and relationships; we defer the operationson domains and relations to the next section.A number of error conditions are common to all of the procedures in this section. Since values arerepresented as REF ANYs, all type checking must currently be done at run-time. The procedures inthis section indicate illegal arguments by generating the errors IllegalAttribute, IllegalDomain,IllegalRelation, IllegalValue, IllegalEntity, and IllegalRelship, according to the type of argumentexpected. The error NILArgument is generated if NIL is passed to any procedure that cannot acceptNIL for that argument. The error NullifiedArgument is generated if an entity or relationship ispassed in after it has been deleted or rendered invalid by transaction abort or close. DeclareEntity: PROC[ d: Domain, name: ROPE_ NIL, version: Version_ NewOrOld] RETURNS [e: Entity];DeclareEntity finds or creates an entity in domain d with the given name. The name may beomitted if desired, in which case an entity with a unique name is automatically created. If versionis OldOnly and an entity with the given name does not exist, NIL is returned. If version is NewOnlyand an entity with the given name already exists, the signal NonUniqueEntityName is generated.DeclareRelship: PROC [ r: Relation, avl: AttributeValueList_ NIL, version: Version_ NewOrOld] RETURNS [Relship];DeclareRelship finds or creates a relship in r with the given attribute values. If version isNewOnly, a new relship with the given attribute values is generated. If version is OldOnly, therelship in r with the given attribute values is returned if it exists, otherwise NIL is returned. If"fpuFpu Mp _sX \2 Z; Xx TpH Rhspsp5 P4sps p M X Kspsp Etr2 ApY ?d- ;12 9T s p6 75 s 4,ps p# 2 s psp. 0spsp* .MW *rsX (=9 &  "- p&sp As psp3sps p=sp sX H K o psp&sp ;sp3spsp  spEsp R M >Q]LMODEL LEVEL INTERFACE29version is NewOrOld, the relship with the given attribute values is returned if it exists, otherwiseone is created. If the creation of a new relship violates the key constraints specified byDeclareAttribute, the signal NonUniqueAttributeValue is generated.DestroyEntity: PROC[e: Entity];DestroyEntity removes e from its domain, destroys all relationships referencing it, and destroys theentity representative itself. Any client variables that reference the entity automatically take on thenull value (Null[e] returns TRUE), and cause error NullifiedArgument if passed to database systemprocedures. After an entity is destroyed, its old name may be re-used in creating a new one.DestroyRelship: PROC[t: Relship];DestroyRelship removes t from its relation, and destroys it. Any client variables that reference therelationship automatically take on the null value, and will cause error NullifiedArgument ifsubsequently passed to database system procedures.SetF: PROC[t: Relship, a: Attribute, v: Value];SetF assigns the value v to attribute a of relationship t. If the value is not of the same type as theattribute (or a subtype thereof if the attribute is entity-valued), then the errorMismatchedAttributeValueType is generated. If a is not an attribute of t's relation, IllegalAttributeis generated.GetF: PROC[t: Relship, a: Attribute] RETURNS [Value];GetF retrieves the value of attribute a of relationship t. If a is not an attribute of t's relation, errorIllegalAttribute is generated. The client should use the V2x routines described in the next section tocoerce the value into the expected type.SetFS: PROC [t: Relship, a: Attribute, v: ROPE];GetFS: PROC[t: Relship, a: Attribute] RETURNS [ROPE];GetFS and SetFS provide a convenient veneer on top of GetF and SetF that provide the illusionthat all relation attributes are string-valued. The effect is something like the Relational data model,and is useful for applications such as a relation displayer and editor that deal only with strings. Thesemantics of GetFS and SetFS depend upon the actual type of the value v of attribute a:"SfpuFpupuGp _spsp D \ K Zsp sp VsX R psp,! PF! N spspsp  LX*3 H|sX! D pspH Bl&!sp @72 <\sX/ 8psp spsp. 6KC 4spspsp s 1p .sX5 *+p spspspsp 'sp-* %( !sX0 5 pspspsp a mJ 9 spsp*sp sH >QS CYPRESS DOCUMENTATION30typeGetFS returnsSetFS assigns attribute to beStringTypethe string vthe string vIntTypev converted to decimal stringthe string converted to decimal integerBoolType"TRUE" or "FALSE"true if "TRUE", false if "FALSE"a domain Dthe name of the ref'd entitythe entity with name v(or null string if v is NIL)(or NIL if v is null string)AnyDomainTypesame, but includes domain:the entity with the given domain and name:(or NIL if v is null string)The same signals generated by GetF and SetF, such as IllegalAttribute, can also be generated bythese procedures. The string NIL represents the undefined value. The signal NotFound is generatedin the last case above if no entity with the given name is found.NameOf: PROC [e: Entity] RETURNS [s: ROPE];ChangeName: PROC [e: Entity, s: ROPE];NameOf and ChangeName retrieve or change the name of an entity, respectively. They generatethe signal IllegalEntity if e is not an entity.ChangeName should be used with caution. It is not quite equivalent to destroying and re-creating an entity with the newname but the same existing relationships referencing it. ChangeName is considerably faster than that, and furthermoreentity-valued variables which reference the entity are not nullified by ChangeName, though they would be byDestroyEntity. These features should be a help, not a hindrance. However, changing an entity name may invalidatereferences to the entity from outside the segment, e.g. in another segment or in some application-maintained file such as alog of updates. DomainOf: PROC[e: Entity] RETURNS [Domain];RelationOf: PROC[t: Relship] RETURNS [Relation];DomainOf and RelationOf can be used to find the entity representative of an entity's domain or arelationship's relation, respectively. The signal IllegalEntity is generated if e is not an entity. Thesignal IllegalRelship is generated if r is not a relationship.SegmentOf: PROC[e: Entity] RETURNS [Segment];SegmentOf returns the segment in which an entity is stored. It can be applied to domain, relation,or attribute entities.Eq: PROC [e1: Entity, e2: Entity] RETURNS [BOOL];Eq returns TRUE iff the same database entity is referenced by e1 and e2. This is not equivalent tothe Cedar expression "e1 = e2", which computes Cedar REF equality. If e1 and e2 are in"fpuFpu Mp ^._v`^ _X -^_ \s ` - Z`-' Xx`- VD `-`T- Q `-)`O- Kpspsp sp  Isp-sp GbA CsX+ AR& =vps p( ;A s psp 7ut 5G/ 37yu+ 1B0 /2I - *+sX+ '0 $ps p. !3s p) spsp sX- pE  sX1 ;psp/spsptp sp*spsp  M >Q]L+MODEL LEVEL INTERFACE31different segments, Eq returns true iff they have the same name and their domains have the samename.Null: PROC [x: EntityOrRelship] RETURNS [BOOL];Null returns TRUE iff its argument has been destroyed, is NIL, or has been invalidated by abortionof the transaction under which it was created.GetP: PROC [e: Entity, aIs: Attribute, aOf: Attribute_ NIL] RETURNS [Value];SetP: PROC [e: Entity, aIs: Attribute, v: Value, aOf: Attribute_ NIL] RETURNS[Relship];GetP and SetP are convenience routines for a common use of relationships, to represent"properties" of entities. Properties allow the client to think of values stored in relationshipsreferencing an entity as if they are directly accessible fields (or "properties") of the entity itself. Seethe figure on page 15 illustrating properties. GetP finds a relationship whose from attribute is equal to e,and returns that relationship's to attribute. The from attribute may be defaulted if the relation isbinary, it is assumed to be the other attribute of to's relation. If it is not binary, the current implementationwill find the "first" other attribute, where "first" is defined by the order of the original calls calls to DeclareAttribute.SetP defaults the from attribute similarly to GetP, but operates differently depending on whetherfrom is a key of the relation. Whether it is a key or not, any previous relationship that referenced ein the from attribute is automatically deleted. In either case, a new relationship is created whosefrom attribute is e and whose to attribute is v. SetP returns the relationship it creates for theconvenience of the client. GetP and SetP can generate the same errors as SetF and GetF, e.g. if eis not an entity or to is not an attribute. In addition, GetP and SetP can generate the errorIllegalProperty if to and from are from different relations. GetP generates the errorMismatchedPropertyCardinality if more than one relationship references e in the from attribute; ifno such relationships exist, it returns a null value of the type of the to attribute. SetP allows anynumber of existing relationships referencing e; it simply adds another one (when from is a key, ofcourse, there will always be one relationship). GetPList: PROC [e: Entity, to: Attribute, from: Attribute_ NIL] RETURNS [LIST OF Value];SetPList: PROC [e: Entity, to: Attribute, vl: LIST OF Value, from: Attribute_ NIL];GetPList and SetPList are similar to GetP and SetP, but they assume that any number ofrelationships may reference the entity e with their from attribute. They generate the signalMismatchedPropertyCardinality if this is not true, i.e. the from attribute is a key. GetPList returnsthe list of values of the to attributes of the relationships that reference e with their from attribute.Cedar has LISP-like list manipulation facilities. SetPList destroys any existing relationships that reference ewith their from attribute, and creates Length[vl] new ones, whose from attributes reference e and"SfpuFpupuGp _sp3 \ YsX/ TVpsp)sp% R". NFsXL LW GbpspI E-%< BQu @pspsps >pspsp. <\3sp u/ :',Q 7sp spsp. 5spDs 3psp$5 1Usp sp sp spsp, /! spsp!spsp s ,psp$spsp *sp@spspspsp (sp*spsp &Otp,sp sp $-sp#sp !1  sXX S 'pspspsp$ 'sp sp% spspsp sp0sp sp Uu% psp3s p spsp spsp ?Q\2oCYPRESS DOCUMENTATION32whose to attributes are the elements of vl. GetPList and SetPList may generate any of the errorsthat GetF and SetF may generate, and the error IllegalProperty if to and from are from differentrelations.Note that the semantics of SetPList are not quite consistent with the semantics of SetP. SetPListreplaces the current values associated with a "property" with the new values (i.e., destroys and re-creates relationships); SetP adds a new property value, unless the aOf attribute is a key, in whichcase it replaces the current value. The semantics are defined in this way because this has proven themost convenient in our application programs.Examples of the use of the property procedures for data access can be found in Section 4.3.Properties are also useful for obtaining information about the data schema. For example, GetP[a,aRelationIs] will return the attribute a's relation, and GetPList[d, aTypeOf] will return all theattributes that can reference domain d.E2V: PROC[e: Entity] RETURNS[v: Value];B2V: PROC[b: BOOLEAN] RETURNS[v: Value];I2V: PROC[i: LONG INTEGER] RETURNS[v: Value];S2V: PROC[s: ROPE] RETURNS[v: Value];The x2V routines convert the various Cedar types to Values. The conversion is not normallyrequired for ropes and entities since the compiler will widen these into the REF ANY type Value.V2E: PROC[v: Value] RETURNS[Entity];V2B: PROC[v: Value] RETURNS[BOOLEAN];V2I: PROC [v: Value] RETURNS[LONG INTEGER];V2S: PROC [v: Value] RETURNS[ROPE];The V2x routines convert Values to the various Cedar types. The MismatchedValueType error israised if the value is of the wrong type. It is recommended that these routines be used rather thanuser-written NARROWs, as the representation of Values may change. Also, NARROWs of opaque typesdon't yet work in the Cedar compiler.3.5 Query operations on domains and relationsIn this section we describe queries upon domains and relations: operations that enumerate entitiesor relationships satisfying some constraint."fpuFpu Mp _spspspsp \spspspspspsp Z U sp0sps Stp#9 Qsptp"sp O`#C M,, H|K FH>s D pspsp A%sp ;sX' 9w( 7B- 5% 0_psp-sp! .*)7 *NsX$ (% %+ ## pspsp"sp );  wpsp uwu d%  r- ^p#@ *, M ?Q](MODEL LEVEL INTERFACE33RelationSubset: PROC[ r: Relation, constraint: AttributeValueList_ NIL] RETURNS [RelshipSet];NextRelship: PROC[rs: RelshipSet] RETURNS [Relship];PrevRelship: PROC[rs: RelshipSet] RETURNS [Relship];ReleaseRelshipSet: PROC [rs: RelshipSet];AttributeValueList: TYPE = LIST OF AttributeValue;AttributeValue: TYPE = RECORD [ attribute: Attribute, low: Value, high: Value_ NIL -- omitted where same as low or not applicable --];The basic query operation is RelationSubset. It returns a generator of all the relationships inrelation r which satisfy a constraint list of attribute values. The relationships are enumerated bycalling NextRelship repeatedly; it returns NIL when there are no more relationships. PrevRelshipmay similarly be called repeatedly to back the enumeration up, returning the previous relationship; itreturns NIL if the enumeration is at the beginning. ReleaseRelshipSet should be called when theclient is finished with the query.The constraint list may be NIL, in which case all of the relationships in r will be enumerated.Otherwise, relationships which satisfy the concatenation of constraints on attributes in the list will beenumerated. If an index exists on some subset of the attributes, the relationships will be enumeratedsorted on the concatenated values of those attributes. For a StringType, IntType, or TimeTypeattribute a of r, the contraint list may contain a record of the form [a, b, c] where the attributevalue must be greater or equal to b and less than or equal to c to satisfy the constraint. For anytype of attribute, the list may contain a record of the form [a, b] where the value of the attributemust exactly equal b. The Cedar ROPE literals "" and "\377" may be used in queries as aninfinitely large and infinitely small string, respectively. The signal MismatchedAttributeValueTypeis generated by RelationSubset if one of the low or high values in the list is of a different typethan its corresponding attribute.DomainSubset: PROC[ d: Domain, lowName, highName: ROPE_ NIL, searchSubDomains: BOOL_ TRUE, searchSegment: Segment_ NIL]"SfpuFpupuGp _sX \3 Z V4 R4 O) K>2 I  F D BlG =p s p5 ;spZ 9Ts psp(s 7pU 4sp*sp 2" .sp,sp +&C )51 'i$s psps %5p spsp'sp # spsp$ <sp! sp sp c8s /ps pspsp  ! sX    MD ?Q]CYPRESS DOCUMENTATION34 RETURNS [EntitySet];NextEntity: PROC[EntitySet] RETURNS [Entity];PrevEntity: PROC[EntitySet] RETURNS [Entity];ReleaseEntitySet: PROC[EntitySet];DomainSubset enumerates all the entities in a domain. If lowName and highName are NIL, theentire domain is enumerated, in no particular order. Otherwise, only those entities whose names arelexicographically greater than lowName and less than highName are enumerated, in lexicographicorder. If searchSubDomains is TRUE, subdomains of d are also enumerated. Each subdomain issorted separately. The searchSegment argument is currently only used if d is one of the systemdomains, e.g. the Domain domain. It is used to specify which segment to search.Analogously to relation enumeration, NextEntity and PrevEntity may be used to enumerate theentities returned by DomainSubset, and ReleaseEntitySet should be called upon completion.GetDomainRefAttributes: PROC [d: Domain] RETURNS [AttributeList];This procedure returns a list of all attributes, of any relation defined in d's segment, which referencedomain d or one of its superdomains. The list does not include AnyDomainType attributes, whichcan reference any domain. GetDomainRefAttributes is implemented via queries on the dataschema. GetDomainRefAttributes is useful for application-independent tools; most specificapplications can code-in the relevant attributes.GetEntityRefAttributes: PROC [e: Entity] RETURNS [AttributeList];This procedure returns a list of all attributes in which some existing relationship actually referencese, including AnyDomainType attributes.3.6 System domains and relationsIn this section we describe what one might call the schema schema, the pre-defined system domainsand relations which constitute the data schema for client-defined domains and relations. The typicaldatabase application writer may skip this section, since the schema declaration operations defined inSection 3.3 are adequate when the data schema is completely defined and known at the time aprogram is written. The system domains and relations we describe in this section are most useful forgeneral-purpose tools (e.g. for displaying, querying, or dumping any database), where the tools must"fpuFpu Mp _sX [:- W^- S" N pspspsp LH Jjspsp H6 spspu Fps p$sp  CP ? s ps p <s psp  9 sXA 4^p4sp 2)sp/s p /sp" -sp; +1 'sXA #p/8 sp s p s ur p4t p e'> 1)< G U Atp M L>Q\MODEL LEVEL INTERFACE35examine the data schema "on the fly".As noted earlier, the permanent repository for data describing user-defined data in a database is thedatabase's data schema, represented by schema entities and relationships. Schema entities aremembers of one of the pre-defined system domains: DomainDomain, RelationDomain,DatatypeDomain, and so on. Every client-defined domain, relation, or attribute contains arepresentative entity in these domains. Client-defined datatypes are not currently permitted, so theonly entities in the DataType domain are the pre-defined IntType, StringType, and BoolType.The information about the client-defined domains and attributes are encoded by relationships in thedatabase. Domains participate in the system relation dSubType, which encodes a domain typehierarchy:dSubType: Relation; dSubTypeOf: Attribute; -- the domain in this attribute is a super-type of dSubTypeIs: Attribute; -- the domain in this attributeThe dSubType has one element per direct domain-subdomain relationship, it does not contain thetransitive closure of that relation. However, it is guaranteed to contain no cycles. That is, thedatabase system checks that there is no set of domains d1, d2, ... dN, N>1, such that d1 is a subtypeof d2, d2 is a subtype of d3, and so on to dN, and d1=dN. The dSubType may define a lattice asopposed to a tree, i.e. the sSubType attribute is not a key of the relation.The information about attributes is encoded as binary relations, one relation for each argument tothe DeclareAttribute procedure defining properties of the attribute. The names are easy toremember; for each argument, e.g. Foo, we define the aFoo relation, with attributes aFooOf andaFooIs. The aFooIs attribute is the value of that argument, and the aFooOf attribute is [the entityrepresentative of] the attribute it pertains to. Thus we have the following relations: aRelation: PUBLIC READONLY Relation; -- Specifies attribute - relation correspondence: -- [aRelationOf: KEY Attribute, aRelationIs: Relation] aRelationOf: PUBLIC READONLY Attribute; -- attribute whose relation we are specifying aRelationIs: PUBLIC READONLY Attribute; -- the relation of that attribute aType: PUBLIC READONLY Relation; -- Specifies types of relation attributes: -- [aTypeOf: KEY Attribute, aTypeIs: ValueType] aTypeOf: PUBLIC READONLY Attribute; -- the attribute aTypeIs: PUBLIC READONLY Attribute; -- domain or datatype of the attribute aUniqueness: PUBLIC READONLY Relation; -- Specifies attribute value uniqueness: -- [aUniquenessOf: KEY Attribute, aUniquenessIs: INT LOOPHOLE[Uniqueness]]"SfpuFpupuGp _% [:P Y-tp $ V?(tp s @ TpD Rhe P4 spsps psp LXN J#%sp G DsX AK ?8 ;pspF 912 7f$67f67f67f67f 51451451451451451451sp 2sp( /!+7 ,sp? *!spspsp (spsp2sp &OW "ssXX ?:  Y M mM 93 8 N gQ 3M J >Q^'CYPRESS DOCUMENTATION36 aUniquenessOf: PUBLIC READONLY Attribute; -- the attribute aUniquenessIs: PUBLIC READONLY Attribute; -- INT for Uniqueness: 0=None, 1=Key, etc. aLength: PUBLIC READONLY Relation; -- Specifies length of attributes: -- [aLengthOf: KEY Attribute, aLengthIs: INT] aLengthOf: PUBLIC READONLY Attribute; -- the attribute aLengthIs: PUBLIC READONLY Attribute; -- INT corresponding to attribute's length aLink: PUBLIC READONLY Relation; -- Specifies whether attribute is linked: -- [aLinkOf: KEY Attribute, aLinkIs: INT] aLinkOf: PUBLIC READONLY Attribute; -- the attribute aLinkIs: PUBLIC READONLY Attribute; -- 0=unlinked, 1=linked, 2 =colocated The final set of system relations pertain to index factors. Each index on a relation is defined toinclude one or more attributes of a relation. For each attribute in the index, there is an index factorentity. For each index, there is an index entity. Each index factor is associated with exactly oneindex and exactly one attribute. Indices may have many index factors, however, and an attributemay be associated with more than one index factor, since attributes may participate in multipleindices. The two relations pertaining to indices map indices on to their index factors, and indexfactors to the attributes they index: ifIndex: PUBLIC READONLY Relation; -- Specifies the index factors for each index -- [ifIndexOf: KEY IndexFactor, ifIndexIs: Index] ifIndexOf: PUBLIC READONLY Attribute; -- the index factor ifIndexIs: PUBLIC READONLY Attribute; -- index of the factor ifAttribute: PUBLIC READONLY Relation; -- Specifies attribute index factor corresponds to -- [ifAttributeOf: KEY IndexFactor, ifAttributeIs: Attribute] ifAttributeOf: PUBLIC READONLY Attribute; -- the index factor ifAttributeIs: PUBLIC READONLY Attribute; -- the attribute this factor representsThe relations on attributes, index factors, and domains can be queried with the RelationSubset orGetPList operations. For example, GetP[a, aRelationIs] returns the attribute a's relation.GetPList[r, aRelationOf] returns the relation r's attributes. RelationSubset[dSubType,LIST[[dSubTypeIs, d]]] will enumerate all the dSubType relationships in which d is the subtype.As noted earlier, the data schema (attributes, relations, domains, indices, index factors, and relationspertaining to these) may only be read, not written by the database client. In order to ensure theconsistency of the schema, it must be written indirectly through the schema definition procedures:DeclareDomain, DeclareRelation, DeclareAttribute, and DeclareSubType. Attempts to perform"fpuFpu Mp _sX> \X XxG VD1 T: QU MrL K>- I 8 FO Bp-t p& @#E >d <\@ :'V 75- 5% 1sXR /5 -z> +EA &[ $A "sA ?U cp;s p /spsp  sp ssptsps pspsp 9/ E H Mspsps p  Z M ?Q]MODEL LEVEL INTERFACE37updates through operations such as SetP result in the error ImplicitSchemaUpdate.3.7 ErrorsWhen a database system operation invokes an error, the SIGNAL Error is generated, with an errorcode indicating the type of error that occured. The error code is a Cedar enumerated type:Error: SIGNAL [code: ErrorCode];ErrorCode: TYPE = {AlreadyExists, -- Entity already exists and client said version=NewOnlyBadUserPassword, -- On an OpenTransactionDatabaseNotInitialized, -- Attempt to do operation without calling InitializeFileNotFound, -- No existing segment found with given nameIllegalAttribute, -- Attribute not of the given relship's Relation or not an attributeIllegalValueType, -- Type passed DeclareAttribute is not datatype or domainIllegalDomain, -- Argument is not actually a domainIllegalFileName, -- No directory or machine given for segmentIllegalEntity, -- Argument to GetP, or etc., is not an EntityIllegalRelship, -- Argument to GetF, or etc., is not a RelshipIllegalRelation, -- Argument is not a relationIllegalSegment, -- Segment passed to DeclareDomain, or etc., not yet declaredIllegalString, -- Nulls not allowed in ROPEs passed to the database systemIllegalSuperType, -- Can't define subtype of domain that already has entitiesIllegalValue, -- Value is not REF INT, ROPE, REF BOOL, or EntityIllegalValueType, -- Type passed DeclareAttribute is not datatype or domainImplicitSchemaUpdate, -- Attempt to modify schema with SetP, DeclareEntity, etc.InternalError, -- Impossible internal state (possibly bug or bad database)MismatchedProperty, -- aOf and aIs attribute not from the same relationMismatchedAttributeValueType, -- Value not same type as required (SetF)MismatchedExistingAttribute, -- Existing attribute is different (DeclareAttribute)MismatchedExistingSegment, -- Existing segment is different (DeclareSegment)MismatchedPropertyCardinality, -- Did GetP with aOf that is not a KeyMismatchedSegment, -- Attempt to create ref across segment boundary (SetF)MismatchedValueType, -- value passed V2E, V2I, etc. not of expected typeMultipleMatch, -- More than one relationship satisfied avl on DeclareRelship.NonUniqueEntityName, -- Entity in domain with that name already existsNonUniqueKeyValue, -- Relship already exists with that valueNotFound, -- Version is OldOnly but no such Entity, Relation, or etc foundNotImplemented, -- Action requested is not yet implementedNILArgument, -- Attempt to perform operation on NIL argumentNullifiedArgument, -- Entity or relationship has been deleted or invalidatedProtectionViolation, -- Read or write to segment not permitted this user.SegmentNotDeclared, -- Attempt to open transaction w/o DeclareSegmentServerNotFound -- File server does not exist or does not respond };"SfpuFpupuGp _#spsp Xr Tp7s p R0+ NsX LJjGH)FME :C@VAuK?3==<=:K>8.6M4J3 M1U@/K-P+J*+G(`G&R$L#E!6JkHMF <AJv:<LILE @  p>Q\CYPRESS DOCUMENTATION38In this report, the expression "generates the error X" means that the SIGNAL Error is generatedwith code=X. Unless otherwise specified, the client may CONTINUE from the signal, aborting theoperation in question. Signals should not be RESUMEd except by a wizard who knows the result ofproceeding with an illegal operation.Two special signals are associated with the file system level:Aborted: SIGNAL [trans: Transaction];Failure: SIGNAL [why: ATOM, server: ROPE];The Aborted signal can be generated by any database operation, and indicates that the transactionhas been aborted. The client must call AbortTransaction and may then call OpenTransaction toproceed. The Failure signal is generated when a transaction cannot be open due to server failure orcommunication difficulties."fpuFpu Mp _3s p \)sp Zsp+ Xx% T>PsX%N* Jpsp3# H'spsp F spO DZ$ MD>Q#j394. Application ExampleThis section provides a simple example of the use of Cypress. Section 4.1 introduces the example, adatabase of documents. Section 4.2 is a discussion of database design: the process of representingabstractions of real-world information structures in a database, somewhat specialized to the datastructures available in Cypress. In Section 4.3, a working program is illustrated.Our example is necessarily short; don't expect any startling revelations on these pages. We will tryto consider some of the most common cases, however.4.1 A database applicationWhat are the properties of a well-designed database? To a large extent these properties follow fromthe general properties of databases. For instance, we would like our databases to extend gracefullyas new types of information are added, since the existing data and programs are likely to be quitevaluable.It may be useful to consider the following point. The distinguishing aspect of information stored ina database system is that at least some of it is stored in a form that can be interpreted by the systemitself, rather than only by some application-specific program. Hence, one important dimension ofvariation among different database designs is in the amount of the database that is system-interpretable, i.e. the kinds of queries that can be answered by the system.As an example of variation in this dimension, consider the problem of designing a database fororganizing a collection of Mesa modules. In the present Mesa environment, this database wouldneed to include at least the names of all the definitions modules, program modules, configurationdescriptions, and current .Bcd files. A database containing only this information is little more than afile directory, and therefore the system's power to answer queries about information in this databaseis very limited. A somewhat richer database might represent the DIRECTORY and IMPORTS sectionsof each module as relationships, so that queries such as "which modules import interface Y?" can beanswered by the system. This might be elaborated further to deal with the use of individual typesand procedures from a definitions module, and so on. There may be a limit beyond which it isuseless to represent smaller objects in the database; if we aren't interested in answering queries like"what procedures in this module contain IF statements?", it may be attractive to represent the bodyof a procedure (or some smaller naming scope) as a text string that is not interpretable by thedatabase system, even though it is stored in a database. We shall illustrate design ideas with a database of information about documents. Our currentfacilities, which again are simply file directories, leave much to be desired. The title of a document;[{pSYqO}pbMIMKGHSDpeBC3;r8p\5 Y3 V1s-pb+c#sp2 ).a&"9$L p6(G-4L\ 322tptp8!tpzJF5(  ] (tp9Xt8)Tp=d"E v>Q\CYPRESS DOCUMENTATION40on the printed page does not tell the reader where the document is stored or how to print a copy.Relationships between different versions of the same basic document are not explicit. Retrievals bycontent are impossible. Our goal here is not to solve all of these problems, but to start a design thathas the potential of dealing with some of them.4.2 Schema designEach document in our example database has a title and a set of authors. Hence we might representa collection of documents with a domain of entities whose name is the title of the document, and anauthor property specifying the authors:Document: Domain = DeclareDomain["Domain"];dAuthors: Property = DeclareProperty["author", Document, StringType];Here the authors' names are concatenated into a single string, using some punctuation scheme toallow the string to be decoded into the list of authors. This is a very poor database design because itdoes not allow the system to respond easily to queries involving authors; the system cannot parse theencoded author list.Note that in the above definition authors are strings, so anything is acceptable as an author. Thisweak typing has some flexibility: the database will never complain that it doesn't know the authoryou just attached to a certain document. However, the system is not helpful in catching errors whena new document is added to the database. If "Mark R. Brown" is mistakenly spelled "Mark R.Browne", then one of Mark's papers will not be properly retrieved by a later search. A step in thedirection of stronger type checking is to provide a separate domain for authors.To represent authors as entities, and to allow a variable number number of authors for a document,a better design would be:Document: Domain = DeclareDomain["Domain"];Person: Domain = DeclareDomain["Person"];author: Property = DeclareProperty["author", Document, Person];Incidentally, in the last line above we define a property rather than relation for brevity. Instead ofthe author property declaration we could have written:author: Relation = DeclareRelation["author"]; authorOf: Attribute = DeclareAttribute[author, "of", Document]; authorIs: Attribute = DeclareAttribute[author, "is", Person];YptFpt pjQLjO}KjMI\ jK/jDrj@p;&j>\jQ\O&CYPRESS DOCUMENTATION42where a large number of relationships are expected to refer to the same entity, it is also more spaceefficient in our implementation.If an authorOrder attribute is defined, the client may wish to redefine the authorOf attribute sothat links (pointers) are not maintained between the Document entities and author relationships,instead defining a more space-efficient B-tree index on the [authorOf, authorOrder] pair:authorOf: Attribute = DeclareAttribute[ relation: author, name: "of", type: Document, link: FALSE];authorIndex: Index = DeclareIndex[author, LIST[[authorOf, authorOrder]]];The Cypress implementation will use this index to process any call of the formRelationSubset[author, LIST[[authorOf, x]]This call to RelationSubset will therefore enumerate authors of document x sorted by authorOrder.Cypress will also use the index in processing for GetPList[..., authorOf] as GetPList usesRelationSubset.This solution is also somewhat less than perfect, as it depends upon the fact that the Cypressimplementation orders relationships when an index exist; but indices are not intended to change thesemantics of the operations, only to improve performance. Probably the best solution, if theordering is important to the semantics of a database application, is to represent a list by a binary"next" relation connecting the entities in an ordering.Documents have other interesting properties. Some of these, for example the date on which thedocument was produced, are in one-to-one correspondence with documents. Such properties can bedefined by specifying a relation or property as being keyed on the document:publDate: Property = DeclareProperty["publDate", Document, StringType, Key];We are using the convention that domain names are capitalized and relation, attribute, and propertynames are not capitalized, both for the Cedar Mesa variable names and in the names used in thedatabase system itself. If and when the database system is better integrated with Cedar Mesa, the Cedar anddatabase names will be one and the same.We might wish to include additional information for particular kinds of documents, for exampleconference papers. Conference papers may participate in the same relations as other documents.For example, they have authors. In addition, we may want to define relations in which onlyconference papers may participate, for example a presentation relation which defines who presentedthe paper, and where. We can define a conference paper to be a sub-domain of documents, and]"ptFpt pjUG_jSjO6pu p- up jMup upjJY{FuX'{D@{@TIjd #>QDTCYPRESS DOCUMENTATION44<==2UD`D`@@D`@CCCD`C@>UC`BCQ4Cl@CCg ClG,BCK4/D@D@> UBCZBpB 3@CڃCڂCZ݀%~CڂBpB ;@ "DbC>CVCHCHCBBh3>CClDhC,B$BP;>%}%~Dq"Cڂ%}>uV)CZBCW2D@D@CQ2@/ CEDrClC >V7C`CQ2+ACh"ClCCBCK27AD@D`>V)CZ,B$3>BmCڂ%}݀CڂCځCHB$;>B] Cl@DbC ?!VCHBhpBClD CECClG,CZBPB%~CڃDq"CZ%~%~?DUBBDD@D@C`@/BCCDrl ?RU+ABD "DbCBCZ7ABDD@D`?DUZ,BmB%}%~Dq"Cڂ%}CHCH*B]BCl@CCg ClG?!U(n BBm CEDrClC CZB BB]CڃCڂCZ݀%~Cڂ>U,BBAD@D`C`A_BBACClDhC>TBBB Cl@DbC CZ,BBB/D@D@>uUBBpB%~CڃDq"CZ%~%~CH*BpBCh"ClCC>CU(CH CBBm3?CDrl B BB];@Cڂ%}݀CڂCځ> UZ,CZCW4AD@D`A_CQ3AClD CECClG>rLwD`D`@@D`@CCCD`C@>RLwC`BCQ4Cl@CCg ClG,BCK4/D@D@>`LBCZBpB 3@CڃCڂCZ݀%~CڂBpB ;@ "DbC>LCHCHCBBh3>CClDhC,B$BP;>%}%~Dq"Cڂ%}>M CZBCW2D@D@CQ2@/ CEDrClC >MC`CQ2+ACh"ClCCBCK27AD@D`?/M CZ,B$3>BmCڂ%}݀CڂCځCHB$;>B] Cl@DbC ?aLCHBhpBClD CECClG,CZBPB%~CڃDq"CZ%~%~?LBBDD@D@C`@/BCCDrl ?Lw+ABD "DbCBCZ7ABDD@D`?L:,BmB%}%~Dq"Cڂ%}CHCH*B]BCl@CCg ClG?aLn BBm CEDrClC CZB BB]CڃCڂCZ݀%~Cڂ?/K,BBAD@D`C`A_BBACClDhC>KBBB Cl@DbC CZ,BBB/D@D@>KBBpB%~CڃDq"CZ%~%~CH*BpBCh"ClCC>LCH CBBm3?CDrl B BB];@Cڂ%}݀CڂCځ>`L:,CZCW4AD@D`A_CQ3AClD CECClGRick CattellMark Brown rT7 rQw2Qw2T7 rT7 T7 QwD@D@ RT7D@D` rQ2QD@D@ rQWD@D`QwT7D@D`RQwD@D@2T rTD@D`2TWD@D@T7QD@D@T7D@D` I GGI I I GD@D@ ID@D` G7G7D@D@ FD@D`rGrID@D`GD@D@I ID@D`ID@D@RIRGWD@D@ID@D`,V,T5T5V,V-V-TD@D@,VD@D`,T75T7D@D@,SD@D`5T5VD@D`5TD@D@5V,VD@D`5VD@D@1rV1rTWD@D@12VD@D`-RJ-RH6H6J-RJ-rJ-rHD@D@-2JD@D`-RH76H7D@D@-RGD@D`5H5JD@D`62HD@D@6J-RJD@D`6JD@D@1J1HWD@D@1JD@D`Cypress DatabaseAn Analysis ofPriority Queues-2P-2M5M5P-2P-RP-RMD@D@-PD@D`-2M5MD@D@-2MD@D`5M5PD@D`6MD@D@5Pw-2PwD@D`5PD@D@1P1ND@D@1rPD@D`ofofofofofisisis198219774IwEsCr,6;2CrC!CRwAC!˲89 zD[Cb C>pݻBM0Am`@ 6S CYlDq2Cb 4OWE(A B4@"@3;&C' OBC 8QDeڼ)sBܩC C9D`B@B`9OEI|Wʌ(?CPCcCDoa8:A@BDODSn'';NsD?K,@Q A~Cr<!UC@Cr6D[@[:`~A CcD`UCO =#MD[oӽB@B@C1A{7`Cο@C)D[B@ %@CDi8Cޫ<4SUEhVqAIB# D@?T@D@0ҿ 95Ce AW<|A DCD]}19RUE*@"=1C[^AR.CAπ0C4AFBz CD`?T.:U8?\B??&߀耽pCDlBEoDBALO@ C9B2fC8*:T8746ZW ཆCZ)D8$CDhBDE̒DVө6PC B]PCB2<sC%S7p;,D{C~'AQ@DAD^FAِCECB88#C.NpdDCAAo>1LƀBpDJ(DXdĀEpc h*AD€A@C䀽<@9B(C*OWDW0HCspCBDU5@DMEmT#jC@D{n̼n8C9@BpC;#P8DpCDk. CoDc@C Es뾶CP LCfCڂC>5B C>-Rxq*CĪ@i, CpDc@C L Ddc5V?C^?Ϋ?FCx@ KCoCSHEjˀC-&CB(߀=܀CһRڻDQCm`'A DCD]݀=Z#HE;DLN`;GDF̗Cc\`C>BoXC?6 CKC@@մfC=C DgxB#(oIE:DLQ:D@軍*NC:Cր<@ZA`CՀ!vCQ9Bz@@?B`3bC_DfdBoPRERQB׬FBRШC@A @0Cـ<׬7,BA/WC)Da@AQR0SEC\G@C]3BQ+]tCBWPC.|b(zB~2&0C}DcA&HE2`CAg?BGW@+CA߀:C.dCX 3D<`B @CDeBa怼IEʈCM]CCƐ B=CiAD4C7eDB]AA漀2:C_Db AisisrwD`D`@@D`@CCCD`C@RwC`BCQ2ClBCC@h ClB,BCK2/D@D@`BCZBqB$3=CڂCڂCZ%} CڂBrB$;= $DbCCHCHCBBh3=CClBgC,B%BP;=%}%}}Dq#@Cڂ%}  CZBCW1D@D@CQ10/ @CEDrClB C`CQ1+ACh`$ClBCBCK17AD@D`/ CZ,B%3=BmCڂ%}}CڂCڂCHB%;=B] @ClBDbC aCHBhnBClB CECClB,CZBPB%}CڂDq#@CZ%} %} BBBD@D@C`0/BACDrg w+ABB $DbCBCZ7ABBD@D`:,BmB%}%}}Dq#@Cڂ%} CHCH*B]BClBCCh ClBamBBm @CEDrClB CZBBB]CڂCڂCZ%} Cڂ/,΀BBAD@D`C`΀A_BBACClBgC΀BBB @ClBDbC CZ,΀BBB/D@D@BBrB%}CڂDq#@CZ%}@%} CH*BrBCh`$ClBCCHCBBm3<CDr g BB#B];=Cڂ%}}CڂCڂ`:,CZCW2AD@D`A_CQ1AClB @CECClB,,::,,,D@D@,rD@D`,:D@D@,D@D`99D@D`:2D@D@:,D@D`:7D@D@00D@D@0D@D`55D@D@5rD@D`R.D`D`@@D`@CCCD`C@2.C`BCQ2ClBCCh ClC,BCK2/D@D@@.BCZBrB$3>CڂCڂCZ݀%} CڂBrB$;> $DbCc/&CHCHCBBh3=CClDgC,B$BP;=%}%~}Dq"Cڂ%~/ICZBCW2D@D@CQ2@/ CEDrClB /WC`CQ2+ACh"ClBCBCK27AD@D`/ICZ,B$3=BmCڂ%}CڂCڂCHB$;=B] Cl@DbC A/&CHBhnBClB CECClC,CZBPB%}CڃDq#@CZ%} %~d.BBBD@D@C`0/BACDrh r.+ABB $DbCBCZ7ABBD@D`d.z,BmB%}%~}Dq"Cڂ%~CHCH*B]BClBCCh ClCA.Hn BBm CEDrClB CZB BB]CڂCڂCZ݀%} Cڂ.%,BBAD@D`C`A_BBACClDgC.BBB Cl@DbC CZ,BBB/D@D@.%BBpB%}CڃDq#@CZ%} %~CH*BpBCh"ClBCc.HCHCBBm3=CDrh BB#B];>Cڂ%}CڂCڂ@.z,CZCW2AD@D`A_CQ1AClB CECClC?1D`D`@@D`@CCCD`C@>1C`BCQ2Cl@CCh ClC,BCK2/D@D@?1TBCZBpB$3>CڃCڂCZ݀%~CڂBpB$;> "DbC?#1CHCHCBBh3>CClDhC,B$BP;>%}%~Dq"Cڂ%~?U1CZBCW2D@D@CQ2@/ CEDrClC ?1C`CQ2+ACh"ClCCBCK27AD@D`?1CZ,B$3>BmCڂ%}݀CڂCڂCHB$;>B] Cl@DbC @1CHBhnBClD CECClC,CZBPB%~CڃDq"CZ%~%~@$1TBBBD@D@C`@/BACDrh @21+ABB "DbCBCZ7ABBD@D`@$0,BmB%}%~Dq"Cڂ%~CHCH*B]BCl@CCh ClC@0n BBm CEDrClC CZB BB]CڃCڂCZ݀%~Cڂ?0,BBAD@D`C`A_BBACClDhC?0wBBB Cl@DbC CZ,BBB/D@D@?U0BBpB%~CڃDq"CZ%~%~CH*BpBCh"ClCC?#0CH CBBm3=CDrh B B#B];>Cڂ%}݀CڂCڂ?0,CZCW2AD@D`A_CQ1AClD CECClC?R'D`D`@@D`@CCCD`C@?2'C`BCQ2Cl@CCh ClC,BCK2/D@D@?@(4BCZBpB"3>CڃCڂCZ@%~CڂBpB";> "DbC?c(fCHCHCBBh3>CClBhC,B$BP;>%}%}Dq"Cڂ%~?(CZBCW2D@D@CQ20/ CEDrClC ?(C`CQ2+ACh$ClCCBCK27AD@D`@(CZ,B$3>BmCڂ%}݀CڂCڂCHB$;>B] ClBDbC @A(fCHBhoBClD CECClC,CZBPB%~CڂDq"CZ%~%~@d(4BBBD@D@C`@/BACDrh @r'+ABB "DbCBCZ7ABBD@D`@d',BmB%}%}Dq"Cڂ%~CHCH*B]BCl@CCh ClC@A'nBBm CEDrClC CZBBB]CڃCڂCZ@%~Cڂ@'e,BBAD@D`C`A_BBACClBhC?'WBBB ClBDbC CZ,BBB/D@D@?'eBBtB%~CڂDq"CZ%~%~CH*BtBCh$ClCC?c'CH CBBm3=CDrh B B!B];>Cڂ%}݀CڂCڂ?@',CZCW2AD@D`A_CQ1AClD CECClCRick CattellMark Brown-2W-/6/62W-2W-2W-/D@D@-2WD@D`-/6/D@D@-/wD@D`6r/6r2WD@D`6/D@D@627-27D@D`62wD@D@2R2W2R/D@D@22WD@D`.,.)W6)W6,.,.2,.2)WD@D@-,D@D`.)w6)wD@D@.)7D@D`6)W6,D@D`6)WD@D@6+.+D@D`6,7D@D@2+2)WD@D@2r+D@D`ofofisis5*E(A B4@"@3;C'$O@BC8QDeڼ)s9BܩC ZC9D`B@B`:*EI|Wƌ(@@~CPCcC@Doa8:A@BDODSo''@<)D?K,@Q A~xCr<!SC@Cr6D[@[;`~A CcD`UCO >)RD[oӽB@B@C1A{7bCο@C)D[B@ %@CDi8Cެ</0?\B??&耽tCDlÀBEoDBALo@C9B|2fC8+/746ZW ཆCZ)E8(CDhBDE̒DVө6PC B]PCB2<sC&v.p;,D{C~'AQ@DAD^FAِCECB88#C.*WpdDCAAo1DƀBpDJ(DXcEpc h*AD€A @C䀽<@9B(C**DW0HCspC|B DU5@DMʀEmT#jC@D{n n8C9@BpC:$+DpCD˽. CoDc@C @Es뾶CP LCfCC>5@B C> -q*CĪ@h., CpDc@C L Ddc5V?I^?Ϋ?CCx@ JCoC@ConferencePapersub-domain of Documentwhich can participate in a "presentation" relation.AuthorrelationPresentationrelation8REpXN CbCB03@C h뻣PD]C`AD@D_@;D{u:C~rBbsLBg,pBAC:C{0l C: Ub[NBb BqAqHCKDl@B0~<sBR Bo--DrC=VDIWDivBRPBMcBN+C]CDAG@C]T6>F HA(B6$,"Dk}Cڀ6`=DsBEIVмCҶC@dJB4CDRTB3꺬 8Cf 6D^C6>s!]DϢEB{xCQ7pBCDSB B; {G?(8gTDQC̀.`Do*rn@\@X )C@$CπCC@$& E޼֘B\BG?CDn:i Q(Dκ;TA CݺCCCu"/ZBCCu!EzDuDJd,_4CDl40 $Ce^ABπAc`CȽCR@CȾ2DihfBNpBxAe @I`CЀDr&.`!,$ D«wCRCW@5C(CC'XDӲB:CKB`b7BCRDs\AyP7B"b"EI@CC-TCm7j@*qCȖCma/D%% CWPCSAf$# CDpy@Cf(#$ EZiA`RAs)"!@Dp(C@)!CuC~pAcPApCϺC#Cz"CϺ1J?AٳBYBB5DsSC&DjDǨQABEBI-XCCClL@!C03ѻ B}hBjA٘ CMDqCg @D8DB伸$BlB(BF0Aw0CUC'A``5؀CU`/eм.CE3BJAHC܀DkBDBC奚3hvCBDVDK @vEgD~=#Aw@Bw0C(!BC# LDUBɜ!'ؽ=!RBDTDO R`E». hBaA`C@CBC+$DZ;' ѐA&BNB:DR] DPEfr2b-A@9`C BCACM SIGMOD 1982The Cedar DBMS: APreliminary Report.87.5w65w687.87.287.25wD@D@-87D@D`.565D@D@.5WD@D`65w687D@D`65wD@D@68.8D@D`68WD@D@28725D@D@2R87D@D`?77D`D`@@D`@CCCD`C@>77C`BCQ2Cl@CCh ClC,BCK2/D@D@?7tBCZBpB$3>CڃCڂCZ݀%~CڂBpB$;> "DbC?#7CHCHCBBh3>CClDhC,B$BP;>%}%~Dq"Cڂ%~?U7CZBCW2D@D@CQ2@/ CEDrClC ?7C`CQ2+ACh"ClCCBCK27AD@D`?7CZ,B$3>BmCڂ%}݀CڂCڂCHB$;>B] Cl@DbC @7CHBhnBClD CECClC,CZBPB%~CڃDq"CZ%~%~@$7tBBBD@D@C`@/BACDrh @277+ABB "DbCBCZ7ABBD@D`@$6,BmB%}%~Dq"Cڂ%~CHCH*B]BCl@CCh ClC@6n BBm CEDrClC CZB BB]CڃCڂCZ݀%~Cڂ?6,BBAD@D`C`A_BBACClDhC?6BBB Cl@DbC CZ,BBB/D@D@?U6BBpB%~CڃDq"CZ%~%~CH*BpBCh"ClCC?#6CH CBBm3=CDrh B B#B];>Cڂ%}݀CڂCڂ?6,CZCW2AD@D`A_CQ1AClD CECClC56E?~BA3A4CAڰB%\C<~A3@BgAFCDacAZ`9Q6EC` CYBL9@CBMpoC$xZ'ByV| %PC`DbAڤ 41ECr8@PAECpC@'C.:H`DUcfBc@"BvDJDW90EЃBuDRBb^CB7(C@0A޻NW@A#CpClD`@@Nori Suzuki/^6Y02BaGA@AS*`gB<Ds C}cg@EDD03Cgs@6̽* B-CCC\P CC@-"5DCd6DC67Ds[CEu.-.$+c4'&$9,"nR "*&D4y"4+*O;:$ 6 $4 Z"0B@/Ddr >Q\OCYPRESS DOCUMENTATION46InsertData: PROC = BEGIN t: Relship; tty.PutF["Inserting data...\n"]; cedarPaper_ DeclareEntity[ConferencePaper, "The Cedar DBMS"]; cypressDoc_ DeclareEntity[Document, "Cypress DB Concepts & Facilities"]; thesis_ DeclareEntity[Thesis, "An Analysis of Priority Queues"]; sigmod_ DeclareEntity[Conference, "SIGMOD 81"]; rick_ DeclareEntity[Person, "Rick Cattell"]; mark_ DeclareEntity[Person, "Mark Brown"]; -- Note we can create entity and then set name... nori_ DeclareEntity[Person]; ChangeName[nori, "Nori Suzuki"]; -- Data can be assigned with SetP, SetF, or DeclareRelship's initialization list: t_ DeclareRelship[presentation,, NewOnly]; SetF[t, presentationtOf, cedarPaper]; SetF[t, presentationBy, mark]; SetF[t, presentationAt, sigmod]; []_ SetPList[cypressDoc, authorIs, LIST[rick, mark]]; -- the Cedar notation LIST[ ... ] defines a list []_ SetPList[cedarPaper, authorIs, LIST[rick, mark, nori]]; []_ DeclareRelship[author, LIST[[authorOf, thesis], [authorIs, mark]]]; []_ SetP[cypressDoc, publDate, I2V[1982]]; []_ SetP[thesis, publDate, I2V[1977]]; -- the I2V[...] calls needed because Cedar Mesa does not yet coerce INT to REF ANY -- Check that thesis can't be presented at conference: ok_ FALSE; t_ DeclareRelship[presentation]; SetF[t, presentationOf, thesis ! MismatchedAttributeValueType => {ok _ TRUE; CONTINUE}]; IF NOT ok THEN ERROR; END;DestroySomeData: PROCEDURE = -- Destroy one person entity and all frog entities BEGIN flag: BOOL_ FALSE; tty.Put[char[CR], rope["Deleting Rick from database..."], char[CR]]; DestroyEntity[DeclareEntity[Person, "Frank Baz", OldOnly]]; DestroyDomain[Frog]; END;PrintDocuments: PROC = -- Use DomainSubset with no constraints to enumerate all Documents BEGIN doc: -- Document -- Entity; authors: LIST OF Value; es: EntitySet; tty.PutF["Documents:\n\n"]; tty.PutF["Titleauthors\n"];\rptFpt p{TuX{R{Q"{O7?{MlJ{KB{I1{H .{FB,{Dw3{B{@"{?S{=M,{;){9"{7${6"7{4X4{2={0I{.,{--({+cV{)8{' {&"{$8{"n={ {{C{y4{{F{={N{{ { $D{ Y{{{{/{d6 z M 6]APPLICATION EXAMPLE47 es_ DomainSubset[Document]; WHILE (doc_ NextEntity[es])#NIL DO tty.PutF["%g", rope[GetName[doc]]]; authors_ GetPList[doc, authorIs]; FOR al: LIST OF Entity_ NARROW[authors], al.rest UNTIL al=NIL DO tty.PutF["%g ", rope[GetName[al.first]]]] ENDLOOP; ENDLOOP; ReleaseEntitySet[es]; END;PrintPersonsPublications: PROC [pName: ROPE] = -- Use RelationSubset to enumerate publications written by person BEGIN p: Person_ DeclareEntity[Person, pName, OldOnly]; authorT: --author-- Relship; rs: RelshipSet; first: BOOL_ TRUE; IF p=NIL THEN {tty.PutF["%g is not a person!", rope[pName]]; RETURN}; tty.PutF["Papers written by %g are:\n", rope[pName]]; rs_ RelationSubset[author, LIST[[authorIs, p]]]; WHILE (authorT_ NextRelship[rs])#NIL DO IF first THEN first_ FALSE ELSE tty.Put[rope[", "]]; tty.Put[rope[GetFS[authorRS, authorOf]]]; ENDLOOP; tty.PutF["\n"]; ReleaseRelshipSet[rs]; END;tty.Put[rope["Creating database..."], char[CR]];Initialize[];DeclareSegment["[Local]Test", $Test, 1,, NewOnly];OpenTransaction[$Test];Initialize[];InsertData[];PrintDocuments[];PrintPersonsPublications["Mark Brown"];DestroySomeData[];PrintDocuments[];CloseTransaction[TransactionOf[$Test]];tty.Close[];END.gWptF pt9pO7uXMl$KwI%H DFB8Dw B@=M.;C9736"4X20.;--7+b2))'8&-$8 "m x0 2N   ' # Y' d +oX, HELVETICA HELVETICA  HELVETICA HELVETICA  TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN HELVETICA  HELVETICA  HELVETICA  HELVETICA  TIMESROMAN  TIMESROMAN  TIMESROMAN  HELVETICA  TIMESROMAN  TIMESROMAN HELVETICA  HELVETICAGACHA  TIMESROMAN j  *&PW]2@ !  '.6<BHPW/^ah)nv}P;rI6P0b'?bi~dCd>z􌻊bbb~bºazbN~d>bbj//PCypressDoc.pressCattell15-Jun-83 9:47:27 PDT: