Information Modeling and Relational Databases From Conceptual Analysis to Logical Design The Morgan Kaufmann Series in Data Management Systems SeriesEditor:JimGray,MicrosoftResearch InformationModelingandRelational JoeCelko’sSQLforSmarties: PrinciplesofTransactionProcessing Databases:FromConceptualAnalysis AdvancedSQLProgramming,Second PhilipA.BernsteinandEricNewcomer toLogicalDesign Edition UsingtheNewDB2:IBM’sObject- TerryHalpin JoeCelko RelationalDatabaseSystem TransactionalInformationSystems: JoeCelko’sDataandDatabases: DonChamberlin Theory,Algorithms,andPracticeof ConceptsinPractice DistributedAlgorithms ConcurrencyControlandRecovery JoeCelko NancyA.Lynch GerhardWeikumandGottfriedVossen DevelopingTime-OrientedDatabase ActiveDatabaseSystems:Triggersand SpatialDatabases:WithApplication ApplicationsinSQL RulesforAdvancedDatabase toGIS RichardT.Snodgrass Processing PhilippeRigaux,MichelScholl,and WebFarmingfortheDataWarehouse EditedbyJenniferWidomandStefano AgnesVoisard RichardD.Hackathorn Ceri SQL:1999—UnderstandingRelational DatabaseModeling&Design,Third MigratingLegacySystems:Gateways, LanguageComponents Edition Interfaces,&theIncrementalApproach JimMeltonandAlanR.Simon TobyJ.Teorey MichaelL.BrodieandMichael ComponentDatabaseSystems Stonebraker ManagementofHeterogeneousand EditedbyKlausR.Dittrichand AutonomousDatabaseSystems AtomicTransactions AndreasGeppert EditedbyAhmedElmagarmid,Marek NancyLynch,MichaelMerritt,William ManagingReferenceDatain Rusinkiewicz,andAmitSheth Weihl,andAlanFekete EnterpriseDatabases:Binding Object-RelationalDBMSs:Tracking QueryProcessingforAdvanced CorporateDatatotheWiderWorld theNextGreatWave,SecondEdition DatabasedSystems MalcolmChisholm MichaelStonebrakerandPaulBrown EditedbyJohannChristophFreytag, InformationVisualizationinData withDorothyMoore DavidMaier,andGottfriedVossen MiningandKnowledgeDiscovery ACompleteGuidetoDB2Universal TransactionProcessing:Conceptsand EditedbyUsamaFayyad,GeorgesG. Database Techniques Grinstein,andAndreasWierse DonChamberlin JimGrayandAndreasReuter DataMining:ConceptsandTechniques UniversalDatabaseManagement:A BuildinganObject-OrientedDatabase JiaweiHanandMichelineKamber GuidetoObject/RelationalTechnology System:TheStoryofO 2 UnderstandingSQLandJavaTogether: CynthiaMaroSaracco EditedbyFrançoisBancilhon,Claude AGuidetoSQLJ,JDBC,andRelated Delobel,andParisKanellakis ReadingsinDatabaseSystems,Third Technologies Edition DatabaseTransactionModelsfor JimMeltonandAndrewEisenberg EditedbyMichaelStonebrakerand AdvancedApplications Database:Principles,Programming, JosephM.Hellerstein EditedbyAhmedK.Elmagarmid andPerformance,SecondEdition UnderstandingSQL’sStored AGuidetoDevelopingClient/Server PatrickandElizabethO’Neil Procedures:ACompleteGuide SQLApplications TheObjectDataStandard:ODMG3.0 toSQL/PSM SetragKhoshafian,ArvolaChan,Anna EditedbyR.G.G.CattellandDouglas JimMelton Wong,andHarryK.T.Wong K.Berry PrinciplesofMultimediaDatabase TheBenchmarkHandbookfor DataontheWeb:FromRelationsto Systems DatabaseandTransactionProcessing SemistructuredDataandXML V.S.Subrahmanian Systems,SecondEdition SergeAbiteboul,PeterBuneman,Dan EditedbyJimGray PrinciplesofDatabaseQuery Suciu ProcessingforAdvancedApplications CamelotandAvalon:ADistributed DataMining:PracticalMachine ClementT.YuandWeiyiMeng TransactionFacility LearningToolsandTechniqueswith EditedbyJeffreyL.Eppinger,LilyB. AdvancedDatabaseSystems JavaImplementations Mummert,andAlfredZ.Spector CarloZaniolo,StefanoCeri,Christos IanWittenandEibeFrank Faloutsos,RichardT.Snodgrass,V.S. ReadingsinObject-OrientedDatabase Subrahmanian,andRobertoZicari Systems EditedbyStanleyB.ZdonikandDavid Maier Information Modeling and Relational Databases From Conceptual Analysis to Logical Design Terry Halpin MicrosoftCorporation ExecutiveEditor DianeD.Cerra PublishingServicesManager ScottNorton SeniorProductionEditor CheriPalmer AssistantEditor BelindaBreyer EditorialAssistant MonaBuehler CoverDesign RossCarronDesign CoverImage ©LeslieHarris/PictureQuest TextDesign MarkOng,SidebySideStudios Copyeditor KenDellaPenta Proofreader JenniferMcClain Composition/Illustration Technologies’NTypography Indexer TyKoontz Printer CourierCorporation Designationsusedbycompaniestodistinguishtheirproductsareoftenclaimedastrademarksorregistered trademarks.InallinstancesinwhichMorganKaufmannPublishersisawareofaclaim,theproductnames appearininitialcapitalorallcapitalletters.However,readersshouldcontacttheappropriatecompaniesfor morecompleteinformationregardingtrademarksandregistration. MorganKaufmannPublishers 340PineStreet,SixthFloor,SanFrancisco,CA94104-3205,USA http://www.mkp.com ACADEMICPRESS AHarcourtScienceandTechnologyCompany 525BStreet,Suite1900,SanDiego,CA92101-4495,USA http://www.academicpress.com AcademicPress HarcourtPlace,32JamestownRoad,London,NW17BY,UnitedKingdom http://www.academicpress.com ©2001byAcademicPress Allrightsreserved PrintedintheUnitedStatesofAmerica 05 04 03 02 01 5 4 3 2 1 Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmittedinanyformorby anymeans—electronic,mechanical,photocopying,recording,orotherwise—withoutthepriorwrittenper- missionofthepublisher. LibraryofCongressCataloging-in-PublicationData Halpin,T.A. Informationmodelingandrelationaldatabases : fromconceptualanalysistological design / TerryHalpin. p. cm. Includesbibliographicalreferencesandindex. ISBN1-55860-672-6 1.Databasedesign. 2.Relationaldatabases. I.Title. QA76.9.D26H3552001 005.75(cid:2)6—dc21 00-053468 Thisbookisprintedonacid-freepaper. To Norma, my wonderful wife. Here’s to another 30 years! —Terry Halpin This Page Intentionally Left Blank Contents ForewordbyJohnZachman ForewordbyRobertMeersman ForewordbyGordonEverest Preface 1 Introduction 1 1.1 InformationModeling 2 1.2 ModelingApproaches 6 1.3 SomeHistoricalBackground 18 1.4 TheRelevantSkills 22 1.5 Summary 23 2 Information Levels and Frameworks 25 2.1 FourInformationLevels 26 2.2 TheConceptualLevel 30 vii viii Contents 2.3 FromExternaltoConceptualtoRelational 40 2.4 DevelopmentFrameworks 47 2.5 Summary 53 3 Conceptual Modeling: First Steps 55 3.1 ConceptualModelingLanguageCriteria 56 3.2 ORM’sConceptualSchemaDesignProcedure 58 3.3 CSDPStep1:FromExamplestoElementaryFacts 60 3.4 CSDPStep2:DrawFactTypes,andPopulate 78 3.5 CSDPStep3:TrimSchema;NoteBasicDerivations 93 3.6 Summary 104 4 Uniqueness Constraints 109 4.1 CSDPStep4:UniquenessConstraints;ArityCheck 110 4.2 UniquenessConstraintsonUnariesandBinaries 111 4.3 UniquenessConstraintsonLongerFactTypes 123 4.4 ExternalUniquenessConstraints 129 4.5 KeyLengthCheck 140 4.6 Projection-JoinCheck 153 4.7 Summary 158 5 Mandatory Roles 163 5.1 IntroductiontoCSDPStep5 164 5.2 MandatoryandOptionalRoles 166 5.3 LogicalDerivationCheck 179 5.4 ReferenceSchemes 186 5.5 CaseStudy:ACompactDiscRetailer 206 5.6 Summary 210 6 Value, Set-Comparison, and Subtype Constraints 215 6.1 CSDPStep6:Value,Set,andSubtypeConstraints 216 6.2 BasicSetTheory 216 6.3 ValueConstraintsandIndependentObjects 220 6.4 Subset,Equality,andExclusionConstraints 229 Contents ix 6.5 Subtyping 244 6.6 GeneralizationofObjectTypes 266 6.7 Summary 274 7 Other Constraints and Final Checks 277 7.1 CSDPStep7:OtherConstraints;FinalChecks 278 7.2 OccurrenceFrequencies 278 7.3 RingConstraints 283 7.4 OtherConstraints 295 7.5 FinalChecks 304 7.6 Summary 310 8 Entity Relationship Modeling 313 8.1 OverviewofER 314 8.2 BarkerNotation 316 8.3 InformationEngineeringNotation 327 8.4 IDEF1X 332 8.5 MappingfromORMtoER 343 8.6 Summary 346 9 Data Modeling in UML 349 9.1 Introduction 350 9.2 ObjectReferenceandSingle-ValuedAttributes 352 9.3 Multi-valuedAttributes 357 9.4 Associations 362 9.5 SetComparisonConstraints 370 9.6 Subtyping 378 9.7 OtherConstraintsandDerivationRules 382 9.8 MappingfromORMtoUML 396 9.9 Summary 399 10 Relational Mapping 403 10.1 ImplementingaConceptualSchema 404 10.2 RelationalSchemas 405