The Relational Model - theoretical foundation Database Group, Georgia Tech © Leo Mark Relational Model 1 The Relational Model • data structures • constraints • operations – algebra (ISBL) – tuple calculus (QUEL, SQL) – domain calculus (QBE) • views Database Group, Georgia Tech © Leo Mark Relational Model 2 Data Structures • let D1, D2 , D3 , ..., Dn be sets (not necessarily distinct) of atomic values • relation, R, defined over D1, D2 , D3 , ..., Dn is a subset of the set of ordered ntuples {<d1, d2, d3, ..., dn | di Di, i=1, ...,n}; D1, D2 , D3 , ..., Dn are called domains • the number, n, is the degree of the relation (unary, binary, ternary, n-ary). • the number of tuples, |R|, in R is called the cardinality of R • if D1, D2 , D3 , ..., Dn are finite then there are 2|D1||D2| ... |Dn| possible relation states Database Group, Georgia Tech © Leo Mark Relational Model 3 Data Structures • an attribute name refers to a position in a tuple by name rather than position • an attribute name indicate the role of a domain in a relation • attribute names must be unique within relations • by using attribute names we can forget the ordering of field values in tuples • a relation definition includes the following R( A1:D1, A2 :D2 , ..., An :Dn) Database Group, Georgia Tech © Leo Mark Relational Model 4 Constraints • • • • keys primary keys entity integrity referential integrity FLT-SCHEDULE CUSTOMER FLT# CUST# CUST-NAME p p RESERVATION FLT# DATE CUST# Database Group, Georgia Tech © Leo Mark Relational Model 5 AIRPORT airportcode name city state FLT-SCHEDULE flt# airline dtime from-airportcode atime to-airportcode miles price FLT-WEEKDAY flt# weekday FLT-INSTANCE flt# date plane# #avail-seats AIRPLANE plane# plane-type total-#seats CUSTOMER cust# first middle last phone# street city state zip RESERVATION flt# date cust# seat# check-in-status ticket# Database Group, Georgia Tech © Leo Mark Relational Model 6 Operations • classes of relational DMLs: – relational algebra (ISBL) – tuple calculus (QUEL, SQL) – domain calculus (QBE) • a relational DML with the same “retrieval power” as the relational algebra is said to be relationally complete • all relational DMLs have syntax for: – change (insert, delete, update) – queries (retrieval) Database Group, Georgia Tech © Leo Mark Relational Model 7 Operations - insert, delete, update FLT-SCHEDULE flt# airline dtime from-airportcode atime to-airportcode miles price • constructs for insertion are very primitive: INSERT INTO FLT-SCHEDULE VALUES (“DL212”, “DELTA”, 11-15-00, “ATL”, 13-05-00, ”CHI”, 650, 00351.00); INSERT INTO FLT-SCHEDULE VALUES (FLT#:“DL212”, AIRLINE:“DELTA”); Database Group, Georgia Tech © Leo Mark Relational Model 8 Operations - insert, delete, update FLT-SCHEDULE flt# airline dtime from-airportcode atime to-airportcode miles price FLT-WEEKDAY flt# weekday FLT-INSTANCE flt# date plane# #avail-seats • “insert into FLT-INSTANCE all flights scheduled for Thursday, 9/10/98” INSERT INTO FLT-INSTANCE(flt#, date) (SELECT S.flt#, 1998-09-10 FROM FLT-SCHEDULE S, FLT-WEEKDAY D WHERE S.flt#=D.flt# AND weekday=“TH”); • interesting only because it involves a query Database Group, Georgia Tech © Leo Mark Relational Model 9 Operations - insert, delete, update FLT-WEEKDAY flt# weekday • constructs for deletion are very primitive: • “delete flights scheduled for Thursdays” DELETE FROM FLT-WEEKDAY WHERE weekday=“TH”; • interesting only because it involves a query Database Group, Georgia Tech © Leo Mark Relational Model 10 Operations - insert, delete, update FLT-WEEKDAY flt# weekday • constructs for update are very primitive: • “update flights scheduled for Thursdays to Fridays” UPDATE FLT-WEEKDAY SET weekday=“FR” WHERE weekday=“TH”; • interesting only because it involves a query Database Group, Georgia Tech © Leo Mark Relational Model 11 Relational Algebra • the Relational Algebra is procedural; you tell it how to construct the result • it consists of a set of operators which, when applied to relations, yield relations (closed algebra) R S union R S intersection R\S set difference R S Cartesian product A1, A2, ..., An (R) projection expression (R) selection R S natural join R S theta-join RS divideby [A1 B1,.., An Bn] rename Database Group, Georgia Tech © Leo Mark Relational Model 12 Selection FLT-WEEKDAY flt# weekday • “find (flt#, weekday) for all flights scheduled for Mondays” weekday=MO (FLT-WEEKDAY) • the expression in expression (R) involves: • operands: constants or attribute names of R • comparison operators: Š •° = • logical operators: • nesting: ( ) Database Group, Georgia Tech © Leo Mark Relational Model 13 Projection FLT-WEEKDAY flt# weekday • “find flt# for all flights scheduled for Mondays flt#(weekday=MO (FLT-WEEKDAY)) • the attributes in the attribute list ofA1, A2, ..., An (R) must be attributes of the operand R Database Group, Georgia Tech © Leo Mark Relational Model 14 Union FLT-WEEKDAY flt# weekday • “find the flt# for flights that are schedule for either Mondays, or Tuesdays, or both” flt#(weekday=MO (FLT-WEEKDAY)) flt#(weekday=TU (FLT-WEEKDAY)) • the two operands must be "type compatible" Database Group, Georgia Tech © Leo Mark Relational Model 15 Intersection FLT-WEEKDAY flt# weekday • “find the flt# for flights that are schedule for both Mondays and Tuesdays” flt#(weekday=MO (FLT-WEEKDAY)) flt#(weekday=TU (FLT-WEEKDAY)) • the two operands must be "type compatible" Database Group, Georgia Tech © Leo Mark Relational Model 16 Set Difference FLT-WEEKDAY flt# weekday • “find the flt# for flights that are scheduled for Mondays, but not for Tuesdays” flt#(weekday=MO (FLT-WEEKDAY)) \ flt#(weekday=TU (FLT-WEEKDAY)) • the two operands must be "type compatible" • Note: R S = R \ (R \ S) Database Group, Georgia Tech © Leo Mark Relational Model 17 Cartesian Product FLT-INSTANCE flt# date plane# #avail-seats CUSTOMER cust# first middle last phone# street city state zip RESERVATION flt# date cust# seat# check-in-status ticket# “make a list containing (flt#, date, cust#) for DL212 on 9/10, 98 for all customers in Roswell that are not booked on that flight” (cust#(city=ROSWELL(CUSTOMER)) flt#,date (flt#=DL212 date=1998-09-10 (FLT-INSTANCE))) \ flt#,date ,cust#(RESERVATION) Database Group, Georgia Tech © Leo Mark Relational Model 18 Natural Join FLT-WEEKDAY flt# weekday FLT-INSTANCE flt# date plane# #avail-seats • “make a list with complete flight instance information” FLT-INSTANCE FLT-WEEKDAY • natural join joins relations on attributes with the same names • all joins can be expressed by a combination of primitive operators: FLT-INSTANCE.flt#, date, weekday, #avail-seats (FLT-INSTANCE.flt#=FLT-WEEKDAY.flt# (FLT-INSTANCE FLT-WEEKDAY)) Database Group, Georgia Tech © Leo Mark Relational Model 19 -join FLT-SCHEDULE flt# airline dtime from-airportcode atime to-airportcode miles price FLT-INSTANCE flt# date plane# #avail-seats • “make a list of pairs of (FLT#1, FLT#2) that form possible connections” fl1, flt#(([flt# fl1, from-airportcode da1,dtime dt1, to-airportcode aa1, atime at1, date d1] (FLT-SCHEDULE FLT-INSTANCE )) d1=date aa1=from-airportcode at1< dtime (FLT-SCHEDULE FLT-INSTANCE)) • the-operators: Š •° = Database Group, Georgia Tech © Leo Mark Relational Model 20 Divideby FLT-INSTANCE flt# date plane# #avail-seats RESERVATION flt# date cust# seat# check-in-status ticket# • “list the cust# of customers that have reservations on all flight instances” flt#, date, cust# RESERVATION flt#, date (FLT-INSTANCE) Database Group, Georgia Tech © Leo Mark Relational Model 21 ISBL - an example algebra R S R S R\S A1, A2, ..., An (R) expression (R) R S R S R S RS [A1 B1,..., An Bn] (R) R UNION S R INTERSECT S R MINUS S R[A1, A2, ..., An] R WHERE EXPRESSION R JOIN S (no shared attributes) R JOIN S (shared attributes) via selection from R DIVIDEBY S R[A1 B1,.., An Bn] Database Group, Georgia Tech © Leo Mark Relational Model 22 Features of ISBL • the Peterlee Relational Test Vehicle, PRTV, has a query optimizer for ISBL • Naming results: T = R JOIN S • Lazy evaluation: T = N!R JOIN N!S • LIST T • 2-for-1 JOIN: – Cartesian product if no shared attribute names – natural join if shared attribute names • ISBL is relationally complete ! Database Group, Georgia Tech © Leo Mark Relational Model 23 ISBL - an example query FLT-SCHEDULE flt# airline dtime from-airportcode atime to-airportcode miles price FLT-INSTANCE flt# date plane# #avail-seats • “make a list of pairs of (FLT#1, FLT#2) that form possible connections” LIST(((FLT-SCHEDULE JOIN FLT-INSTANCE ) [FLT# FL1, FROM-AIRPORTCODE DA1,DTIME DT1, TOAIRPORTCODE AA1, ATIME AT1, DATE D1]) JOIN (FLT-SCHEDULE JOIN FLT-INSTANCE) WHERE D1=DATE AA1=FROM-AIRPORTCODE AT1< DTIME)[FL1, FLT#] Database Group, Georgia Tech © Leo Mark Relational Model 24 Relational Calculus • the Relational Calculus is nonprocedural. It allows you to express a result relation using a predicate on tuple variables (tuple calculus): { t | P(t) } or on domain variables (domain calculus): { <x1, x2, ..., xn> | P(<x1, x2, ..., xn>) } • you tell the system which result you want, but not how to construct it Database Group, Georgia Tech © Leo Mark Relational Model 25 Tuple Calculus • query expression: { t | P(t) } where P is a predicate built from atoms • range expression: t R denotes that t is a member of R; so does R(t) • attribute value: t.A denotes the value of t on attribute A • constant: c denotes a constant • atoms: t R, r.A s.B, or r.A c • comparison operators: Š • <>°= • predicate: an atom is a predicate; if P1 and P2 are predicates, so are ¬(P1 ) and (P1 ), P1 P2, P1 P2, and P1 P2 • if P(t) is a predicate, t is a free variable in P, and R is a relation then t R (P(t)) andt R (P(t)) are predicates Database Group, Georgia Tech © Leo Mark Relational Model 26 Tuple Calculus CUSTOMER cust# first middle last phone# street city state zip • { r |(rCUSTOMER} is infinite, or unsafe • a tuple calculus expression { r | P(r) } is safe if all values that appear in the result are from Dom(P), which is the set of values that appear in P itself or in relations mentioned in P Database Group, Georgia Tech © Leo Mark Relational Model 27 Selection FLT-WEEKDAY flt# weekday • “find (FLT#, WEEKDAY) for all flights scheduled for Mondays { t | FLT-WEEKDAY(t) t.WEEKDAY=MO} Database Group, Georgia Tech © Leo Mark Relational Model 28 Projection FLT-WEEKDAY flt# weekday • “find FLT# for all flights scheduled for Mondays { t.FLT# | FLT-WEEKDAY(t) t.WEEKDAY = MO} Database Group, Georgia Tech © Leo Mark Relational Model 29 Union FLT-WEEKDAY flt# weekday • “find the FLT# for flights that are schedule for either Mondays, or Tuesdays, or both” { t.FLT# | FLT-WEEKDAY(t) (t.WEEKDAY=MO t.WEEKDAY=TU)} Database Group, Georgia Tech © Leo Mark Relational Model 30 Intersection FLT-WEEKDAY flt# weekday • “find the FLT# for flights that are schedule for both Mondays and Tuesdays” { t.FLT# | FLT-WEEKDAY(t) t.WEEKDAY=MO sFLT-WEEKDAY(s) t.FLT#=s.FLT# s.WEEKDAY=TU)} Database Group, Georgia Tech © Leo Mark Relational Model 31 Set Difference FLT-WEEKDAY flt# weekday • “find the FLT# for flights that are scheduled for Mondays, but not for Tuesdays” { t.FLT# | FLT-WEEKDAY(t) t.WEEKDAY=MO ((s) (FLTWEEKDAY(s) t.FLT#=s.FLT# s.WEEKDAY=TU))} Database Group, Georgia Tech © Leo Mark Relational Model 32 Cartesian Product FLT-INSTANCE flt# date plane# #avail-seats CUSTOMER cust# first middle last phone# street city state zip RESERVATION flt# date cust# seat# check-in-status ticket# “make a list containing (FLT#, DATE, CUST#) for DL212 on 9/10, 98 for all customers in Roswell that are not booked on that flight” {s.FLT#, s.DATE, t.CUST# | FLT-INSTANCE(s) CUSTOMER(t) t.CITY=ROSWELL s.FLT#=DL212 s.DATE=1998-0910rFLT-INSTANCE(r) r ° s r.FLT#=s.FLT# r.DATE=s.DATE r.CUST#=t.CUST#)} Database Group, Georgia Tech © Leo Mark Relational Model 33 Natural Join FLT-WEEKDAY flt# weekday FLT-INSTANCE flt# date plane# #avail-seats • “make a list with complete flight instance information” { s.FLT#, s.WEEKDAY, t.DATE, t.PLANE#, t.#AVAILSEATS | FLT-WEEKDAY(s) FLT-INSTANCE(t) s.FLT#=t.FLT# } Database Group, Georgia Tech © Leo Mark Relational Model 34 -join FLT-SCHEDULE flt# airline dtime from-airportcode atime to-airportcode miles price FLT-INSTANCE flt# date plane# #avail-seats • “make a list of pairs of (FLT#1, FLT#2) that form possible connections” { s. FLT#, t.FLT# | FLT-SCHEDULE(s) FLTSCHEDULE(t) ((u)(v) FLT-INSTANCE(u) FLT-INSTANCE(v) u.FLT#=s.FLT# v.FLT#=t.FLT# u.DATE=v.DATE s.TO-AIRPORTCODE=t.FROMAIRPORTCODE s.ATIME < t.DTIME) } Database Group, Georgia Tech © Leo Mark Relational Model 35 Divideby FLT-INSTANCE flt# date plane# #avail-seats RESERVATION flt# date cust# seat# check-in-status ticket# • “list the CUST# for customers that have reservations on all flight instances” { s.CUST# | RESERVATION(s) (( t) FLTINSTANCE(t) ((r) RESERVATION(r) r.FLT#=t.FLT# r.DATE=t.DATE r.CUST#=s.CUST#))} Database Group, Georgia Tech © Leo Mark Relational Model 36 QUEL - an example tuple calculus FLT-SCHEDULE flt# airline dtime from-airportcode atime to-airportcode miles price FLT-INSTANCE flt# date plane# #avail-seats • “make a list of pairs of (FLT#1, FLT#2) that form possible connections” range s is FLT-SCHEDULE range t is FLT-SCHEDULE range u is FLT-INSTANCE range v is FLT-INSTANCE retrieve into CON( s.FLT#, t.FLT#) where u.FLT#=s.FLT# and v.FLT#=t.FLT# and u.DATE=v.DATE and s.TO-AIRPORTCODE=t.FROMAIRPORTCODE and s.ATIME < t.DTIME; Database Group, Georgia Tech © Leo Mark Relational Model 37 QBE - Projection FLT-WEEKDAY FLT# WEEKDAY P. =MONDAY • “find FLT# for all flights scheduled for Mondays Database Group, Georgia Tech © Leo Mark Relational Model 38 QBE - Union FLT-WEEKDAY FLT# WEEKDAY P. MONDAY P. TUESDAY • “find the FLT# for flights that are schedule for either Mondays, or Tuesdays, or both” Database Group, Georgia Tech © Leo Mark Relational Model 39 QBE - Intersection FLT-WEEKDAY FLT# WEEKDAY P._SX MONDAY _SX TUESDAY • “find the FLT# for flights that are schedule for both Mondays and Tuesdays” Database Group, Georgia Tech © Leo Mark Relational Model 40 QBE - Set Difference FLT-WEEKDAY FLT# WEEKDAY P._SX MONDAY _SX TUESDAY • “find the FLT# for flights that are scheduled for Mondays, but not for Tuesdays” Database Group, Georgia Tech © Leo Mark Relational Model 41 QBE - Cartesian Product CUSTOMER FLT-INSTANCE #AVAIL- CUST# P._C CUST-NAME CITY FLT# DATE ROSWELL P._F P._D _F DL212 SEATS 98-9-10 _D RESERVATION FLT# _F DATE _D CUST# _C “make a list containing (FLT#, DATE, CUST#) for DL212 on 9/10, 98 for all customers in Roswell that are not booked on that flight” Database Group, Georgia Tech © Leo Mark Relational Model 42 QBE - Natural Join FLT-WEEKDAY FLT-INSTANCE #AVAIL- FLT# WEEKDAY P._SX P. FLT# DATE _SX P. SEATS P. • “make a list with complete flight instance information” Database Group, Georgia Tech © Leo Mark Relational Model 43 QBE-join FLT-SCHEDULE FLT# AIRLINE FROMAIRPORT DTIME CODE P._SX TOAIRPORT CODE _A ATIME PRICE _AT FLT-SCHEDULE FLT# AIRLINE P._SY FROMAIRPORT DTIME CODE _A TOAIRPORT CODE ATIME PRICE _DT FLT-INSTANCE CONDITION _AT < _DT FLT# DATE _SX _D _SY _D #SEATS • “make a list of pairs of (FLT#1, FLT#2) that form possible same day connections” Database Group, Georgia Tech © Leo Mark Relational Model 44 Views • relational query languages are closed, i.e., the result of a query is a relation • a view is a named result of a query • a view is a snapshot relation • views can be used in other queries and view definitions • queries on views are evaluated by query modification • some views are updatable • some views are not updatable • more on views when we look at SQL Database Group, Georgia Tech © Leo Mark Relational Model 45

Descargar
# Algebra Calculus Powerpoint