Revision for Final ExamRelational Query LanguagesWhat is an Algebra?Relational AlgebraThe Role of Relational Algebra in a DBMSSelect OperatorSelection ConditionSelection Condition - ExamplesProject OperatorSlide 10ExpressionsSet OperatorsUnion Compatible RelationsExampleCartesian ProductRenaming in Cartesian ProductRenaming OperatorExampleDerived Operation: JoinTheta Join – ExampleSlide 21Equijoin Join - ExampleNatural JoinNatural Join (cont’d)Natural Join ExampleExample Data InstanceNatural Join and IntersectionDivisionDivision Using Our Existing OperatorsDivision: R1 ¸ R2Slide 31Division (cont’d)Division - ExampleRelational CalculusTuple Relational CalculusGeneric FormSimple example 1Simple example 2Elements of a tuple calculusMore Example:Q0Formal Specification of tuple Relational CalculusElements of formulaExample Queries Using the Existential QuantifierMore ExampleCont.Safe ExpressionsDomain Relational Calculus (DRC)DRCExamplesAlternative notationMore exampleSlide 52QBESummaryQuizThe Big Picture: SQL to Algebra to Query Plan to Web PageRelational Calculus: A Logical Way of Expressing Query OperationsDomain Relational CalculusMore Complex PredicatesSome ExamplesLogical EquivalencesFree and Bound VariablesCan Rename Bound Variables OnlySafetySafety and Termination GuaranteesMini-QuizTranslating from RA to DRCSelection: TR[ R]Projection: TR[i1,…,im(e)]Union: TR[R1 R2]Other Binary OperatorsSlide 72Limitations of the Relational Algebra / CalculusRevision for Final ExamProf. Sin-Min LeeDepartment of Computer ScienceRelational Query Languages•Languages for describing queries on a relational database•Structured Query LanguageStructured Query Language (SQL)–Predominant application-level query language–Declarative•Relational AlgebraRelational Algebra–Intermediate language used within DBMS–ProceduralWhat is an Algebra?•A language based on operators and a domain of values•Operators map values taken from the domain into other domain values•Hence, an expression involving operators and arguments produces a value in the domain•When the domain is a set of all relations (and the operators are as described later), we get the relational relational algebraalgebra•We refer to the expression as a queryquery and the value produced as the queryquery resultresultRelational Algebra•Domain: set of relations•Basic operators: selectselect, projectproject, unionunion, setset differencedifference, CartesianCartesian productproduct•Derived operators: set intersectionset intersection, divisiondivision, joinjoin•Procedural: Relational expression specifies query by describing an algorithm (the sequence in which operators are applied) for determining the result of an expressionThe Role of Relational Algebra in a DBMSSelect Operator•Produce table containing subset of rows of argument table satisfying conditioncondition (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 HobbyId Name Address HobbySelection Condition•Operators: <, , , >, =, •Simple selection condition:–<attribute> operator <constant>–<attribute> operator <attribute>•<condition> AND <condition>•<condition> OR <condition>• NOT <condition>Selection Condition - Examples Id>3000 OR Hobby=‘hiking’ (PersonPerson) Id>3000 AND Id <3999 (PersonPerson) NOT(Hobby=‘hiking’) (PersonPerson) Hobby‘hiking’ (PersonPerson)Project Operator•Produces table containing subset of columns of the table taken as argument 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 HobbyProject 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)Expressions1123 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) )Set Operators•Relation is a set of tuples, so set operations should apply: , , (set difference)•Result of combining two relations with a set operator is a relation; hence all its elements must be tuples having the same structure•Hence, scope of set operations limited to union compatible relationsunion compatible relationsUnion 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 relations have the same domain•Union compatible relations can be combined using unionunion, intersectionintersection, and setset differencedifferenceExampleTables: 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.Cartesian Product•If RR and SS are two relations, RR SS is the set of all concatenated tuples <x,y>, where x is a tuple in RR and y is a tuple in S S (but see naming problem next)(but see naming problem next)•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 SSRenaming in Cartesian ProductResult of expression evaluation is a relation.Attributes of relation must have distinct names. So what do we do if they
View Full Document