Transcript ppt

Final Review
Tuesday, March 6, 2007
1
The Final
•
•
•
•
•
•
Date: Tuesday, March 13, 2007
Time: 6:30 - 8:30
Room: EE 037
You must come to campus
Open book exam :)
No computers :(
2
Problem 1: Queries
• SQL
• XPath/XQuery
3
SQL
•
•
•
•
•
•
Select-from-where
Subqueries
Aggregation
Nulls
Outer joins
Database modifications (insert/delete)
A tricky query: for each product, find total sales in November
4
XPath/XQuery
• Xpath: simple navigation /, //, *, […]
• Xquery: nest/unnest/renest/aggregates
A tricky query: eliminate duplicates in a collection of elements
5
Problem 2: Data Modeling
• E/R diagrams
• Functional dependencies and normal forms
• XML and semistructured data
6
E/R Diagrams
•
•
•
•
•
Relationships
Inheritance
Weak entity sets
Mapping to relations
SQL DDL:
– Creating tables
– Constraints
A tricky question: map a complex inheritance graph to relations
7
Functional Dependencies
•
•
•
•
•
Basic definitions
Computing the closure X+
Computing the keys
Checking if a relation is in BCNF
Decomposing into BCNF
Tricky questions: find FD’s in a view; give counterexamples to FDs
8
XML
•
•
•
•
XML syntax
DTD
From relations to XML
From XML to relations
A tricky question: N/A
9
Problem 3: Transactions
• Recovery
• Concurrency control
10
Recovery
• Undo log
• Redo log
• Undo/redo log
A tricky question: place a missing END-CHECKPOINT
11
Concurrency control
•
•
•
•
Serializability and conflict serializability
Locks
Timestamps
Validation
A tricky question: tell what happens in a schedule
12
Problem 4:
Query Processing Engine
•
•
•
•
•
•
Storage of database elements
Indexes
Logical algebra
Physical algebra
Optimizations
Size/cost estimation
13
Storage of Database Elements
• Storing records in blocks
• Storing attributes in records
A tricky question: N/A
14
Index Structures
• Types of indexes:
– Dense/sparse index
– Primary/secondary index
• B+-trees
• Hash tables:
– Extensible hash tables
A tricky question: perform insert/delete in a B+ tree or hash table
15
Logical Algebra
• Operators
– Some interesting ones: natural joins, semijoins
• Converting SQL into the algebra
A tricky question: SQL with NOT EXISTS to RA
16
Physical Operators
•
•
•
•
•
•
One-pass algorithms
Nested-loop joins
Two-pass algorithms based on sorting
Two-pass algorithms based on hash tables
Index-based algorithms
Their cost
A tricky question: N/A
17
Optimizations
• Algebraic laws
• The dynamic programming algorithm
• Pipelining
A tricky question: discuss alternative plans for a query
18
Size/Cost Estimation
• Simple size estimation formulas for
selection and join
• Histograms
– Eqdepth, eqwidth
A tricky question: N/A
19
General Advice
• Some problems will require thinking
– Use judgment
• Problem difficulty may be uneven:
– do the easy ones first
20
Grading
–Homework 35%
–Project: 35%
–Final: 30%
21
COMMIT
(The End)
22