Relations, Functions, and MatricesDatabaseEntity-Relationship ModelExample: E-R DiagramSlide 5Relational ModelSlide 7Slide 8Example: Relational ModelSlide 10Slide 11Slide 12Slide 13Operations on RelationsSlide 15Example: Unary OperationsExample: Binary OperationExample: OperationsSlide 19Relational AlgebraStructured Query Language (SQL)Database IntegritySlide 23Relations, Functions, and MatricesMathematical Structures for Computer ScienceChapter 4Copyright © 2006 W.H. Freeman & Co. MSCS Slides Relations, Functions and MatricesSection 4.3 Relations and Databases 2DatabaseA database is a storehouse of associated information about some enterprise. The user of a database can certainly retrieve some specific fact stored in the database. A well designed database is more than simply a list of facts. The user can perform queries on the database to retrieve information not contained in any single fact. The whole becomes more than the sum of its parts. To design a useful and efficient computerized database, it is necessary to model or represent the enterprise with which the database is concerned. A conceptual model attempts to capture the important features and workings of the enterprise. Considerable interaction with those who are familiar with the enterprise may be required to obtain all the information necessary to formulate the model.Section 4.3 Relations and Databases 3Entity-Relationship ModelOne high-level representation of an enterprise is the entity-relationship model. In this model, important objects, or entities, in the enterprise are identified, together with their relevant attributes or properties. The information of the relationships between these various entities is represented graphically by an entity-relationship diagram, or E-R diagram. In an E-R diagram, rectangles denote entity sets, ellipses denote attributes, and diamonds denote relationships.Section 4.3 Relations and Databases 4Example: E-R DiagramThe Pet Lovers of America Club (PLAC) wants to set up a database. PLAC has bought mailing lists from commercial sources, and it is interested in those people who own pets and in some basic information about those pets, such as the name, type of pet (dog, cat, etc.), and breed.The figure below shows an E-R diagram for the PLAC enterprise.Section 4.3 Relations and Databases 5Example: E-R DiagramThis diagram says that persons and pets are the entities. Persons have the attributes of Name, Address, City, and State. Pets have the attributes of Pet-name, Pet-type, and Breed. The diagram also shows that persons own pets. Thinking of the entities as sets, the Person set and the Pet set, the relationship “owns” is a binary relation from Person to Pet The ownership relation is captured by (person, pet) ordered pairs. The “1”and “N” on the connecting lines indicate that this binary relation is one-to-many.In this particular enterprise, one person can own many pets, but no pet has multiple owners. (Pets with multiple owners would result in a many-to-many relation.) Also, in this example, some persons may own no pets, and some pets may have no owners. The fact that no pet has multiple owners is one of the “business rules” of the enterprise. Such business rules are important to identify when designing a database.Section 4.3 Relations and Databases 6Relational ModelAnother representation of an enterprise called relational model can be developed from the E-R model. Both the entity sets and the relationships of the E-R model become relations (in the mathematical sense) in the relational model. The relations are described by tables, and a relational database consists of collections of such tables.An entity set table is named for the entity set. Each row in the table contains the values of the n attributes for a specific instance of that entity set. Thus, the relational table may be thought of as a set of n-tuples (rows), and an individual row is called a tuple. True to the idea of a set, no duplicate tuples exist, and no ordering of the tuples is assumed. The ordering of the attributes is unimportant, except that consistency must be maintained; that is, each column in the table contains values for a specific attribute in all of the tuples.Section 4.3 Relations and Databases 7Relational ModelThe number of attributes (columns) is called the degree of the relation. The number of tuples (rows) is called the cardinality of the relation; it is the cardinality (in the set-theoretic sense) of the set of rows. More formally, a database relation is a subset of D1  D2  ...  Dn, where Di is the domain from which attribute Ai takes its values. This means that the database use of the word relation is consistent with our definition of an n-ary relation on multiple sets.Section 4.3 Relations and Databases 8Relational ModelBecause there are no duplicate tuples in a relation, giving the value of all n attributes of a tuple clearly distinguishes the tuple from all others. However, there may be a minimal subset of the attributes that can be used to uniquely identify each tuple. This subset is called the primary key of the relation; if the subset consists of more than one attribute, then it is a composite primary key. In the table describing the relation, the primary key is underlined in the row of attribute names.Section 4.3 Relations and Databases 9Example: Relational ModelThe Person relation in the PLAC database might contain the following data:The four attributes for each tuple are Name, Address, City, and State. The Pet relation could be:Section 4.3 Relations and Databases 10Example: Relational ModelAnother business rule of the PLAC enterprise is that all people have unique names; therefore, Name is sufficient to identify each tuple and was chosen as the primary key in the Person relation. In the Person relation as shown in this example, State could not serve as a primary key because there are two tuples with State value “IL.” However, just because Name has unique values in this instance does not preclude the possibility of duplicate names. It is the business rule that determines that names will be unique. There is no business rule that says that addresses or cities are unique, so neither of these attributes can serve as the primary key, even though there happen to be no duplicates in the Person relation shown. The primary key in a