7 Basic Relational Algebra operations

7 Basic Relational Algebra operations: 

– Selection 

– Projection 

– Join 

– Union 

– Intersection 

– Difference 

– Cartesian product 

5 Primitive operators are:

SELECTION, PROJECTION, UNION, DIFFERENCE and CARTESIAN PRODUCT

ITEM(Item-Id, Description, Pack, Unit-Price)

1. Selection (sigma)

σ predicate (R)

- Produces a horizontal subset of R consisting of tuples which satisfy the predicate.

- Selection means which rows are to be returned.

e.g.

List items whose item_id is less than 'I35'

σ Item-id < “I35” (ITEM)

SELECT item_id, description, pack, to_char(unit_price,'$9,990.99') as unit_price 
FROM ITEM
WHERE item_id < 'I35';

 item_id < 'I35' is the selection part.

ITEM_ID  DESCRIPTION  PACK  UNIT_PRICE

-------- --------------- ---------- ----------

I26      Bolt                    10      $0.10

I22      Spanner                1      $5.50

I34      Nail                    20      $3.45

2. Projection (pi)

π column list (R)

- Produces a vertical subset of R consisting of columns in the column list.

- Projection means choosing which columns (or expressions) the query shall return.

e.g. List all items by item_id and Description

SELECT item_id, description FROM ITEM;

item_id, description is the projection part

ITEM_ID  DESCRIPTION   

-------- ---------------

I26      Bolt           

I35      Nut            

I87      Washer         

I22      Spanner        

I98      Tool Box       

I56      Hammer         

I34      Nail           

3. Join

Join operator is used for combining data from two or more relations, based on a common attribute or attributes.

- Types of Joins:

- Theta-join

- Equi-join

- Natural-join

- Outer-join

SUPPLIER (Item_id, Supp_id)

ITEM_ID  SUPP_ID

-------- --------

I26      S44     

I87      S22     

I22      S10     

I98      S10     

I56      S43    

1. Using Theta-join

(Relation_1) ⋈F (Relation_2)

e.g. List all items and their suppliers id

(ITEM) ⋈ Item.Item_Id = Supplier.Item_Id (ITEM_SUPPLIER)

SELECT 
i.item_id, 
i.description, 
pack, 
to_char(i.unit_price,'$9,990.99') as unit_price, 
s.item_id, 
s.supp_id 
FROM ITEM i
JOIN supplier s
on i.item_id = s.item_id;

2. Using Natural Join

(ITEM) ⋈ (ITEM_SUPPLIER)

Duplicate attributes are eliminated

1 2 3

SELECT  item_id,  description,  pack,  to_char(unit_price,'$9,990.99') as unit_price,  supp_id  FROM ITEM NATURAL JOIN supplier; Colored by Color Scripter

cs

3. Outer join

(ITEM) ⋊ (ITEM_SUPPLIER)

Everything in ITEM and SUPPLIER is included, with ITEM on the left side.

e.g. List all items and suppliers including where there is no supplier

SELECT 
i.item_id, 
i.description, 
i.pack, 
to_char(i.unit_price,'$9,990.99') as unit_price, 
s.item_id, 
s.supp_id
FROM item i
LEFT OUTER JOIN supplier s
on i.ITEM_ID = s.ITEM_ID;

- UNION, INTERSECTION, DIFFERENCE

These three operators require UNION - compatible tables.

Two tables said to be UNION - compatible if they have the same structure, the same number of columns and corresponding columns are defined over the same domain.

UNION: an operator that results in a table containing all the rows from both tables but no duplicate rows.

INTERSECTION: an operator that results in a table whose rows appear in both the contributing tables.

DIFFERENCE: an operator that results in a table whose rows occur in the first table but not the second.

4. Union

Student and Teacher tables are not union competible.

However, projection (vertical subsets) of the two tables may be union - competible.

e.g. π Surname, Suburb(STUDENT) ∪ π Surname, Suburb(TEACHER) 

List all students and teachers with their suburbs

SELECT surname, suburb
FROM student
UNION 
SELECT surname, suburb 
FROM teacher;

SURNAME         SUBURB   
--------------- ----------
Beige           Elmwood   
Black           Oakwood   
Blue            Elmwood   
Brown           Elmwood   
Gold            Ashwood   
Green           Oakwood   
Grey            Oakwood   
Maroon          Elmwood   
Orange          Ashwood   
Red             Oakwood   
Silver          Ashwood   
 
SURNAME         SUBURB   
--------------- ----------
Violet          Ashwood   
White           Elmwood   
Yellow          Oakwood   

14 rows are selected, instead of 15. This is because UNION eliminates duplicate rows.

5. Intersection

π Surname, Suburb(STUDENT) ∩ π Surname, Suburb(TEACHER)

e.g. List all students and their suburbs who have the same surname and suburb as a teacher.

SELECT surname, suburb
FROM student
INTERSECT
SELECT surname, suburb 
FROM teacher;

SURNAME         SUBURB   
--------------- ----------
Violet          Ashwood  

6. Difference

π Surname, Suburb(STUDENT) – π Surname, Suburb(TEACHER)

e.g. List all students with their suburb who do not have the same surname as a teacher

SELECT surname, suburb
FROM student
MINUS
SELECT surname, suburb 
FROM teacher;

SURNAME         SUBURB   
--------------- ----------
Black           Oakwood   
Blue            Elmwood   
Brown           Elmwood   
Gold            Ashwood   
Green           Oakwood   
Orange          Ashwood   
Red             Oakwood   
White           Elmwood   
Yellow          Oakwood 

7. Cartesian Product

Definition from orafaq.com

A Cartesian join or Cartesian product is a join of every row of one table to every row of another table. This normally happens when no matching join columns are specified. For example, if table A with 100 rows is joined with table B with 1000 rows, a Cartesian join will return 100,000 rows.

σ Item-Id < “I35”(ITEM) × σ Supp-Id = “S10”(ITEM_SUPPLIER)

e.g. List all item information for items with item_id less than "I35" and supplied by supplier S10

Select item_id less than I35 from ITEM

Cartesian Product

Select supplier ID = S10 from SUPPLIER

SELECT * 
FROM item i, supplier s
WHERE i.item_id < 'I35'
AND s.supp_id = 'S10';

ITEM_ID  DESCRIPTION           PACK UNIT_PRICE ITEM_ID  SUPP_ID
-------- --------------- ---------- ---------- -------- --------
I26      Bolt                    10         .1 I22      S10     
I22      Spanner                  1        5.5 I22      S10     
I34      Nail                    20       3.45 I22      S10     
I26      Bolt                    10         .1 I98      S10     
I22      Spanner                  1        5.5 I98      S10     
I34      Nail                    20       3.45 I98      S10  

Questions

1.  Discuss the following terms

• Relation: A Named table with columns and rows
• Attribute: Named column of a relation
• Domain: Domain of an Attribute is the set of values the attribute may take
• Tuple: A row of a relation
• Degree of a Relation: Number of attributes
• Cardinality of a Relation: Number of tuples

2.   Consider the CUSTOMER and ORDER relations below:

CUSTOMER (CUSTOMER-ID, NAME, ADDRESS)
ORDER (ORDER-ID, DATE, CUSTOMER-ID)

Assume a single customer may have any number of orders.

1. Identify the primary key and foreign key attributes in these relations.

CUSTOMER_PK = CUSTOMER-ID

ORDER_PK = ORDER-ID

2. Can you think of a reason why we would not just store all the customer and order information in one relation so that we would not have to perform the join operation?

Doing so would result in substantial data redundancy and would lead to insert, update and delete anomalies.

3. Suppose we have the following 4 relations:

HOTEL(HOTEL-NO, NAME, ADDRESS)

ROOM(ROOM-NO, HOTEL-NO, TYPE, PRICE)

BOOKING(HOTEL-NO,GUEST-NO, DATE-FROM, DATE-TO, ROOM-NO)

GUEST(GUEST-NO, NAME, ADDRESS)

Generate the relational algebra for the following queries:

1. List the names and addresses of all hotels.

SELECT name, address FROM hotel;
π name, address HOTEL

2. List all single rooms with a price below $50

SELECT room FROM hotel WHERE price < $50 AND type = 'single';
σ price < $50 and type = 'single' ROOM

3. List the names and addresses of all guests

SELECT name, address FROM GUEST;
π name, address GUEST

4. List the price and type of all rooms at the Grosvenor Hotel

SELECT r.price, r.type 
FROM ROOM r 
JOIN HOTEL h 
ON r.hotel-no = h.hotel-no 
WHERE h.name='Grosvenor';
 
GrosvenorNO = π price,type (σ name='Grosvenor' HOTEL)
π price, type (GrosvenorNO ⋈ ROOM)

5. List all names and addresses of guests currently staying at the Grosvenor Hotel (assume that if the guest has a tuple in the BOOKING relation, then they are currently staying in the hotel)

SELECT name, address
FROM guest g
JOIN booking b
ON g.guest-no = b.guest-no
JOIN hotel h
ON b.hotel-no = h.hotel-no
WHERE h.name = 'Grosvenor';
 
GrosvenorNO = π hotel-no (σ name = 'Grosvenor' HOTEL)
GrosvenorBookings = π guest-no(GrosvenorNO ⋈ BOOKINGS)
ANSWER = π name, address (GrosvenorBookings ⋈ GUEST)

6. Using the sample tables below, show how the JOIN operation can be expressed in terms of the fundamental operators by showing the process to do a natural join of customer and order.

CUSTOMER
   CUST_ID NAME     
---------- ----------
         1 Green     
         2 Blue      
 
ORDERS
  ORDER_ID ORDER_DATE    CUST_ID
---------- ---------- ----------
         1 23-FEB-09           1
         2 26-FEB-09           1
         3 26-FEB-09           2

Fundamental operators are: SELECTION, PROJECTION, UNION, DIFFERENCE, CARTESIAN PRODUCT

Cartesian = CUSTOMER X ORDERS
σ C.Cust_id = O.Cust_id
π cust_id