Example: customer-name = {Jones, Smith, Curry, Lindsay} customer-street = {Main, North, Park} customer-city y = {Harrison, Rye, Pittsfield

CHAPTER 2 CHAPTER 2

RELATIONAL MODEL

RELATIONAL MODEL

Chapter 2: Relational Model p

ƒ Structure of Relational Databases

ƒ Fundamental Relational Algebra Operations

ƒ Additional Relational Algebra Operations

ƒ Additional Relational Algebra Operations

ƒ Extended Relational-Algebra-Operations

ƒ Null Values

ƒ Modification of the Database

Basic Structure

ƒ Formally,

given sets D ₁ , D ₂ , …. D _n a relation r is a subset of D ₁ x D ₂ x … x D _n

R ⊆ D ₁ , X ….. X D (n: degree of R) R ⊆ D ₁ , X ….. X D _n (n: degree of R) or

R = { <d ₁ , ..., d _n > | d ₁ ∈ _{D 1 , ..., d n} ∈ _{D n} } (set of tuples)

ƒ Example: customer-name = {Jones, Smith, Curry, Lindsay}

customer-street = {Main, North, Park}

customer-city y = {Harrison, Rye, Pittsfield} { , y , }

Then r = { (Jones, Main, Harrison), (Smith, North, Rye),

Attribute Types yp

ƒ Each attribute of a relation has a name

ƒ The set of allowed values for each attribute is called the domain of the attribute

of the attribute

ƒ Attribute values are (normally) required to be atomic, that is, indivisible

indivisible

à E.g. multivalued attribute values are not atomic

à E g composite attribute values are not atomic E.g. composite attribute values are not atomic

ƒ The special value null is a member of every domain

Th ll l li i i h d fi i i f

ƒ The null value causes complications in the definition of many operations

d

à we shall ignore the effect of null values in our main presentation and

consider their effect later

Relation Schema

ƒ A _{1 1} , A _{2 2} , …, A _{n n} are attributes

ƒ R = (A ₁ , A ₂ , …, A _n ) is a relation schema

E g Customer schema = (customer name customer street customer city) E.g. Customer-schema = (customer-name, customer-street, customer-city)

ƒ r(R) is a relation (variable) on the relation schema R

E.g. customer(Customer-schema)

Relational Algebra g

ƒ Algebra : operators and operands

à Relational algebra

‚ operands : relations

b i (+ ddi i l i )

‚ operators : basic operators (+ additional operations)

 take two or more relations as inputs and give a new relation as a result.

ƒ Procedural language Procedural language

ƒ 6 Fundamental Operators

à select

à select

à project

à union

à set difference

à Cartesian product

à rename

Example Queries p Q

ƒ Find all loans of over $1200 σ amount >1200 (loan)

ƒ Find the loan number for each loan of an amount greater than

$1200

$1200

∏ loan-number (σ amount>1200 (loan))

Example Queries p Q

ƒ Find the names of all customers who have a loan, an account, or both, from the bank

∏ customer-name (borrower) ∪ ∏ customer-name (depositor)

ƒ Find the names of all customers who have a loan and an account at bank.

∏ customer-name customer name (borrower) ∩ ∏ customer-name customer name (depositor)

Example Queries p Q

ƒ Find the names of all customers who have a loan at the Perryridge branch.

∏ customer-name (σ branch-name=“Perryridge”

( σ _{b l b = l l b} (borrower x loan)))

( σ borrower.loan-number = loan.loan-number (borrower x loan)))

ƒ Find the names of all customers who have a loan at the Perryridge branch but do not

ƒ Find the names of all customers who have a loan at the Perryridge branch but do not have an account at any branch of the bank.

∏ _t ( σ _{b h “P id ”}

∏ customer-name ( σ branch-name = “Perryridge”

( σ borrower.loan-number = loan.loan-number ( borrower x loan ⁾⁾⁾

– ∏ customer-name ( depositor ⁾

Example Queries p Q

ƒ Find the names of all customers who have a loan at the Perryridge branch.

Query 1

∏ (

∏ customer-name (σ branch-name = “Perryridge”

(σ borrower.loan-number = loan.loan-number (borrower x loan)))

Query 2

∏ (

∏ customer-name (

(σ loan.loan-number = borrower.loan-number (

( σ branch name = “Perryridge” (loan) ) x borrower

( branch-name = Perryridge ( ) ) x w

)

))

Example Queries p Q

ƒ Find the largest account balance g

à Rename account relation as d

à The query is:

∏ _balance (account) –

∏ _balance ( )

∏ account.balance (

σ ( t x ρ _{( t) )}

σ account.balance < d.balance (account x ρ _d (account) )

)

Formal Definition

ƒ A basic expression in the relational algebra consists of either one of the following:

à A relation in the database

A l

à A constant relation

ƒ Let E ₁ and E ₂ be relational-algebra expressions; the following are ll l ti l l b p i

all relational-algebra expressions:

à E ₁ ∪ E ₂

à E ₁ – E ₂

à E ₁ x E ₂

à σ _p (E ₁ ), P is a predicate on attributes in E ₁

à ∏ _s (E ₁ ), S is a list consisting of some of the attributes in E ₁

à ρ _N (E ₁ ), N is the new name for the result of E ₁

Additional Operations p

We define additional operations that do not add any power to the p y p relational algebra, but that simplify common queries.

ƒ Set intersection

ƒ Natural join Natural join

ƒ Division A i

ƒ Assignment

Division Operation p

r ÷ s

ƒ Suited to queries that include the phrase “for all”

ƒ Suited to queries that include the phrase for all .

ƒ Let r and s be relations on schemas R and S respectively where

à R = (A ₁ , …, A _m , B ₁ , …, B _n )

à S = (B ₁ , …, B _n )

Th l f i l i h

The result of r ÷ s is a relation on schema R – S = (A ₁ , …, A _m )

r ÷ s = { t | t ∈ ∏ _R-S (r) ∧ ∀ u ∈ s ( tu ∈ r ) }

Division Operation – Example p p

„ Relations r s: ^„ r ÷ s:

B A A B

„ Relations r, s: ^„ r ÷ s:

B A

α 1

2 α α 1

2 2 β

α β γ

3 1

1 s

δ γ δ δ

1 1 3 δ 4

∈ ∈

4

6

1

Division Operation – Example p p

„ Relations r s: ^„ r ÷ s:

A B C D E D E A B C

„ Relations r, s: ^„ r ÷ s:

A B α ^a

C D α ^a

E 1 1

D a b

E 1 1

A B α ^a

C α γ

α β

a a a

γ γ γ

a b a

1 1 1

b 1 γ a γ

s β γ

γ

a a a

γ γ γ

b a b

3 1 γ 1

γ ^a γ

β ^b 1

r

Division Operation p

ƒ Property

à Let q = r ÷ s

à Then q is the largest relation satisfying q × s ⊆ r

ƒ Definition in terms of the basic algebra operation Let r(R) and s(S) be relations, and let S ⊆ R

r ÷ s = ∏ _R-S (r) –∏ _R-S ( (∏ _R-S (r) × s) – ∏ _R-S,S (r)) To see why

à ∏ _R-S,S (r) simply reorders attributes of r

Example Queries

ƒ Find all customers who have an account from at least the

p Q

“Downtown” and the “Uptown” branches.

à Query 1

∏ customer-name ( σ branch-name=“Downtown ^” (depositor account)) ∩

∏ ( σ (depositor account))

∏ customer-name ( σ branch-name=“Uptown ^” (depositor account))

à Query 2

∏ customer-name, branch-name (depositor account)

÷ ρ temp(branch-name ) ({(“Downtown”), (“Uptown”)})

Example Queries p Q

ƒ Find all customers who have an account at all branches located in Find all customers who have an account at all branches located in Brooklyn city.

∏ customer-name, branch-name customer name, branch name (depositor ( p account) )

÷ ∏ branch-name (σ branch-city = “Brooklyn” (branch))

Extended Relational-Algebra Operations g p

adds power and convenience to the relational algebra p g

ƒ Generalized Projection

ƒ Generalized Projection

ƒ Aggregate Functions

ƒ Outer Join

Generalized Projection j

ƒ Extends the projection operation by allowing arithmetic p j p y g functions to be used in the projection list.

∏ _{F1, F2, , , … , Fn ,} (E)

à E is any relational-algebra expression

à Each of F ₁ , F ₂ , …, F _n are are arithmetic expressions involving constants and attributes in the schema of E.

ƒ Find how much more each person can spend credit-info(customer-name, limit, credit-balance) f ( )

∏ customer-name, limit – credit-balance (credit-info)

Aggregate Functions and Operations

ƒ Aggregation function

gg g p

gg g

à takes a collection of values and returns a single value as a result.

à avg, min, max, sum, count

ƒ Aggregate operation in relational algebra

g ^(E)

G1, G2, …, Gn g F1(A1), F2(A2), …, Fm(Am) (E)

à E is any relational-algebra expression

à G ₁ , G ₂ … , G _n is a list of attributes on which to group (can be empty)

F i f i d

à F _i is an aggregate function, and

à A _i is an attribute name, for i=1, …, m

Aggregate Operation – Example gg g p p

ƒ Relation r:

A B α α

C α 7

α β

α β β

7 7 β 3

β

β β

3 10

sum C

g ^{sum(c) (r) sum-C}

27

Aggregate Operation – Example

ƒ Relation account

gg g p p

branch-name account-number n h n o n n balance n Perryridge

Perryridge

A-102 A-201

400 900 Brighton

Brighton Redwood

A-217 A-215 A-222

750 750 700

g ^(account) branch-name balance

branch-name g sum(balance) (account)

Perryridge Brighton Redwood

1300 1500 700

ƒ Result of aggregation does not have a name

C i i i ( i SQL)

Redwood 700

à Can use rename operation to give it a name (as in SQL)

Outer Join J

ƒ An extension of the join operation that avoids loss of j p information

à Compute the join

à add tuples that do not have matching tuples in the other relation

‚ fill in undefined attribute values with null

ƒ Three types

à left outer join

à right outer join

à full outer join

ƒ Conventional join is called inner join

Outer Join – Example J p

loan-number branch-name amount

ƒ Relation loan o n n o n

L-170 L-230 L 260

3000 4000 1700 Downtown

Redwood

P id

L-260 Perryridge 1700

ƒ Relation borrower

customer-name loan-number Jones

S i h

L-170 L 230 Smith

Hayes

L-230 L-155

ƒ Inner join: loan Borrower

ƒ Inner join: loan Borrower

loan-number branch-name amount customer-name

L-170 Downtown 3000 Jones

Outer Join – Example

ƒ Left outer join:

J p

loan-number branch-name amount customer-name loan borrower

o n n o n

L-170 L-230 L 260

3000 4000 1700

o n

Jones Smith

ll n h n

Downtown Redwood

P id

L-260 Perryridge 1700 null

ƒ Right outer join : loan borrower

loan-number amount

L-170 L 230

3000 4000

customer-name Jones

Smith branch-name

Downtown Redwood L-230

L-155

4000 null

Smith Hayes Redwood

null

ƒ Full outer join : loan-number branch-name amount customer-name

Null Values

ƒ null: an unknown or non-existing value g

ƒ The result of any arithmetic expression involving null is null

ƒ Aggregate functions

ƒ Aggregate functions

à simply ignore null values (SQL semantics)

à Is an arbitrary decision Could have returned null as result instead

à Is an arbitrary decision. Could have returned null as result instead.

ƒ For duplicate elimination and grouping

ll i d lik h l d ll d b h

à null is treated like any other value, and two nulls are assumed to be the same (SQL semantics)

à Alternative: assume each null is different from each other Alternative: assume each null is different from each other

à Both are arbitrary decisions

Null Values

ƒ Comparisons with null values return the special truth value unknown

à Why do we need unknown?

à If false was used instead of unknown, then

not (A < 5) would not be equivalent to A >= 5 not (A < 5) would not be equivalent to A > 5

ƒ Three-valued logic using the truth value unknown:

à OR: (unknown or true) = true, (unknown or false) = unknown (unknown or unknown) = unknown

à AND: (true and unknown) = unknown, ( ) (false and unknown) = false,

(unknown and unknown) = unknown

à NOT: (not unknown) = unknown ( )

à In SQL, “P is unknown” evaluates to true if predicate P evaluates to unknown

ƒ Result of select predicate is treated as false if it evaluates to unknown

Modification of the Database

ƒ The content of the database may be modified using the y g following operations:

à Deletion

à Insertion

à Updating

ƒ All these operations are expressed using the assignment operator All these operations are expressed using the assignment operator.

Deletion

ƒ A delete request is expressed similarly to a query, except instead q p y q y p of displaying tuples to the user, the selected tuples are removed from the database.

ƒ Deletion operation in relational algebra : r ← r E

r ← r – E

where r is a relation and E is a relational algebra query.

ƒ You can only delete whole tuples;

à cannot delete values on only particular attributes

=> should use update operation

Deletion Examples

ƒ Delete all account records in the Perryridge branch.

p

account ← account – σ branch-name = “Perryridge” (account)

ƒ Delete all loan records with amount in the range of 0 to 50 loan ← loan – σ _{amount ≥ 0} and amount ≤ ₅₀ (loan)

ƒ Delete all accounts at branches located in Needham.

r ₁ ← σ branch-city = “Needham” (account branch)

r ← ∏ _{b h b b l} (r )

r ₂ ← ∏ branch-name, account-number, balance (r ₁ )

r ₃ ← ∏ customer-name, account-number (r ₂ depositor)

t ← t

account ← account – r ₂

depositor ← depositor – r ₃

Insertion

ƒ To insert data into a relation, we either:

à specify a tuple to be inserted

à write a query whose result is a set of tuples to be inserted

ƒ Insertion operation in relational algebra:

r ← r ∪ E r ← r ∪ E

where r is a relation and E is a relational algebra expression.

ƒ The insertion of a single tuple is expressed by letting E be a

constant relation containing one tuple.

Insertion Examples p

ƒ Insert information in the database specifying that Smith has p y g

$1200 in account A-973 at the Perryridge branch.

account ← account ∪ {(“Perryridge”, A-973, 1200)}

account ← account ∪ {( Perryridge , A 973, 1200)}

depositor ← depositor ∪ {(“Smith”, A-973)}

ƒ Provide as a gift for all loan customers in the Perryridge branch, a $200 savings account. Let the loan number serve as the

account number for the new savings account.

r ₁ ← (σ branch-name = “Perryridge” (borrower loan))

account ← account ∪ ∏ branch-name account-number 200 branch-name, account-number,200 (r ( _{1 1} ) )

depositor ← depositor ∪ ∏ ,(r )

Updating p g

ƒ A mechanism to change a value in a tuple without changing all g p g g values in the tuple

ƒ Use the generalized projection operator to do this task Use the generalized projection operator to do this task r ← ∏ F1, F2, …, FI, (r)

Each F _i , is either

à the ith attribute of r: the attribute is not updated, or,

à an expression, involving only constants and the attributes of r, which gives

h l f h ib h ib i d d

the new value for the attribute: the attribute is updated

Update Examples p p

ƒ Make interest payments by increasing all balances by 5 percent. p y y g y p account ← ∏ account#, branch-name, balance*1.05 (account)

ƒ Pay all accounts with balances over $10,000 6 percent interest

d ll h 5

and pay all others 5 percent account ←

∏ account#, branch-name, balance*1.06 _{, ,} (σ _{balance > 10000} (account) ) ∪

∏ account#, branch-name, balance*1.05 (σ _{balance ≤ 10000} (account) )

END OF CHAPTER 2

END OF CHAPTER 2