database revision notes

Cost of Joins

Direct = A + B
[Needs suff memory]

Nested Loop = A + AB
with Buffer = A + Math.ceil(A/Buf-2)*B

Simple Loop = A + RecB [ XindexA + SelCardA ]
[index req]
XindexA : cost to access index
SelCardA = #tuple/#satisfy for A

Merge-Sort = 2A + 2A Math.ceil(log[deg]A) + 2B +2B Math.ceil(log[deg]B) + A + B
[A + B is the cost to join if they are already sorted]

Cost of write back(size of result)
Join Selectivity not known / No PK

JS = 1 / MAX(DistinctValueA, DistinctValueB)

Sz of join = Math.ceil(JS*RecA*RecB/bfr[size of joined tuple])

Minimal cover

1) All RHS only got 1 field
2) Remove each rule and check if can get it back w/o it

B+ tree
B = Block size // fit the nodes into a block
V = sz of key
D = sz of data pointer
P = sz of internal pointers[within node in tree]
p = no. of nodes in a block
Psp = sz of pointer for leaf node pointing to next leaf node(linked list)

Non-leaf node : pP + (p-1)V <= B
Leaf node : p[leaf] (V+D) + Psp <= B

NF
2NF
-no partial dependencies

3NF
-no transitive

BCNF
-Determinant is superkey

Equivalence
a = {A->C, AC->D}
b = {A->CD}

from a, {A}+ -> {ACD} covered {A->CD}
from b, {A}+ -> {ACD} covered {A->C}, {AC->D}
therefore, proven

DB Recovery
Immediate (Undo-Redo) / Defered Updates (Redo)

1) Find last checkpoint
2) 2 lists
-Committed Transaction
-Uncommitted Transaction
[ For Immediate Only
2b)
Analyze dependencies for any cascading and put affected commited to uncommited
-Undo UNCommitted
]
3) Redo commited
4) Restart uncommited

SQL optimise
Cartesian Product
Push select down and restrictive select first
Replace Cartesian Product with join
Push Project down

DB Security
1) Create View
2) Grant [*|select,...] on [table] to [user] [with Grant option]