[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci & Eng Dept] / [R J Botting] /[CS372 Course Materials] /d3.html [d3.txt(Text)] [Search ] Wed Nov 11 09:33:20 PST 2009
[About] [News] [Schedule] [Syllabus] [Glossary] [Contact] [Grades]
Readings Analysis [1] [2] [3] [4] [5] Choices [1] [2] [3] Data [1] [2] [3] [4] Requirements [1] [2] [3]
[Review] Field Trips [1] [2] [3] Project Iterations [1] [2] [3] [4] [5]
Opening the PDF files on this page may require you to download Adobe Reader or an equivalent viewer (GhostScript).

Contents

    Entity Relationship Models

      Data Design Concepts

      1. Data design is critical in computer systems. You have already studied the discovery and documentation of data as it flows through an enterprise [ a4.html ] , you have designed data flows [ a5.html ] [ c1.html ] , and studied the design of data elements [ d2.html ] and the presentation and input of data [ d1.html ] from a user. You have looked at combining elements into records. These next two topics about about organizing many kinds of of records into a workable and reliable data base. Modern data storage is always called a data base even if it consists of a single file of student names and addresses. All the data stores in a DFD are conceptually in one data base.

      2. (conceptual models): The purpose of stored data is to represent a part of the current reality. The data should be a mirror of the world outside the computer. So a wise way to design data is to start with creating a picture of the stake holder's world. We call this a conceptual model. We use Enity-Relationship Diagrams (ERDs) to draw a picture of it. Notice the importance of the stakeholder's ideas. These form an excellent entry into data base design.

      3. ERD::acronym="Entity Relationship Diagram", a simple visual model of a set of concepts or logical data groups.

        The entity relationship diagram gathers all types of records -- from all over the system -- into one place and works out how they are related. It then maps directly into the structure of most DBMSs.

        An ERD shows a single database -- or a part of a larger database. There is no official way in an ERD to indicate that data is spread out over several data bases or file systems -- largely because it is a tool for integrating data onto one system. Even when you distribute data over several servers you need to first draw a single data base that ignores the deployment. It is (in my experience) rare -- probably due to some strange non-functional requirement -- that you distribute data over several "systems". And example would be the Internets DNS system -- millions of servers with their own data but linked into a single data base. ERD are not used to describe the placement of data in a system. We use an UML deployment diagram to show how we distribute various parts of a system onto hardware. We use them to show that some data is held on one system and the rest of it elsewhere. We saw these in [ a3.html ] earlier in this course.

      4. Later we will talk about another entry into data base design: samples of existing and planned data. There is a process that extracts an ideal data base design from samples of data. The process is called normalization. The details are later but much normalization can be done directly on a ERD/UML class diagram. Here is a picture summarizing ways to normalize a ERD:

        [Normaliing a ERD]

      5. Inside a data base there is a lot of computer science: CS330 Data structures, CS350 File Structures, etc.. We have a required BA course on Data Bases: CSCI572. These notes here are just an introduction to a fascinating and lucrative field.
      6. (The Principle of Locality): Data is processed most quickly in the order in which it is stored. Example: Telephone directories. It is designed to make it easy to find Joe Coyote's address in a phone book. However, it is not easy to find Joe Coyote's neighbor's name using a phone book.
      7. Data bases are first designed as Logical data bases and then fitted to a particular Physical design to meet performance requirements. The logical model is (nowadays) always a normalized entity-relationship model.
      8. DBMS::=Data Base Management Systems. Examples with links to information later.
      9. DBA::=Data Base Administrator. The guru who maintains the structure and integrity of the data base.
      10. guru::="a person who has arcane knowledge and expertise", roughly synonimous with rabi, wizard, and sensei.

      DBMS Components

      1. A DataBase Management System (DBMS) supports three kinds of interface: User + DBA + API. The user interface is special purpose software that makes it easy for the user to read, write, update, ... data. The DBA has a more technical interface that includes the creation and deletion of new types of data. The API is programmers to write programs that read and write data in the data base. An example is the Java DataBase Connectivity package -- JDBC These days DBA's and programers typically use the Structured Query Language --SQL to define and access data in the data base. You would be wise to get some experience of SQL before you go hunting for a job! The DBA can define special views and applications that let Users access the right data. Programs can use the DBMS API (Application Programmer Interface) to meet stakeholder needs.
      2. Schema::="a description of all the records, links, reports, triggers, ... making up the data base". This is also called a data dictionary.
      3. Physical data -- the underlying coding and data structures.

    Web-based database design

    1. Many modern web pages are just an elegant and easily used front-end to a complex data base. The connection between the web and the data base is called middle-ware. Sometimes the web server, the middle-ware, and the data base are all different computers. This is called a multi-tier architecture.
    2. Security is a vital concern when you hook up the web to a data base (or anything else). Security Rule 1: never store unencrypted passwords in a data base.

    Data Design Terminology

      Entity

       An entity is something that we need to keep track of in the real world, also used for the data we store about a "real" entity. This can be confusing. Examples -- me and this class are entities in CSUSB and we have our data stored in CMS (and some other systems no doubt).

      Relations

       Relationships (relations) link entities together in the real world. Example -- "Dick is married to Tricia". Example -- "Dick teaches this course". These are reflected by special tables in a data base. A relation is a set of facts all with the same template: 
       _____ is taking class _____ with teacher ____ at time ____
      Filling in the blanks generates facts. Listing the blanks in a template gives us a table in a data base! A Binary relation would have a sentence with two blanks, a ternary with 3, and so on. The number of columns equals the number of blanks in the template.

      Entity type

       A collection of entities that all have similar data. Sometimes we deliberately use the word "entity" to refer to an "entity type". Examples -- I have entity type "Faculty", and this class is a "Class".

      Record Tuple or Row

       A collection of named data elements that should reflect some facts about a real world entity. Example -- "My record showing I teach this class" 
       		 RBOTTING   CS372
    1. A Record is also called a row because it is displayed as a row in a table of similar records.
    2. Records are also called Tuples because of the underlying discrete mathematical model of an "n-tuple". In mathematics (1,2,3) is a 3-tuple and (3,4,5,6) is a 4-tuple and so a tuple is any list of data items!
    3. Records are also called " Logical Data Groups " because a record is a collection of data elements that go together.

      Table or File

       A set of similar records -- all reflecting the same type of entity and (ideally) having the same structure.
    4. Example: the CSCI Schedule for the next quarter.
    5. Many tables describe the attributes or properties of a set of entities.
    6. Other tables relate different entities. For example this table is part of a "Teaches" table:
      Table
      TeacherCourse
      RBOTTINGCS372
      TYUCS310
      KVOIGTCS201
      ......

      (Close Table)
    7. Most tables/files describe both the attributes of an entity and the other entities it is related to.
    8. Some keep track of real relationships between entities. The above table relates the entity Teacher and the Entity Course.
    9. Some keep track of complicated properties between many entities/values. Each row represents a sentence that is true:
    10. CSCI372 section 01 is taught in JBH372 at 4-6pm TuTh by RBOTTING
      Table
      CourseSection RoomTimeTeacher
      CSCI37201JBH1464-6pm TuThRBOTTING
      ...

      (Close Table)

      Field or Column or Attribute

       A field is named data elements with a given name in a column of a table or file. The word field goes back to the days of punched cards. A field (or column) is also called an attribute. All attributes in a column or field must have the same type of data element. In the above table there is a column for Section, Room, Time, and Teacher. In a normalized table each column is either an item of data of a particular type or the identifier or Key of a row in another table.

      Diagrams have special ways to show the fields/columns/attributes in a table/file/entity. You need to know them all since all are in use.

      Key

      Keys are fields or attributes that uniquely identify records in files/tables uniquely. They are used to connect the different tables in a data base together. I will show how these are documented in an ERD when we cover normalization. There are many types of key: primary, candidate, foreign, secondary. They are the heart of normalization and the most popular type of database: the relational data base. Relational data bases and normalization are in [ d4.html ] and will covered later.

      Cardinality and Multiplicity

       The data base community talk about Cardinality and the UML community talk about multiplicity. In both cases the question is
    11. For each X, how many Y's are there?

      The common answers are: one, many, zero or one, and one or more.

    12. Example each section in CSUSB is given a unique number but a course has many sections. Some relations relate a single entity to a single entity. We say these are one-to-one relations. An example is the relation between an SSN and a resident in the united states. Similarly some relations are said to be "one-to-many". An example is: a teacher may teach many classes and each class is taught by one teacher. Finally you can have relations link many entities to many entities. For example, a student takes many classes and a class has many students. It turns out that these difference are vital for getting a data base that works. There are 3 popular ways of indicating the number of entities -- the cardinality or multiplicity,

      [Three popular Notations for multiplicity]

      In a relational database we talk about tables and each row in the table is an object or entity. Cardinalities and Multiplicities count how many entities are found in a given table's columns -- is each one unique or are there many of them.

    Summary of the theory of conceptual data bases

     Data reflects the world. Records reflect entities. Tables reflect properties of entities and relationships between entities.

    A Conceptual Data Base Design Process

    1. Start with your notes and recordings of interviews, your DFDs, and the data dictionaries you already have.
    2. List the kinds of facts that you want to record about the world outside the computer.
      1. "Dick Botting is 6ft 3in high and teaches CSCI372"
      2. "RBOTTING teaches CSCI372"
      3. "RBOTTING teaches CSCI489"
      4. "CSCI372 has 24 students"
      5. "Student Jo Coyote is taking CSCI372"
      6. ...

    3. When the facts contain words like "and" or "or" split them up into simpler facts: Example: "Dick Botting is 6ft 3in high". "Dick Botting teaches CSCI372"
    4. Look for nouns that are used by the stakeholders, these are often entities. But what type of entity are they? Are they aliases -- alternative names of entities you've already spotted? Do they pass the "Point at it" test -- is there a way, in the real world to identify a unique entity with this name?
    5. Look for data that acts as an identifier. Look for names that end "...ID", "...Number", etc. When the user has gone to the trouble of assigning an identifier to something then it is probably an entity in that user's world. For example our courses have numbers so we can expect there to be an entity called "Course" in a system for this campus. Example -- This class has the Id "CSCI372". THese are an excellent source for "candidate Keys". They are nearly always the kind of thing you will need as an entity in your data base.
    6. Work out the best name for the types of entity. Good names come from the user's world.
    7. Look for facts that assert simple properties of entities -- especially measurements, counts, and strings. These are likely to be attributes/elements/fields/columns. Again give attributes a good name.
      1. Example: "Dick Botting is 6ft 3in high". Attribute name: height.
      2. Example: "CSCI372 has 24 students". Attribute: classSize.

    8. Now look for facts that relate two or more entities -- typically by using their names and Ids. Example: "Dick Botting teaches CSCI372" You'll find these in samples of data and not in the statements that people make to you when you interview them. These become relationships. Relationships a stored as tables/files/entities in your data base.

      What is an Entity

        First, it should be something that exists (or is imagined) outside the system you are designing.

        Second, there must be many occurrences of the entity. So, we don't store the name of CSUSB in a CSUSB data base: there is only one CSUSB. However in the Chancellor's office CSUSB will be an occurrence of the entity Campus.

        Third, the occurrences should be identifiable and countable. Thus Butter is not an entity, but CaseOfButter would be. On current and/or planned systems is there an ID or number(#)? How many occurrences are there currently? Record this "frequency" because it will determine the speed of the resulting programs!

        Fourth, it may be something that has data stored in the current system. It is nice if it is something that will need to have data stored in the future system. So, in a system about students and faculty, Student and Faculty are likely to be entities. Ask: If we lost the data, how much damage would this do to the enterprise? For example, CSUSB doesn't get hurt much if it doesn't know the color of your hair. Notice: you can extract a lot of structure from existing and proposed input and output formats. [ d4.html ]

        Fifth, the occurrence should have interesting life cycles that last longer than a single program, function, or application. Ask: when do these entities get created and when are they destroyed?

        Finally, most attributes are not entities. For example, Address may be an entity but NumberOnStreet is not. Things that are elementary data -- numbers, measurements, character strings, etc don't make good entities. They will end up as attributes/fields/columns of an entity/class/table. Be careful to distinguish attributes from identifiers and keys which point to entities. Also do not confuse the identifier/key with the type of entity it points at: The ISBN is an identifier for "Book" but is not itself an entity. Book is an entity with attribute ISBN.

      How do I find entities

      1. Talk to stakeholders and see what is important to them. How much would they pay to have data on this kind of entity on file?
      2. Look at the stores and flows in your DFDs.
      3. Start from some sample documents and look for the identifiers embedded in them. For example, a class roster identifies the Section and has the identifiers for a number of Students. Hence we can assume that "Student" and "Section" are entities.

      How do I find relationships

        Write down sentences that describe important facts: facts that your system will need to keep track of: 
         Student "J Coyote" has enrolled in section "01" of class "#CSCI372".
        Given that "Student" and "Section" are entities in your ERD then you have uncovered the relationship: "Enrollment" between them. You can also see another relationship in the above sentence: Each "Section" is for a particular "Course". Exercise: sketch a quick informal ERD showing: Course, Section, Enrollment, and Student.

    ERDs -- Entity Relationship Diagrams

    1. It helps to have a diagram showing the Entity types and the Relations that hold between them. They were introduced in [ a4.html#Modeling Entities and Relationships in the UML ] previously.
    2. ERD::="A diagram showing Entity and Relation Types".
    3. An ERD shows types of entities + relationships between them.
    4. There are ERD notations: Chen vs UML

      [Chen and Unified notations]

    5. Not all relationships have only two entities involved in them and there are different notations and philosophies.

      [n-ary relationships]

    6. Both ERD notations can include attributes. Some people call the resulting diagrams ERA diagrams.

      [ERA examples]

    7. KISS: Use informal ERDs when gathering data and during interviews. Informal means: leave off the boxes and scribble the names of entity and relationship types. Later use a tool to produce a tidy diagram to present to others or keep in a project file.
    8. Do not invest a lot of time in beautifying ERDs because they change as the project progresses.

    ERD Patterns

      Knowing about patterns lets you make good models quickly. Forgetting them may slow you down a bit as you reinvent the wheel. A design pattern is a common way of resolving a set of conflicting forces. Patterns don't claim to be perfect, but they are one a way of solving a set of design issues. They are common solutions.

      Here are some classic analysis patterns that I've noticed over the years. Use this list to help discover ERD models:

      Any time you find yourself drawing the same diagram for the same reason -- you've found a pattern.

    . . . . . . . . . ( end of section ERD Patterns) <<Contents | End>>

    Check list of ERD Errors


    1. Entities are outside the system and so you never have an entity in an ERD that represents the system.
    2. Plural entity names. Examples: People, Students, Adults, Children. Exception when the entity is actually a grouping, set, collection, or list of other entities. Example: Class of Students. In the ERD show a box called "Class" associated with "Student".
    3. Showing activities, actors, processes, etc. in an ERD. Entities and relations don't do things. You only show an actor if you need to store data about it. If you need to record an event or an activity that takes place (outside the system) then this will often be encoded in an attribute in an entity rather than a separate entity named after the event or activity.
    4. Showing composition, aggregation, arrows, and operations: these are part of an object-oriented model of software. Keep ERDs simple.
    5. Not preparing a precise definition of when a relation holds. Is it true now, or in the past (a record of an event), or in the future (a contract)?

    ERD Hints

      My Rule: ERDs are always wrong.... but they are always useful. You should plan to draw and redraw ERDs many times. You either need to throw away a lot of drawings, or to do a lot of erasing, or you need a simple graphic modeling tool.

      ERD Hint -- Beware entity types that have only one instance

       These are commonly surrogates for the whole system or the organization in which the system is running. You can nearly always delete them from a diagram. For example, if we are designing a system tracking Computer Science BA Alumni then it is associated with exactly one department and so you do not need a data store or entity called "Department".

      ERD Hint -- You don't have to draw an ERD

       You can use a wall and sticky notes to work out a set of entities. You can write the Entity names and attributes on the sticky notes and then move them close to the other entities they will be linked to. You can draw the links by hand. The use an electronic camera to record the result. Or you can leave the ERD up on a notice board in the team's conference room.

      ERD Hint -- In UML omit the asterisks

       In the Unified notation a missing multiplicity means "unknown number". An asterisk means "any number". There is so little difference between these two statements that expert UML modelers only show multiplicities like "1" and "0..1". There is a risk that non-experts may misread these a missing multiplicity as "1"... but this is balanced by the ability to draw the diagram faster.

      ERD Hint -- Use Layout to encode structure

      I normalize my ERDs so that all relationships have one end with multiplicity "1" and I always place the boxes so that the "1" end is above the "many" end. It is a discipline from the SSADM method that I've found helpful for many years.

      ERD Hint -- Entities with too many attributes

      Entities that have many attributes can become quite cumbersome and space consuming in an ERD. When this happens you should document the details separately and only show a few important atttributes in the diagram. You should then (informally) add three dots (". . .") at the end of the attribute list to show you have hidden something.

      ERDs Hint -- High Speed ERDS

      How to do ERDs very rapidly:
      1. NO BOXES.
      2. Lowercase names.
      3. Connect with lines for relationships.
      4. Mark the 1 end of many-to-one relationships.
      5. Break many-to-many relationships. Replace by new entities.

      Example: while eating a Fajita in MacDonald's in Carpenteria I looked at the tally role receipt and drew on my Tungsten something like this:

      Very Rough ERD showing store, server, keyboard, order, and order item.

      Later I transcribed it to a napkin using the UML. And even later, I used Visio to get this ERD:

      "MacDonalds Conceptual Model using Visio"

    . . . . . . . . . ( end of section ERD Hints) <<Contents | End>>

    How to quantify UML ERDs

      You can attach numbers to an ERD. This is like attaching times and durations to an activity diagram in the CPM. More importantly you can calculate missing numbers, and check the logic of the model you canstructed.

      Introduction to Quantification

        Example 1.
        Net
        1. You have 20 cats.
        2. Each cat has 4 legs (on average).
        3. |-There are 80 legs.

        (End of Net)

        Example 2
        Net
        1. You need to keep track of 1,000 patients.
        2. Each patients record takes up 500bytes.
        3. How much storage do you need?

        (End of Net)

        Example 3
        Net
        1. The college has 200 teachers and 4,000 students.
        2. How many students per faculty?

        (End of Net)

        Example 4
        Net
        1. The college has 200 teachers and 4,000 student.
        2. A class is taught by one teacher.
        3. Students enroll in an average of 5 classes.
        4. On average, a teacher teaches a 3 classes
        5. What is the average class size?

        (End of Net)

        Four examples as ERDs

        I use three special tagged values to quantify the above data bases.
        Table
        tagaplied tomeaning
        Lattributelength. Number of bytes needed to store attribute
        Lclasslength. Number of bytes in one record in class/entity
        Nclassexpected number of entities/rows in table
        Vclassvolume in bytes, KB, MB
        averageroleaverage number of objects/rows per associated entity
        documentanywhere to find detailed documentation

        (Close Table)

      Procedure -- Quantifying an ERD
      1. Start by normalizing the ERD
      2. Write 1 at the 1 end and the average number at the many end as a UML constraint: {average=...}
      3. Write the number of occurrences of each entity by or in the entity box as a constraint: {N=...}
      4. Check the constraints.

      Constraints on Quantities

       Why check the constraints?

      Some of the constraints are based on the mathematical principle that if you put 20 pigeons in 10 holes than on average you've got 2 pigeons in each hole.

    1. (Pigeon_hole_principle): If there are n A's and m B's and each B has one A then the average number of A's per B is m/n.
      Table
      ContextConstraintNote
      classL = Σ[a:attribute](a.L). Length of entity is sum of its entity lengths.
      classV = L * N Volume is Length times Number of occurences
      associationAll are one-to-many or one-to-optional, no 1-1 and no many-to-many
      associationIf class with N=N1 has a one-to-average A role in class with N=N2 then N2=N1*A.
      associationIf class N=N1 has a one-to-(min..max) role in class with N=N2 then min <= N2/N1 <= max.

      (Close Table)

    Questions

    Online Resources

      An Example of ERDs in the Context of a Project

       The following has too many different ERDs: [ toc.html ] But you can see how ERDs can be used in a project.

      More on Patterns

       For more see [Gammaetal94] and PATTERN in my bibliography.

      There is a book of design patterns for enterprises:

      1. Jim Arlow & Ila Neustadt
      2. Enterprise Patterns and the MDA: Building better solutions with archetype patterns and UML
      3. Addison Wesley 2003
      It is the most incredible collection of ready-to-use business models I have ever seen. However many are too general and most are probably too complex. They are not conceptual models but object oriented designs that the authors have used many times.

      An analysis pattern [Coad92] is a commonly observed set of real world entities and relations. In most models you'll find several patterns.

      Data Base Management Systems

      Oracle [ index.html ] [ Oracle_%28DBMS%29 ] [ http://www.oracjobs.com/ ] , MSAccess [ FX100487571033.aspx ] [ Microsoft_Access ] , MySQL [ MySQL ] , Postgres [ PostGres ] , etc.

      SQL injection attacks to database-driven web services

       What is the average security risk level of SQL injection attacks to database-driven web services? Are there standard security techniques that help to safeguard against this kind of attack, or are the security solutions variable depending on the structure of the database design and/or web interface design? You've got the usual suspect: extra quotation marks that fake a stupid script into executing the data as a command. See the Wikipedia article [ SQL_injection ] which includes the usual ways to defend against the threat. I would also expect there are standard security techniques for them.

      What is an API

    1. API::= "Application Programmer Interface", a long list of functions that can be called in a program to manipulate the data. For a typical data base the functions take a string as an argument that contains a SQL command. They return a code indicating if they worked or not. They may have other arguments that provide data to the database, or are set to the results of the command. There are three basic kinds of function:
      1. Queries extract information from the data base
      2. Updates change the data in the data base
      3. Administration commands change the structure of the Data Base

      This search [ manual-lookup.php?pattern=SQL ] lists the names of the functions in the PHP API.

      Other Application Programmer Interfaces

      1. JDBC::="Java Data Base Connectivity".
      2. SQL::="Structured Query Language", [ SQL ]

        Examples of working with SQL data bases: [ 372doc6.pdf ] (Aaron Smith) and [ 372doc7.pdf ] (Nieleh Wilcots). If you need to see an example of an SQL base API check out the PHP language that includes special functions [ ref.mysql.php ] that use SQL to drive a MySQL database.

        Mapping ERDs to XML

        Given all the attributes this is not difficult and there are tools that can help you: [ xml_wrangling.html ]

      . . . . . . . . . ( end of section Online Resources) <<Contents | End>>

      Review Questions

      1. What is an ERD? Define the term and explain what and ERD looks like and what it means.
      2. Redraw each of the UML diagrams on this page as diagrams using the Chen notation.
      3. Find one example of each of the patterns in a domain/system that you know about.
      4. Draw a rough (no boxes) ERD of part of CSUSB.
      5. Take my ERDPatterns hand out and insert the asterisks I have left off.
      6. Draw a rough ERD of a DFD. Use these entity names: Process, Store, External Entity, Data Flow. List any constraints that can not be expressed in an ERD.
      7. What fragment of an ERD is suggested by "CSCI372 section 01 is taught in JBH146 at 4-6pm TuTh by RBOTTING"? Note: several solutions are possible.
      8. Draw an ERD describing use cases in a project. A project has many use cases. Each communicates with many actors and many actors communicate with a given use case. A Use case has a name. An actor has a name. Each user has a prime actor that achieves some goal by using that use case.
      9. We have 10,000 students and each student is on average enrolled in 5 sections. Each faculty, on average teaches 2.5 sections. How many faculty must we have?
      10. Find any tally-roll or receipt that you have and list the identifiers on it. If each identifier in your tally-roll or receipt is the key to an Entity type derive a rough ERD for the system that produced the receipt.
      11. What are the two properties of a entity type that are used to determine the total volume of data needed? What is the formula connecting these tagged values to the volume.
      12. Draw a rough ERD of a Dungeon-type game: Rooms have walls. Most walls have two rooms: one on each side. Walls have doors. Doors can be open or closed. Rooms have artifacts. Characters are always in a room and a room can have any number of characters in it. Characters can carry artifacts. Types of artifact: weapon, clothes, jewel, wand, .... Rooms have monsters. (Multiple answers are possible).
      13. Draw an ERD of: A formula is the sum of many terms. A term is a product of factors. A factor can be a constant, a variable, or another formula.

    . . . . . . . . . ( end of section Entity Relationship Models) <<Contents | End>>

    Abbreviations

  1. TBA::="To Be Announced".
  2. TBD::="To Be Done".

    Also see [ glossary.html ] for more special abbreviations and phrases.

End