DATA3404 Lecture Notes - Lecture 5: Relational Algebra, Merge Sort, Scalability

• School: University of Sydney
• Department: Data Science
• Course: DATA3404
• Professor: Uwe Roehm

Document Summary

Sql gets translated into relational algebra, which can be shown as expression tree: operators have one or more input sets and return one (or more) output set(s). Query execution plan: tree of relational algebra operators, with choice of algorithm for each operator. Physical operations: relational algebra operators == logical operators which represent the intermediate results, physical operators show how query is evaluated. Indexing: can use where conditions to retrieve small set of tuples (selections, joins) Variations for projections: sorted tuples (order by, sort operation, duplicate removal (distinct, set operations, partition tuples by hashing or sorting, then remove duplicates. Select r. sid, r. bid from reserves r: trivial operation: just return subset of columns. Select distinct r. sid, r. bid from reserves r: more expensive: need to remove duplicates. Sorting approach: sort on and remove duplicates. (can optimize this by dropping unwanted information while sorting. ) Hashing approach: hash on to create partitions.