- Safety equivalences
- Relation Algebra
- Storage and Hardware
- B+ Trees
- Join implementations
Databases - DBMS
DBMS - We use it for efficiency, handling large data, integrity, access control, concurrent access, data independence.
Conceptual and semantic - UML
Logical Model - trees & graphs
Physical Model - indexing, clustering
Deletion of a required item:
- Delete dependent fields, cascade.
- Reject deletion.
- Change dependent field to default.
A schema describes valid instances.
Extended ADOM, also allows constants.
ADOM RC– = ADOM RC with no constants ADOM RC is safe.
ADOM RC– = RA = All safe queries.
ADOM RC = RA (without consts) = Safe RC without constants.
SQL with subqueries = RA = ADOMRC = SafeDRC
AdomRC ⊆ RA ⊆ DRC
P(R(col-->col2, col3-->col3'), expr);
Calculate expr, rename the result to R, and rename columns as specified.
Create table table_name(
Foreign key target is a primary key or unique.
Storage and hardware
Data is on pages in disk.
We retrieve pages.
Estimated Result sizes
col = value Rf = 1 / NVals(col)
col = col2 Rf = 1 / Max(NVals(col), NVals(col2))
col > value Rf = High(I) - value / High(I) - Low(I)
Insert and push up if too full.
Delete and steal from siblings if need be.
If they don't have spare capacity; merge.
Simple Nested Loop Join.
Page Oriented Nested Loop Join.
Block Nested Loop Join.
Index Nested Loop Join.
Serial schedule : No interleaving of transactions.
Serialisable: equivalent to a serial schedule.
Equivalence: On the same input, give the same output database for a set of xacts. then two schedules are equivalent.
A conflict is a read/write sequence (where at least one action is a write), by different transactions on the same object.
Schedules are conflict equivalent if they deal with the same actions, and conflicts appear in the same order.
Conflict serialisable if conflict equivalent to a serialisable schedule.
Shared Lock - Needed to read.
Exclusive Lock - Needed to write.
Conflict graph - wait for graph. Transactions are nodes. Precedence/waiting is an edge.