what would a database system look like if it were NOT relational

problems
1) a lot of repeated data
2) inconsistent data

related tables

CustID on the Customer Table is a primary key
uniquely identifies a record

OrderID on the Orders Table is a primary key
uniquely identifies a record

benefits of a relational database:
1) smaller database, no repeated data
2) consistent data

BillCustId and ShipCustID are foreign keys
match up with primary key of another table

Indexing
What if I have 1 million records and I want to search for "Josh Waxman" as the name? How long will it take, on average, to find that record?

Why will it take 5 minutes? Sequential search.
(n+1)*(n/2)
(n^2 +n)/2
divide by n to get average
(n+1)/2 is the average

with 1 million records, sequential search will take (n+1)/2, or 500,000 time units, on average

within the CS department, there is a course called Analysis of Algorithms. Algorithm: a recipe for solving a problem.

Binary search would be much faster. But needs items to be in sorted order.

It is like the high-low game.
mid = (top + bottom)/2
if num looking for is more:
  top = mid + 1

if num looking for is less:
  bottom = mid - 1

we can either have a sorted list Or we can have Binary Search Tree. Course in CS dept called Data Structures. considers how to store collections of data.

if indexed, instead of O(n), it will take O(log n), or 20 searches for a million records.

we are skipping ch 1 hands on 2. we are on page 581, ch 1 hands on 3.

Quiz next time we meet; also Excel exam

The quiz on Ch4 in lecture book.
from SUNDAY, OCTOBER 23, 2011 until
SUNDAY, NOVEMBER 13, 2011

Read, do quickchecks of Ch 6