Relational Model - Inspiring Innovation

Relational Model - Inspiring Innovation

Relational Model Table = relation. Column headers = attributes. name Row = tuple WinterBrew BudLite manf Petes A.B. Beers Relation schema = name(attributes) + other structure info., e.g., keys, other constraints. Example: Beers(name, manf) Order of attributes is arbitrary, but in practice we need to assume the order given in the relation schema.

Relation instance is current set of rows for a relation schema. Database schema = collection of relation schemas. Relational Data Set theoretic Model Domain set of values Relation as table Rows = tuples Columns = components Names of columns = attributes Set of attribute names = schema REL (A1,A2,...,An) C a r d i n a

l i t y A1 A2 A3 ... An a1 a2 a3 an b1 b2 a3 cn a1 c3 b3 . . . bn x1 v2 d3

wn Arity Attributes Tuple Component like a data type Cartesian product (or product) D1 D2 ... Dn n-tuples (V1,V2,...,Vn) s.t., V1 D1, V2 D2,...,Vn Dn Relation-subset of cartesian product of one or more domains FINITE only; empty set allowed Tuples = members of a relation inst.

Arity = number of domains Components = values in a tuple Domains corresp. with attributes Cardinality = number of tuples Name address 5 3 Relation: tel # Example 7 Domain of Relation Cardinality of domain Attribute

Domains N A T N1 A1 T1 N1 A1 T3 A T N1 A1 T1 N2

A2 T2 N1 A1 T7 N3 A3 T3 N1 A2 T1 N4 T4 N1 A3 T1 N5

T5 N2 A1 T1 T7 Domain 3 Cardinality <=5x3x7 of relation N1 A1 T2 N T6 Arity . Component . . Tuple Name Bob Relation Address Instance Telephone 123 Main St 555-1234 Bob

128 Main St 555-1235 Pat 123 Main St 555-1235 Harry 456 Main St 555-2221 Sally 456 Main St 555-2221

Sally 456 Main St 555-2223 Pat 12 State St 555-1235 About Relational Order of tuples not important Model Order of attributes not important (in theory) Collection of relation schemas (intension) Relational database schema Corresponding relation instances (extension) Relational database intension vs. extension

schema vs. data metadata includes schema Why Relations? Very simple model. Often a good match for the way we think about our data. Abstract model that underlies SQL, the most important language in DBMSs today. But SQL uses bags while the abstract relational model is set-oriented. Relational Design Simplest approach (not always best): convert each E.S. to a relation and each relationship to a relation. Entity Set Relation E.S. attributes become relational attributes. name

manf Beers Becomes: Beers(name, manf) Keys in Relations An attribute or set of attributes K is a key for a relation R if we expect that in no instance of R will two different tuples agree on all the attributes of K. Indicate a key by underlining the key attributes. Example: If name is a key for Beers: Beers(name, manf) E/R Relationships Relations Relation has attribute for key attributes of each E.S. that participates in the relationship.

Add any attributes that belong to the relationship itself. Renaming attributes OK. Essential if multiple roles for an E.S. name addr Drinkers 1 Likes manf Beers 2

Buddies husband name Favorite wife Married Likes(drinker, beer) Favorite(drinker, beer) Married(husband, wife) Buddies(name1, name2) For one-one relation Married, we can choose either husband or wife as key. Combining Relations Sometimes it makes sense to combine relations. Common case: Relation for an E.S. E plus the relation for some

many-one relationship from E to another E.S. Example Combine Drinker(name, addr) with Favorite(drinker, beer) to get Drinker1(name, addr, favBeer). Danger in pushing this idea too far: redundancy. e.g., combining Drinker with Likes causes the drinker's address to be repeated, viz.: name Sally Sally addr 123 Maple 123 Maple beer Bud Miller Notice the difference: Favorite is many-one; Likes is many-many.

Weak Entity Sets, Relationships Relations Relation for a weak E.S. must include its full key (i.e., attributes of related entity sets) as well as its own attributes. A supporting (double-diamond) relationship yields a relation that is actually redundant and should be deleted from the database schema. Example name Logins name @ Hosts

Hosts(hostName) Logins(loginName, hostName) At(loginName, hostName, hostName2) In At, hostName and hostName2 must be the same host, so delete one of them. Then, Logins and At become the same relation; delete one of them. In this case, Hosts schema is a subset of Logins schema. Delete Hosts? Subclasses Relations Three approaches: 1. Object-oriented: each entity is in one class. Create a relation for each class, with all the attributes for that class. Dont forget inherited attributes. 2. E/R style: an entity is in a network of classes related by isa. Create one relation for each E.S. An entity is represented in the relation for each subclass to which it belongs. Relation has only the attributes attached to that E.S. + key. 3. Use nulls. Create one relation for the root class or root E.S.,

with all attributes found anywhere in its network of subclasses. Put NULL in attributes not relevant to a given entity. Example name Beers isa color Ales manf OO-Style name manf name

manf color Bud A.B. SummerBrew Pete's dark Beers Ales E/R Style name

manf name Color Bud SummerBrew A.B. Pete's SummerBrew dark Beers Ales Using NULLS name

manf color Bud SummerBrew A.B. Pete's NULL dark Beers Functional Dependencies X A = assertion about a relation R that whenever two tuples agree on all the attributes of X, then they must also agree on attribute A.

Example Drinkers(name, addr, beersLiked, manf, favoriteBeer) name addr beersLiked manf favoriteBeer Janeway Voyager Bud A.B. WickedAle Janeway Voyager WickedAle Pete's WickedAle Spock Enterprise Bud A.B. Bud

Reasonable FD's to assert: 1. name addr 2. name favoriteBeer 3. beersLiked manf Shorthand: combine FD's with common left side by concatenating their right sides. Sometimes, several attributes jointly determine another attribute, although neither does by itself. Example: beer bar price Keys of Relations K is a key for relation R if: 1. K all attributes of R. (Uniqueness) 2. For no proper subset of K is (1) true. (Minimality) If K at least satisfies (1), then K is a superkey. Conventions Pick one key; underline key attributes in the relation schema. X, etc., represent sets of attributes; A etc., represent

single attributes. No set formers in FDs, e.g., ABC instead of {A, B, C}. Example Drinkers(name, addr, beersLiked, manf, favoriteBeer) {name, beersLiked} FDs all attributes, as seen. Shows {name, beersLiked} is a superkey. name beersLiked is false, so name not a superkey. beersLiked name also false, so beersLiked not a superkey. Thus, {name, beersLiked} is a key. No other keys in this example. Neither name nor beersLiked is on the right of any observed FD, so they must be part of any superkey. Important point: key in a relation refers to tuples, not the entities they represent. If an entity is represented by several tuples, then entity-key will not be the same as relation-key. Example 2 Lastname

Firstname Key Student ID Major Key (2 attributes) Superkey Note: There are alternate keys Keys are {Lastname, {StudentID} Firstname} and

Who Determines Keys/FDs? We could assert a key K. Then the only FDs asserted are that K A for every attribute A. No surprise: K is then the only key for those FDs, according to the formal definition of key. Or, we could assert some FDs and deduce one or more keys by the formal definition. E/R diagram implies FDs by key declarations and many-one relationship declarations. Rule of thumb: FDs either come from keyness, many-1 relationship, or from physics. E.g., no two courses can meet in the same room at the same time yields room time course.

Functional Dependencies (FDs) and Many-One Relationships Consider R(A1,, An) and X is a key then X Y for any attributes Y in A1,, An even if they overlap with X. Why? Suppose R is used to represent a many one relationship: E1 entity set E2 entity set where X key for E1, Y key for E2, Then, X Y holds, And Y X does not hold unless the relationship is one-one. What about many-many relationships? Inferring FDs And this is important because When we talk about improving relational designs, we often need to ask does this FD hold in this relation? Given FDs X1 A1, X2 A2,, Xn An, does FD Y B necessarily hold in the same relation? Start by assuming two tuples agree in Y. Use given FDs to infer other attributes on which they must agree. If B is among them, then yes, else no.

Algorithm Define Y+ = closure of Y = set of attributes functionally determined by Y: Basis: Y+:=Y. Induction: If X Y+, and X A is a given FD, then add A to Y+. X Y+ A new Y + End when Y+ cannot be changed. Example A B, BC D. A+ = AB. C+=C. (AC)+ = ABCD. A C

B D Given Versus Implied FDs Typically, we state a few FDs that are known to hold for a relation R. Other FDs may follow logically from the given FDs; these are implied FDs. We are free to choose any basis for the FDs of R a set of FDs that imply all the FDs that hold for R. Finding All Implied FDs Motivation: Suppose we have a relation ABCD with some FDs F. If we decide to decompose ABCD into ABC and AD, what are the FDs for ABC, AD? Example: F = AB C, C D, D A. It looks like just AB C holds in ABC, but in fact C A follows from F and applies to

relation ABC. Problem is exponential in worst case. Algorithm For each set of attributes X compute X+. Drop XY A if X A holds. But skip X = , X = all attributes. Add X A for each A in X+X. Consequence: If X+ is all attributes, then there is no point in computing closure of supersets of X.

Finally, project the FDs by selecting only those FDs that involve only the attributes of the projection. Notice that after we project the discovered FDs onto some relation, the eliminated FDs can be inferred in the projected relation. Example F = AB C, C D, D A. What FDs follow? A+ = A; B+=B (nothing). C+=ACD (add C A). D+=AD (nothing new). (AB)+=ABCD (add AB D; skip all supersets of AB). (BC)+=ABCD (nothing new; skip all supersets of BC). (BD)+=ABCD (add BD C; skip all supersets of BD). (AC)+=ACD; (AD)+=AD; (CD)+=ACD (nothing new). (ACD)+=ACD (nothing new). All other sets contain AB, BC, or BD, so skip. Thus, the only interesting FDs that follow from F are: C A, AB D, BD C.

Example 2 Set of FDs in ABCGHI: AB AC CG H CG I BH Compute (CG)+, (BG)+, (AG)+ Example 3 In ABC with FDs A B, B C, project onto AC. A+ = ABC; yields A B, A C. B+ = BC; yields B C. AB+ = ABC; yields AB C; drop in favor of A C. AC+ = ABC yields AC B; drop in favor of A B. C+ = C and BC+ = BC; adds nothing. Resulting FDs: A B, A C, B C. Projection onto AC: A C.

Recently Viewed Presentations

  • Lisp - Inspiring Innovation

    Lisp - Inspiring Innovation

    If the cdr of the cons cell is not a function, it just returns it Summary Scheme's functional foundation shows its power here Closures and macros let us define delay and force Which allows us to handle large, even infinite...
  • Microsoft Azure: Infrastructure as a Service (IaaS) Module

    Microsoft Azure: Infrastructure as a Service (IaaS) Module

    Navigate to different portal areas, focusing on the dashboard. Next, go to the new Azure portal to show pre-existing resource groups or to create a resource group [EDITOR] TWB_Trevor: 04 October 2013. Content seems to be missing from the bullet...
  • ? A Minibeast Description Game NEXT Click the

    ? A Minibeast Description Game NEXT Click the

    A Minibeast Description Game NEXT Click the leaves for clues I am long with lots of legs. I will turn into another minibeast! I was born from an egg.
  • Everlasting God -

    Everlasting God -

    Everlasting God Strength will rise As we wait upon the Lord We will wait upon the Lord We will wait upon the Lord (Repeat) PRE-CHORUS: Our God, You reign forever Our hope, our strong deliverer CHORUS: You are the everlasting...
  • The Hidden World of Nuclear Reactors

    The Hidden World of Nuclear Reactors

    Thank you for your time! The Wonderful World Of Nuclear Reactors By Josh Daniels History: In the Beginning . . . In the beginning, there was no nuclear power. People were dependent on fossil fuels , like coal and petroleum....
  • Sms Implementation Plan

    Sms Implementation Plan

    Revised bus operator training program in coordination with University of South Florida Center for Urban Transportation Research to offer first-in-class curriculum that includes best practices from Transportation Safety Institute, National Transit Institute, FEMA, DHS, and Smith System
  • Understanding the Nature of Sleep and How it Changes With Age

    Understanding the Nature of Sleep and How it Changes With Age

    Circadian Rhythm Age-Related Changes May Disrupt Tonic Orexin Secretion. Circadian Rhythm Sleep DisordersEndogenous Misalignment: ASPD. Morbidity of Insomnia. Sleep Duration and Risk of Falls . Falls in Older Adults. Nocturia and Sleep Issues.
  • Calculus 8.1 - UH

    Calculus 8.1 - UH

    A sequence is a list of numbers written in an explicit order. nth term Any real-valued function with domain a subset of the positive integers is a sequence. If the domain is finite, then the sequence is a finite sequence....