Teaching Relational Algebra and Relational Calculus: A Programming Approach Kirby McMaster – Weber State University Nicole Anderson - Weber State University Ashley Blake – Seabrook, Texas : Teaching Relational Algebra and Relational Calculus: A Programming Approach Kirby McMaster – Weber State University Nicole Anderson - Weber State University Ashley Blake – Seabrook, Texas
Slide2: Why Bother?
Should we teach relational algebra (RA) and relational calculus (RC) in database courses?
A 2001 survey of 106 database teachers (Robbert and Ricardo, 2003) reported:
92% covered SQL
70% included RA
42% mentioned RC
Slide3: Why Relational Algebra?
RA is the "operations on tables" part of the relational model.
RA provides a procedural way to query a database.
Knowledge of RA facilitates learning, using, and understanding SQL.
The DBMS query processor translates SQL code into RA operations.
Slide4: Why Relational Calculus?
Codd's 1970 database paper suggested predicate calculus (the basis for RC) as a query language.
RC provides a non-procedural way to query a database.
RC is the foundation for Query-By-Example.
RC can be used to develop an intelligent front-end for a database.
Slide5: How to Teach RA and RC?
Mathematical approach
Write queries using mathematical notation, but unable to execute them.
Programming approach
Write query code and watch it run.
RA function library
RC with Prolog
Slide6: Teaching Relational Algebra
Suppose an Inventory database consists of two tables, STOCK and STKTYPE:
STOCK STKTYPE
SNo (PK) TType (PK)
SType (FK) TName
SName ROP
QOH OSize
OnOrder
Slide7:
Inventory Query
List the stock number (SNo), stock name (SName),
quantity-on-hand (QOH), reorder point (ROP),
and order size (OSize) for all inventory items in which
the quantity-on-hand is at or below the reorder point,
and no order has been placed (OnOrder = 'N').
Slide8:
Mathematical approach
A common textbook approach for writing RA queries uses a mathematical notation that includes both infix operators and functional operators.
Using this notation, the Inventory Query could be written as:
πSNo,SName,QOH,ROP,OSize(σOnOrder=‘N’
(σQOH<=ROP(STOCK wvSType=TType STKTYPE)))
Slide9:
This query expression is easier to understand when it is divided into a sequence of RA operations:
TEMP1 ← STOCK wvSType=TType STKTYPE
TEMP2 ← σQOH<=ROP (TEMP1)
TEMP3 ← σOnOrder='N‘ (TEMP2)
TEMP4 ← πSNo,SName,QOH,ROP,OSize(TEMP3)
This format is clearer (but looks less like "Algebra").
Slide10:
Programming approach
A alternative approach for writing a RA query is to make a sequence of function calls, with each function performing one RA operation.
We have developed a function library called RAlgProc. RA queries that use this library can be executed in the Visual FoxPro environment. (Very little knowledge of FoxPro is required.)
Slide11:
The RAlgProc library includes functions to perform the following RA operations:
Operation Function
select TSelect(Table1,RowCond)
project TProject(Table1,ColList)
join TJoin(Table1,Table2,JoinCond)
union TUnion(Table1,Table2)
intersect TIntersect(Table1,Table2)
difference TMinus(Table1,Table2)
product TProduct(Table1,Table2)
divide TDivide(Table1,Table2)
rename TRename(Table1,ColName,NewName)
Slide12:
A sample RA program for the Inventory Query using the RAlgProc library is shown below.
* Relational Algebra – Inventory Query
set procedure to RALGPROC
T1 = TJoin('STOCK','STKTYPE',[SType=TType])
T2 = TSelect(T1,[QOH<=ROP])
T3 = TSelect(T2,[OnOrder='N'])
T4 = TProject(T3,[SNo,SName,QOH,ROP,OSize])
browse
Sample output is shown on the following slides.
Slide13: T1: JOIN Tables
Slide14: T2: SELECT Rows: QOH <= ROP
Slide15: T3: SELECT Rows: OnOrder = 'N' T4: PROJECT Columns
Slide16:
Inventory Query 2
List the stock number, stock name, and quantity-on-hand of all Truffles products.
A sample RA program for this query is:
* Relational Algebra – Inventory Query 2
set procedure to RALGPROC
T1 = TSelect('STKTYPE',[TName='Truffles'])
T2 = TJoin('STOCK',T1,[SType=TType])
T3 = TProject(T2,[SNo,SName,QOH])
browse
Note that the Join is performed after the Select.
Slide17:
T1: Select T3: Project T2: Join
Slide18: Teaching Relational Calculus
Relational Calculus is based on a branch of logic called Predicate Logic.
In programming, a predicate is a function in which the return value is either true or false.
RC uses predicates to specify the data in tables and the result sets for queries.
When RC is implemented as a Prolog program:
Table predicates are defined by facts.
Query predicates are defined by rules.
Slide19:
A table predicate is true for each set of facts that appear as a row in the database.
A query predicate is true whenever the logical expression for the rule is true.
The Prolog query processor searches through the table predicates to determine which row and column values cause a query predicate to be true.
Query output consists of all parameter values for which a query predicate is true.
Slide20:
Because the Prolog query engine performs the searching and pattern matching, a query program is non-procedural.
Students write RC queries by defining predicates--one for each table using facts, and one for each query using rules.
Slide21: Inventory Database in Prolog
/*
Inventory Database
Prolog implementation (Predicate Calculus)
*/
domains
SNo, QOH, ROP, OSize = integer
SType, SName, OnOrder, TType, TName = symbol
predicates /* One predicate for each table */
STKTYPE(TType, TName, ROP, OSize)
STOCK(SNo, SType, SName, QOH, OnOrder)
clauses /* Facts - one for each table row */
STKTYPE("B", "Basket", 60, 90).
STKTYPE("C", "CheeseCake", 50, 75).
STKTYPE("F", "Fudge", 120, 180).
STKTYPE("T", "Truffles", 90, 120).
STKTYPE("W", "Tower", 40, 60).
Slide22:
STOCK(101, "B", "Prune Basket", 65, "N").
STOCK(105, "B", "Pear Basket", 48, "N").
STOCK(107, "B", "Peach Basket", 21, "Y").
STOCK(202, "W", "Deluxe Tower", 54, "N").
STOCK(204, "W", "Special Tower", 29, "N").
STOCK(301, "T", "Mint Truffles", 116, "N").
STOCK(303, "T", "Almond Truffles", 44, "Y").
STOCK(304, "T", "Mocha Truffles", 72, "N").
STOCK(306, "T", "Mixed Truffles", 93, "N").
STOCK(401, "F", "Chocolate Fudge", 145, "N").
STOCK(404, "F", "Marble Fudge", 103, "N").
STOCK(502, "C", "Berry CheeseCake", 73, "N").
STOCK(505, "C", "Apple CheeseCake", 46, "N").
STOCK(506, "C", "Lemon CheeseCake", 18, "Y").
STOCK(508, "C", "Plain CheeseCake", 65, "N").
Slide23:
Inventory Query 1
List the stock number (SNo), stock name (SName),
quantity-on-hand (QOH), reorder point (ROP),
and order size (OSize) for all inventory items in which
the quantity-on-hand is at or below the reorder point,
and no order has been placed (OnOrder = 'N').
Inventory Query 2
List the stock number, stock name, and
quantity-on-hand of all Truffles products.
Slide24: Prolog (RC) Query Program
/* Inventory Queries */
include "STKDATA.PRO" /* Contains Database */
predicates
QUERY1(SNo, SName, QOH, ROP, OSize)
QUERY2(SNo, SName, QOH)
clauses /* Rules */
QUERY1(SNo, SName, QOH, ROP, OSize) if
STOCK(SNo, SType, SName, QOH, OnOrder)
and STKTYPE(TType, TName, ROP, OSize)
and SType = TType
and QOH <= ROP
and OnOrder = "N".
QUERY2(SNo, SName, QOH) if
STOCK(SNo, SType, SName, QOH, OnOrder)
and STKTYPE(TType, TName, ROP, OSize)
and SType = TType
and TName = "Truffles".
Slide25:
Query 1 Results Goal: QUERY1(SNo,SName,QOH,ROP,OSize).
SNo=105, SName=Pear Basket, QOH=48, ROP=60, OSize=90
SNo=204, SName=Special Tower, QOH=29, ROP=40, OSize=60
SNo=304, SName=Mocha Truffles, QOH=72, ROP=90, OSize=120
SNo=404, SName=Marble Fudge, QOH=103, ROP=120, OSize=180
SNo=505, SName=Apple CheeseCake, QOH=46, ROP=50, OSize=75
5 Solutions
Slide26: Goal: QUERY2(SNo,SName,QOH).
SNo=301, SName=Mint Truffles, QOH=116
SNo=303, SName=Almond Truffles, QOH=44
SNo=304, SName=Mocha Truffles, QOH=72
SNo=306, SName=Mixed Truffles, QOH=93
4 Solutions Query 2 Results
Slide27: Summary and Conclusions
This paper has described a programming approach for teaching Relational Algebra and Relational Calculus in database courses.
Instead of using mathematical notation for RA operations, we have created a FoxPro function library to perform RA queries.
We have shown how to use Prolog to express RC queries in a non-procedural form.
Sample query programs have been demonstrated in both the FoxPro and Prolog environments.
Slide28:
Programming can provide a valuable learning tool throughout the database course, not just for SQL.
Using this approach, students can learn RA and RC the same way they learn other computing concepts--by writing programs and watching them run.