indexing

normalization

• used to reduce redunancy and null values

• done by using functional dependencies (rules)

• 1NF: each cell is atomic (either its goes thru or it doesn’t start at all)

BCNF

all functional dependencies are either on the candidate key or trivial

3NF

all functional dependencies satisfy BCNF or are on the right side of the candidate key

indexing

• speeds up data search

• search key: attribute used to search a set of attributes

• ordered: search keys are stored in order

• hash: search keys are spread out using hash function (in “buckets”)

ordered index

• primary index: tells the sequential order

• secondary index: tells an order different from sequential

B tree

• automatically reorganizes itself, reorganization doesn’t interfere with performance

• requires extra insertion and deletion overhead

B tree vs index-sequential

• B tree is mostly better

• index-sequential is only used if the database is never updated, or you want faster search time