1Relational Algebra and SQLPart 1: Relational AlgebraChapter 6Many of these slides are identical to or based on slides copyright © 2002 by Lewis, Bernstein and Kifer. They are used by permission. Others slides are copyright © 2004 by Jack C. Wileden. All rights reserved.2Relational Query Languages• Languages for describing queries on arelational database••Structured Query LanguageStructured Query Language (SQL)– Predominant application-level query language– Declarative••Relational AlgebraRelational Algebra– Intermediate language used within DBMS– Procedural3What is an Algebra?• A language based on operators and a domain of values• Operators map values taken from the domain intoother domain values• Hence, an expression involving operators andarguments produces a value in the domain• When the domain is a set of all relations (and theoperators are as described later), we get the relationalrelationalalgebraalgebra• We refer to the expression as a queryquery and the valueproduced as the queryquery resultresult4Relational Algebra• Domain: set of relations• Basic operators: selectselect, projectproject, unionunion, setsetdifferencedifference, CartesianCartesian productproduct• Derived operators: set intersectionset intersection, divisiondivision, joinjoin• Procedural: Relational expression specifies queryby describing an algorithm (the sequence in whichoperators are applied) for determining the result ofan expression5The Role of Relational Algebra in a DBMS6Select Operator• Produce table containing subset of rows ofargument table satisfying condition!condition (relation)• Example: Person Person !Hobby=‘stamps’(PersonPerson)1123 John 123 Main stamps1123 John 123 Main coins5556 Mary 7 Lake Dr hiking9876 Bart 5 Pine St stamps1123 John 123 Main stamps9876 Bart 5 Pine St stamps Id Name Address Hobby Id Name Address Hobby7Selection Condition• Operators: <, #, $, >, =, %• Simple selection condition:– <attribute> operator <constant>– <attribute> operator <attribute>• <condition> AND <condition>• <condition> OR <condition>• NOT <condition>8Selection Condition - Examples•! Id>3000 OR Hobby=‘hiking’ (PersonPerson)•! Id>3000 AND Id <3999 (PersonPerson)•! NOT(Hobby=‘hiking’) (PersonPerson)•! Hobby%‘hiking’ (PersonPerson)9Project Operator• Produces table containing subset of columnsof argument table "attribute list(relation)• Example: PersonPerson "Name,Hobby(PersonPerson)1123 John 123 Main stamps1123 John 123 Main coins5556 Mary 7 Lake Dr hiking9876 Bart 5 Pine St stampsJohn stampsJohn coinsMary hikingBart stamps Id Name Address Hobby Name Hobby10Project Operator1123 John 123 Main stamps1123 John 123 Main coins5556 Mary 7 Lake Dr hiking9876 Bart 5 Pine St stampsJohn 123 MainMary 7 Lake DrBart 5 Pine StResult is a table (no duplicates); can have fewer tuplesthan the original Id Name Address Hobby Name Address• Example: PersonPerson "Name,Address(PersonPerson)11Expressions1123 John 123 Main stamps1123 John 123 Main coins5556 Mary 7 Lake Dr hiking9876 Bart 5 Pine St stamps1123 John9876 BartId Name Address Hobby Id NamePersonPersonResultResult" Id, Name (! Hobby=’stamps’ OR Hobby=’coins’ (PersonPerson) )12Set Operators• Relation is a set of tuples, so set operationsshould apply: &, ', ( (set difference)• Result of combining two relations with a setoperator is a relation => all its elementsmust be tuples having same structure• Hence, scope of set operations limited tounion compatible relationsunion compatible relations13Union Compatible Relations• Two relations are union compatibleunion compatible if– Both have same number of columns– Names of attributes are the same in both– Attributes with the same name in both relationshave the same domain• Union compatible relations can becombined using unionunion, intersectionintersection, and setsetdifferencedifference14ExampleTables: PersonPerson (SSN, Name, Address, Hobby) ProfessorProfessor (Id, Name, Office, Phone)are not union compatible. But " Name (PersonPerson) and " Name (ProfessorProfessor)are union compatible so " Name (PersonPerson) - " Name (ProfessorProfessor)makes sense.15Cartesian Product• If RR and SS are two relations, RR ) SS is the set of allconcatenated tuples <x,y>, where x is a tuple in RRand y is a tuple in SS––RR and SS need not be union compatible••RR ) SS is expensive to compute:– Factor of two in the size of each row– Quadratic in the number of rows A B C D A B C D x1 x2 y1 y2 x1 x2 y1 y2 x3 x4 y3 y4 x1 x2 y3 y4 x3 x4 y1 y2 RR SS x3 x4 y3 y4 RR) SS16Renaming• Result of expression evaluation is a relation• Attributes of relation must have distinct names.This is not guaranteed with Cartesian product– e.g., suppose in previous example A and C have thesame name• Renaming operator tidies this up. To assign thenames A1, A2,… An to the attributes of the ncolumn relation produced by expression expr use expr [A1, A2, … An]17ExampleThis is a relation with 4 attributes: StudId, CrsCode1, ProfId, CrsCode2TranscriptTranscript (StudId, CrsCode, Semester, Grade)TeachingTeaching (ProfId, CrsCode, Semester) " StudId, CrsCode (TranscriptTranscript)[StudId, CrsCode1] ) " ProfId, CrsCode(TeachingTeaching) [ProfId, Crscode2]18 Derived Operation: JoinA (general or theta) join join of R and S is the expressionR join-condition Swhere join-condition is a conjunction of terms: Ai oper Biin which Ai is an attribute of R; Bi is an attribute of S;and oper is one of =, <, >, $ %, #.The meaning is:! join-condition´ (R ) S)where join-condition and join-condition´ are the same,except for possible renamings of attributes (next)19Join and Renaming• Problem: R and S might have attributeswith the same name – in which case theCartesian product is not defined• Solution:– Rename attributes prior to forming the productand use new names in join-condition´.– Common
View Full Document
Unlocking...