程序代写代做代考 Relational Model and Algebra

Relational Model and Algebra

P.J. McBrien

Imperial College London

P.J. McBrien (Imperial College London) Relational Model and Algebra 1 / 45

The Relational Data Model Relations

Relations are sets of typed tuples

Relations

Relations take the form R(A,B, . . .) where

R is the name of the relation

A,B, … is the set of attributes of the relation

Often write the set without commas: A,B, . . . ≡ AB . . ., and can refer to a set of

attributes as ~A
The number of attributes n is the arity of the relation
Can call R(A1, . . . , An) an n-ary relation
Domain(A) is the set of values (type) that the attribute can have
Will use Atts(R) to find A,B, . . .

The extent of R(A,B, . . .) is the set of tuples
{〈vA1 , v

B
1 , . . . 〉, 〈v

A
2 , v

B
2 , . . . 〉, 〈v

A
3 , v

B
3 , . . . 〉, . . . }

∀x.vAx ∈ Domain(A)
No duplicate tuples
Not ordered
All tuples have the same arity

P.J. McBrien (Imperial College London) Relational Model and Algebra 2 / 45

The Relational Data Model Relations

Relation=Table

A B . . .
v
A
1 v

B
1 . . .

v
A
2 v

B
2 . . .

v
A
3 v

B
3 . . .
…

Set Semantics

Order of columns
not significant

Order of rows not
significant

No duplicate rows

Attribute=Column

Tuple=Row

P.J. McBrien (Imperial College London) Relational Model and Algebra 3 / 45

The Relational Data Model Relations

Quiz 1: Equivalent Relations

Which is the odd one out?

branch
sortcode bname cash

56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00

branch
bname sortcode cash
’Wimbledon’ 56 94340.45
’Goodge St’ 34 8900.67
’Strand’ 67 34005.00

branch
sortcode bname cash

34 ’Goodge St’ 8900.67
56 ’Wimbledon’ 94340.45
67 ’Strand’ 34005.00

branch
sortcode bname cash

56 ’Wimbledon’ 94340.45
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00

P.J. McBrien (Imperial College London) Relational Model and Algebra 4 / 45

The Relational Data Model Relations

Handling ‘missing’ attribute values

Suppose we want to have a relation account(no,type,cname,rate,sortcode), but not all
accounts have a rate.

Solution 1: Separate relations

account
no type cname sortcode

100 ’current’ ’McBrien, P.’ 67
101 ’deposit’ ’McBrien, P.’ 67
103 ’current’ ’Boyd, M.’ 34
107 ’current’ ’Poulovassilis, A.’ 56
119 ’deposit’ ’Poulovassilis, A.’ 56
125 ’current’ ’Bailey, J.’ 56

account rate
no rate

101 5.25
119 5.50

Solution 2: NULL values

account
no type cname rate sortcode

100 ’current’ ’McBrien, P.’ NULL 67
101 ’deposit’ ’McBrien, P.’ 5.25 67
103 ’current’ ’Boyd, M.’ NULL 34
107 ’current’ ’Poulovassilis, A.’ NULL 56
119 ’deposit’ ’Poulovassilis, A.’ 5.50 56
125 ’current’ ’Bailey, J.’ NULL 56

P.J. McBrien (Imperial College London) Relational Model and Algebra 5 / 45

The Relational Data Model Relations

Relational Keys

Key

A key of a relation R(AB . . .) is a subset of the attributes for which the values in
any extent are unique across all tuples

Every relation has at least one key, which is the entire set of attributes

A key is violated by there being two tuples in the extent which have the same
values for the attributes of the key

If A is a key, then so must AB be a key

A minimal key is a set of attributes AB . . . for which no subset of the
attributes is also a key

The primary key is one of the keys of the relation: serves as the default key
when no key explicitly stated

P.J. McBrien (Imperial College London) Relational Model and Algebra 6 / 45

The Relational Data Model Relations

Quiz 2: Violation of Relational Keys

movement
mid no amount tdate
1000 100 2300.00 5/1/1999
1001 101 4000.00 5/1/1999
1002 100 -223.45 5/1/1999
1004 107 -100.00 11/1/1999
1005 103 145.50 12/1/1999
1006 100 10.23 15/1/1999
1007 107 345.56 15/1/1999
1008 101 1230.00 15/1/1999
1009 119 5600.00 18/1/1999

Which key is violated?

movement(mid)

movement(no,amount)

movement(no,tdate)

movement(amount,tdate)

P.J. McBrien (Imperial College London) Relational Model and Algebra 7 / 45

The Relational Data Model Relations

Quiz 3: Correct Keys for Relations

Which key makes most sense in a bank UoD?

movement(amount)

movement(no,amount)

movement(no,tdate)

movement(amount,tdate)

P.J. McBrien (Imperial College London) Relational Model and Algebra 8 / 45

The Relational Data Model Relations

Relational Foreign Keys

Foreign Key

A foreign key R( ~X)
fk
⇒ S(~Y ) of a relation R(AB . . .) is a subset ~X ⊆ AB . . . of the

attributes for which the values in the extent of R also appear as values of attributes
~Y in the extent of S, and ~Y is a key of S.

account(sortcode)
fk
⇒ branch(sortcode)

account
no type cname rate sortcode
100 ’current’ ’McBrien, P.’ NULL 67
101 ’deposit’ ’McBrien, P.’ 5.25 67
103 ’current’ ’Boyd, M.’ NULL 34
107 ’current’ ’Poulovassilis, A.’ NULL 56
119 ’deposit’ ’Poulovassilis, A.’ 5.50 56
125 ’current’ ’Bailey, J.’ NULL 56

key branch(sortcode)

branch
sortcode bname cash

56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00

P.J. McBrien (Imperial College London) Relational Model and Algebra 9 / 45

The Relational Data Model Relations

Quiz 4: Foreign Key Violation

account(sortcode)
fk
⇒ branch(sortcode)

key branch(sortcode)

branch
sortcode bname cash

56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00

Which update violates the foreign key?

insert into account
(126,’business’,’McBrien, P.’,1.00,67)

insert into branch
(78,’Ealing’,1000.00)

delete from branch
(67,’Strand’,34005.00)

delete from account
(103,’current’,’Boyd, M.’,NULL,34)

P.J. McBrien (Imperial College London) Relational Model and Algebra 10 / 45

The Relational Data Model Relations

Example Relational Schema

branch
sortcode bname cash

56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00

movement
mid no amount tdate
1000 100 2300.00 5/1/1999
1001 101 4000.00 5/1/1999
1002 100 -223.45 8/1/1999
1004 107 -100.00 11/1/1999
1005 103 145.50 12/1/1999
1006 100 10.23 15/1/1999
1007 107 345.56 15/1/1999
1008 101 1230.00 15/1/1999
1009 119 5600.00 18/1/1999

account
no type cname rate sortcode

key branch(sortcode)
key branch(bname)
key movement(mid)
key account(no)

movement(no)
fk
⇒ account(no)

account(sortcode)
fk
⇒ branch(sortcode)

P.J. McBrien (Imperial College London) Relational Model and Algebra 11 / 45

Relational Algebra Five Primitive Operators

Relational Algebra: A Query Language for the Relational Model

Primitive operators of the Relational Algebra

Symbol Name Type
π Project Unary
σ Select Unary
× Cartesian Product Binary
∪ Union Binary
− Difference Binary

All operators take relations as input

All operators produce one relation as their output

Other (useful) operators may be defined in terms of the five primitive operators

P.J. McBrien (Imperial College London) Relational Model and Algebra 12 / 45

Relational Algebra Five Primitive Operators

Relational Algebra: Project π

account
no type cname rate sortcode

Project Operator

πno,typeaccount
no type
100 ’current’
101 ’deposit’
103 ’current’
107 ’current’
119 ’deposit’
125 ’current’

πsortcodeaccount
sortcode

67
34
56

P.J. McBrien (Imperial College London) Relational Model and Algebra 13 / 45

Relational Algebra Five Primitive Operators

Relational Algebra: Select σ

account
no type cname rate sortcode

Select Operator

σrate>0account
no type cname rate sortcode
101 ’deposit’ ’McBrien, P.’ 5.25 67
119 ’deposit’ ’Poulovassilis, A.’ 5.50 56

P.J. McBrien (Imperial College London) Relational Model and Algebra 14 / 45

Relational Algebra Five Primitive Operators

Relational Algebra: Product ×

branch
sortcode bname cash

56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00

σrate>0account
no type cname rate sortcode
101 ’deposit’ ’McBrien, P.’ 5.25 67
119 ’deposit’ ’Poulovassilis, A.’ 5.50 56

Product Operator

branch × σrate>0account
sortcode bname cash no type cname rate sortcode

56 ’Wimbledon’ 94340.45 101 ’deposit’ ’McBrien, P.’ 5.25 67
56 ’Wimbledon’ 94340.45 119 ’deposit’ ’Poulovassilis, A.’ 5.50 56
34 ’Goodge St’ 8900.67 101 ’deposit’ ’McBrien, P.’ 5.25 67
34 ’Goodge St’ 8900.67 119 ’deposit’ ’Poulovassilis, A.’ 5.50 56
67 ’Strand’ 34005.00 101 ’deposit’ ’McBrien, P.’ 5.25 67
67 ’Strand’ 34005.00 119 ’deposit’ ’Poulovassilis, A.’ 5.50 56

P.J. McBrien (Imperial College London) Relational Model and Algebra 15 / 45

Relational Algebra Five Primitive Operators

Quiz 5: RA Queries

branch
sortcode bname cash

56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00

account
no type cname rate sortcode

Which RA query lists the name of branches that have deposit accounts?

πsortcode σtype=‘deposit’ account

B
πbname
σaccount.sortcode=branch.sortcode∧type=‘deposit’
(account× branch)

πbname(branch× σtype=‘deposit’ account)

πbname σtype=‘deposit’(account× branch)

P.J. McBrien (Imperial College London) Relational Model and Algebra 16 / 45

Relational Algebra Five Primitive Operators

SPJ Queries

Select Project Join (SPJ) queries

If a product of tables is formed, where a selection is then done that compares the
attributes of those tables, we say that a join has been performed.
Normally not all columns of the product are returned, and therefore a project is also
required.

Branches with current accounts

πbname,no σbranch.sortcode=account.sortcode∧account.type=‘current’(branch× account)
bname no
‘Goodge St’ 103
‘Wimbledon’ 107
‘Wimbledon’ 125
‘Strand’ 100

P.J. McBrien (Imperial College London) Relational Model and Algebra 17 / 45

Relational Algebra Five Primitive Operators

Relational Algebra: Union ∪

πsortcode as idaccount
id
67
34
56

πno as idaccount
id

100
101
103
107
119
125

Union Operator

πsortcode as idaccount ∪ πno as idaccount
id
67
34
56

100
101
103
107
119
125

relations must be union compatible

P.J. McBrien (Imperial College London) Relational Model and Algebra 18 / 45

Relational Algebra Five Primitive Operators

Relational Algebra: Difference −

πnoaccount
no

100
101
103
107
119
125

πnomovement
no

100
101
103
107
119

Difference Operator

πnoaccount− πnomovement
no
125

relations must be union compatible

P.J. McBrien (Imperial College London) Relational Model and Algebra 19 / 45

Relational Algebra Five Primitive Operators

Rules for Combining Operators

Since all operators produce a relation as output, any operator may produce one of
the inputs to any other operator.

well formed RA query

the output of the nested operator must contain the attributes required by an
outer π or σ

the two inputs to a ∪ or − must contain the same number of attributes

P.J. McBrien (Imperial College London) Relational Model and Algebra 20 / 45

Relational Algebra Five Primitive Operators

Quiz 6: Well formed queries

account
no type cname rate sortcode

Which RA query is well formed?

σtype=‘current’ πno account

πno account− πno,mid movement

πno σtype=‘current’ account

πno πtype account

P.J. McBrien (Imperial College London) Relational Model and Algebra 21 / 45

Relational Algebra Five Primitive Operators

Worksheet: Primitive Relational Algebra Operators

branch
sortcode bname cash

56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00

account
no type cname rate sortcode

key branch(sortcode)
key branch(bname)
key movement(mid)
key account(no)

movement(no)
fk
⇒ account(no)

account(sortcode)
fk
⇒ branch(sortcode)

P.J. McBrien (Imperial College London) Relational Model and Algebra 22 / 45

Derived Operators

Derived Relational Algebra: Natural Join ⋊⋉

Natural Join

R ⋊⋉ S = σR.A1=S.A1∧…∧R.Am=S.AmR × S

Natural Join

branch ⋊⋉ account = σbranch.sortcode=account.sortcodebranch× account

branch ⋊⋉ account
sortcode bname cash no type cname rate

34 ’Goodge St’ 8900.67 103 ’current’ ’Boyd, M.’ NULL
56 ’Wimbledon’ 94340.45 107 ’current’ ’Poulovassilis, A.’ NULL
56 ’Wimbledon’ 94340.45 119 ’deposit’ ’Poulovassilis, A.’ 5.50
56 ’Wimbledon’ 94340.45 125 ’current’ ’Bailey, J.’ NULL
67 ’Strand’ 34005.00 100 ’current’ ’McBrien, P.’ NULL
67 ’Strand’ 34005.00 101 ’deposit’ ’McBrien, P.’ 5.25

P.J. McBrien (Imperial College London) Relational Model and Algebra 23 / 45

Derived Operators

Quiz 7: Natural Join

What is the result of πno(account ⋊⋉ movement)?

πno(account ⊲⊳ movement)
no

100
101
103
107
119
125

πno(account ⊲⊳ movement)
no

100
101
103
107
119

πno(account ⊲⊳ movement)
no

125

πno(account ⊲⊳ movement)
no

P.J. McBrien (Imperial College London) Relational Model and Algebra 24 / 45

Derived Operators

Derived Relational Algebra: Semi Join ⋉

Semi Join

R⋉ S = R ⋊⋉ πAttr(R)∩Attr(S)(S)

Semi Join

account⋉movement = account ⋊⋉ πno(movement)

account⋉movement
no type cname rate sortcode
100 ’current’ ’McBrien, P.’ NULL 67
101 ’deposit’ ’McBrien, P.’ 5.25 67
103 ’current’ ’Boyd, M.’ NULL 34
107 ’current’ ’Poulovassilis, A.’ NULL 56
119 ’deposit’ ’Poulovassilis, A.’ 5.50 56

P.J. McBrien (Imperial College London) Relational Model and Algebra 25 / 45

Derived Operators

Derived Relational Algebra: Joins

Natural Join

R ⋊⋉ S = σR.A1=S.A1∧…∧R.Am=S.AmR × S

Equi Join

R
A=B
⋊⋉ S = σR.A=S.BR × S

Semi Join

R⋉ S = R ⋊⋉ πAttr(R)∩Attr(S)(S)

Theta Join

R
θ

⋊⋉ S = σθR× S

P.J. McBrien (Imperial College London) Relational Model and Algebra 26 / 45

Derived Operators

Quiz 8: Understanding join operators

branch
sortcode bname cash

56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00

account
no type cname rate sortcode

Which RA query produces the most tuples?

branch
branch.sortcode‘deposit’ πno,type,cname account

πno σtype=‘current’ σtype<>‘deposit’ account

P.J. McBrien (Imperial College London) Relational Model and Algebra 37 / 45

Relational Algebra Equivalences

Quiz 13: Query Evaluation

Which RA means that the × operator handles fewer tuples?

A
σaccount.no=movement.no
(σsortcode=67 account× σamount<0 movement) B σaccount.no=movement.no∧sortcode=67 (account× σamount<0 movement) C σaccount.no=movement.no∧amount<0 (σsortcode=67 account×movement) D σaccount.no=movement.no∧sortcode=67∧amount<0 (account×movement) P.J. McBrien (Imperial College London) Relational Model and Algebra 38 / 45 Relational Algebra Equivalences Equivalences Involving Binary Operators Product and Union R× (S ∪ T) ≡ (R× S) ∪ (R× T) Product and Difference R× (S− T) ≡ (R× S)− (R× T) Union and Product R ∪ (S× T) unable to move ∪ inside × Union and Difference R ∪ (S− T) unable to move ∪ inside − Difference and Product R− (S× T) unable to move − inside × Difference and Union R− (S ∪ T) ≡ (R− S)− T P.J. McBrien (Imperial College London) Relational Model and Algebra 39 / 45 Relational Algebra Equivalences Quiz 14: Equivalent RA Expressions (Binary Operators) Which equivalence does not hold? A (R× S)× T ≡ R × (S × T ) B (R − S)− T ≡ R− (S − T ) C (R ∪ S) ∪ T ≡ R ∪ (S ∪ T ) D (R ∩ S) ∩ T ≡ R ∩ (S ∩ T ) P.J. McBrien (Imperial College London) Relational Model and Algebra 40 / 45 Relational Algebra Equivalences Worksheet: Equivalences Between RA Expressions 1 πno,type σsortcode=56 πno,type,sortcode σtype=‘deposit’ account 2 σaccount.no=movement.no(πno,cname account× πmid,no σamount>1000 movement)

σaccount.no=movement.no(πno,cname,rate account×
(σamount>1000 πmid,no movement ∪ σamount<100 πmid,no movement)) 4 πno,cname,tdate σamount<0∧account.no=movement.no account×movement P.J. McBrien (Imperial College London) Relational Model and Algebra 41 / 45 Relational Algebra Equivalences Quiz 15: Monotonic and non-monotonic operators A monotonic operator has the property that an additional tuple put into any input relation which only cause additional tuples to be generated in the output relation. A non-monotonic operator has the property that an additional tuple put into an input relation may remove tuples from the output relation Which RA operator is non-monotonic? A π R B R× S C R ∪ S D R− S P.J. McBrien (Imperial College London) Relational Model and Algebra 42 / 45 Relational Algebra Equivalences Incremental Query Evaluation Suppose we add rows ∆R to extent of relation R so it becomes R ′ If we represent ∆R as a relation (with the same attributes as R) then R ′ = R ∪∆R π ~X R ′ ≡ π ~X R ∪ π ~X ∆R σ P ( ~X) R ′ ≡ σ P ( ~X) R ∪ σP ( ~X) ∆R R ′ × S ≡ (R × S) ∪ (∆R × S) R ′ ∪ S ≡ (R ∪ S) ∪∆R R ′ − S ≡ (R − S) ∪ (∆R − S) S −R′ ≡ (S −R)−∆R P.J. McBrien (Imperial College London) Relational Model and Algebra 43 / 45 Relational Algebra Equivalences Example: Query result after update to account (1) 1 Suppose that we had already evaluated query Q πbname,no σbranch.sortcode=account.sortcode∧account.type=‘current’(branch × account) bname no ‘Goodge St’ 103 ‘Wimbledon’ 107 ‘Wimbledon’ 125 ‘Strand’ 100 2 If ∆account is added to account to get account ′: πbname,no σbranch.sortcode=account.sortcode∧account.type=‘current’(branch × account ′) πbname,no σbranch.sortcode=account.sortcode∧account.type=‘current’((branch × account) ∪ (branch × ∆account)) πbname,no σbranch.sortcode=account.sortcode∧account.type=‘current’(branch × account) ∪ πbname,no σbranch.sortcode=account.sortcode∧account.type=‘current’(branch ×∆account) 3 Thus if ∆account is added to account, we only need evaluate πbname,no σbranch.sortcode=account.sortcode∧account.type=‘current’(branch×∆account) P.J. McBrien (Imperial College London) Relational Model and Algebra 44 / 45 Relational Algebra Equivalences Example: Query result after update to account (2) 4 Suppose we have ∆account 126 ’business’ ’McBrien, P.’ 1.00 67 127 ’current’ ’Pietzuch, P.’ NULL 34 Then πbname,no σbranch.sortcode=account.sortcode∧account.type=‘current’(branch×∆account) bname no ’Goodge St’ 127 5 Thus since Q′ = Q ∪∆Q πbname,no σbranch.sortcode=account.sortcode∧account.type=‘current’(branch × account ′) bname no ‘Goodge St’ 103 ‘Wimbledon’ 107 ‘Wimbledon’ 125 ‘Strand’ 100 ’Goodge St’ 127 P.J. McBrien (Imperial College London) Relational Model and Algebra 45 / 45 Relational Model The Relational Data Model Relations Relational Algebra Five Primitive Operators Derived Operators Relational Algebra Equivalences

Related Posts