DBMS Components

1. Database
2. Database Administrator
3. Application Programs
4. Hardware

1. Data sharing
2. Centralized control
3. Redundancy control (normalization)
4. Data integrity
5. Data security
6. Views
7. Data independence

• Conceptual schema is a description of data and relationships
• HARD to achieve

• Physical storage can be changed without bothering users
• EASIER to achieve than LDI

1. DB design is complex
2. Cost (hardware/software)
3. Availability (single point of failure)
4. Speed vs. Flexibility

1. Data Description Language - turns conceptual schema into physical DB description
2. Data Manipulation Language - insert/delete data
3. Query Language - ask questions
4. Data Control Language - security

Defines record sizes, field representations, types of indices, etc.

1. Seek time
2. Rotational delay
3. Transfer time

Advantages

• can operate with a failed drive

Disadvantages

• cost

Advantages

• performance (parallelism)

Disadvantages

• no data replication
• increased prob. of disk failure

• Non-Redundant
• striping only
• good write performance
• no data redundancy

• Mirrored
• no striping
• opportunity for parallel reads
• 2x the number disks ($$$)

• Bit-Interleaved Parity
• striping unit = 1 bit
• can recover from disk failure

• Block-Interleaved Distributed Parity
• striping unit = 1 block
• parity blocks are distributed across all disks
• fairly complex controller design

• Indexed field is a candidate key
• Indexed records are sorted on the CK
• The DB file records are sorted on the CK
• Can have only one per DB file

• The indexed field is not a CK
• The indexed records are sorted on the key
• The DB records are sorted on the key

• The indexed field may be any field
• The index records are sorted
• The DB records are not sorted
• Can have as many secondary indices as needed

• Holds one record for each in DB file
• Can do 'existence check' on just the index

• Indexes only a subset of the field values
• Smaller, therefore faster searching

• Each node contains at most 2M keys
• Each node (excepting the root) has at least M keys
• A non-leaf node has at least 2 children
• All leaf nodes are at the same level
• A non-leaf node of n keys has n+1 children

• Each key is stored in a leaf node
• Copies of some keys occupy internal nodes
• Leaf nodes are linked sequentially left to right to create a sequence set
  • Linear searching
  • No extra storage required

• Has built-in disk pointers for keys in leaves
• Supports exact-match and range queries

• 'Wastes' storage capacity of internal nodes (relatively minimal)
• Insertions and deletions are a bit more complex

1. Requirements Analysis - talk to the client
2. Conceptual Design - create conceptual schema
3. Logical Design - convert to DBMS' implementation data model (normalization)
4. Physical Design - physical storage requirements

• Schema is tree-structured
• Only 1:M relationships (1 parent & M children)

• Graph-based
• A std. theory of DB Systems

• Theoretical foundation: set theory
• Uses no pointers
• No physical/logical schema distinction

• Could map object data into a tuple (awkward)
• Object persistence

{ e.surname, e.givenname, e.salary | Employee(e) Λ e.deptid = 5 }

{ p.Pname | P(p) Λ ∃q (SP(q) Λ p.P# = q.P#

Λ q.Qty > 200) }

{ s.sname | S(s) Λ s.status = 'Active' Λ 

(∃q)(SP(q) Λ s.S# = q.S# Λ

(∃p)(P(p) Λ q.P# = p.P# Λ

p.pname = 'Nut')) }

{ <o> | (∃n)(<nopqr> ∈ P Λ

(∃tu)(<stu> ∈ SP Λ n=t Λ

u > 200)) }

{ <k> | (∃jl)(<jklm> ∈ S Λ l='Active' Λ

    (∃st)(<stu> ∈ SP Λ j=s Λ

       (∃no)(<nopqr> ∈ P Λ n=t Λ

o='Nut'))) }

∏_sname (σ_{status>0 ∧ pname='Nut'}

(σ_S.S#=SP.S# (σ_P.P#=SP.P#

(S × (SP × P)))))

∏_pname (σ_qty>200 (σ_SP.P#=P.P# (SP × P)))

or

∏_pname (σ_qty>200 (SP ⋈_SP.P#=P.P# P)

SELECT sno, AVG(qty)

FROM spj

GROUP BY sno;

• Left Outer Join: retains unmatched tuples from left relation
• Right Outer Join: retains unmatched tuples from right relation
• Full Outer Join: retains all unmatched tuples

CREATE TABLE <name> (

     <attr. name> <data type> [NOT NULL],

     ...

     [PRIMARY KEY (<attr>)]

);

CREATE VIEW <name>

[(<attr. list>)]

AS <select stmt>;

CREATE VIEW supplierpart("Supplier Name","Part #")

AS SELECT DISTINCT sname, pno

     FROM s, spj

     WHERE s.sno = spj.sno;

UPDATE <relation name>

SET <attr. name> = <expression> [,...]

[FROM <relation list>]

[WHERE <condition>];

Ex:

  UPDATE m SET name = 'Ray' where id = 1;

DELETE FROM <relation name>

WHERE <condition>;

DROP [TABLE|INDEX|VIEW|DATABASE] <name>;

• Atomicity: Xacts are all or nothing
• Consistency: An Xact's actions retain the consistency of the DB
• Isolation: Each Xact thinks it's the only Xact in the system
• Durability: A completed Xact's changes are permanent - won't be lost
  

• Active: Xact is being executed
• Partially Committed: Xact's actions are complete but changes may not yet be on disk
• Committed: Xact's changes are on disk
• Failed: The Xact cannot finish, but partial changes still linger
• Aborted: All changes have been cleared away

• Follow the ECA model:
  • Event - causes the activation
  • Condition - if true, action is performed
  • Action - SQL statement(s)

1. Hard to write appropriate actions
2. Specified separately from relations
3. Can reduce concurrency of the DBMS
4. Trigger interaction
5. Rule Termination

CREATE TRIGGER <name>

{BEFORE/AFTER} {INSERT/DELETE/UPDATE}

ON <relation>

[ [FOR EACH ROW] WHEN (<condition>) ]

<PL/SQL block>;

1. Reflexivity: If B ⊆ A, then A→B
2. Augmentation: If C→D, then:
   1. C→CD
   2. CE→D
   3. CE→DE
3. Transitivity: If F→G and G→H, then F→H

A set of FD's is minimal if all of the following hold:

1. All FD's have only 1 attribute on their RHS
2. No attribute can be removed from the LHS of any FD w/o changing the closure
3. All of the FD's in the set are needed to retain the closure

1. Put FD's in Standard Form
2. Minimize the LHS of the FD's
3. Remove redundant FD's

A relation R is in 3NF if, for every non-trivial FD X→A that holds in R, either:

1. X is a superkey of R, or
2. A is a prime attribute of R.

Let R be a relational schema, and let A,B & C be subsets of R's attributes. B is multidependent on A (or A multidetermines B) iff the set of B values matching a given (A,C) pair of values depends only on the A set and is independent of the C set.

CREATE USER <username> [<options>];

• PASSWORD or IDENTIFIED BY <password>
• quotas
• limits on access (e.g. time)
• capabilities (to create DB's, to add users, etc.)

GRANT <privilege>

[ON <object>]

TO <user>

[WITH GRANT OPTION];

Ex:

  GRANT CREATE VIEW to smithj;

  GRANT SELECT ON supplier TO PUBLIC;

REVOKE <privilege>

[ON <object>]

FROM <user>;

Ex:

  REVOKE ALL PRIVILEGES

  ON supplier

  FROM PUBLIC;

TS - Top Secret

S - Secret

C - Classified

U - Unclassified

TS > S > C > U

Subjects (users, groups, etc.) have clearances; Objects (tables, tuples, etc.) have classifications

1. Simple Security Property: S can read O only when class(S) ≥ class(O)
2. Star Property: S can write O only when class(S) ≤ class(O)

1. Availability - to authorized users only
2. Confidentiality - preserve secrecy
3. Integrity - prevent data corruption and/or loss

Provide security from a more 'external' perspective, via:

1. Quality passwords
2. Data encryption (public-key encryption, digital signatures, etc.)

Be Able to recover DB's after accidents/disasters:

• Maintain off-site backups
• Log/journal DBMS actions
• Use a non-0-level of RAID

• Sanity-check all user input (i.e. range-checking)
• Trim excess characters from input strings
• Accept raw input only when necessary (i.e. use option lists)

• Usually orders of magnitude larger than an OLTP system
• Used to generate data summaries and to identify trends
• Often known as On-line Analytical Processing (OLAP)
• Serves as a key input source for data mining algorithms

• Cleaning - attempts to detect/correct errors and omissions in the data
• Reformatting - structures the data to match the schema of the DW
• Metadata ("data about data") - shows the origins of the DW's content
• Backflushing - returning cleaned data to the source DBMSes for re-integration

• The basic OLAP schema is the Star Schema
  • Fact table is at the center
• A variation: The Snowflake Schema
  • Becomes more generalized away from the center

Slicing: An equality selection in 1 or more dimensions
Dicing: A range selection in 1 or more dimensions
Pivoting: Changing the orientation (viewpoint) by rotating the n-dimensional array to 'hide' a dimension.

Roll-up: Moves from the current level in a dimension to the next more general level (ex. Dept→College)

Drill-down: Moves from the current level to the next more specific level (ex. Vegetable→Carrot)

1. Predictions of future events (DANGEROUS)
2. Identification of events (ex. system intrusion)
3. Classification (ex. Which discounts appeal to which customers?)

• Marketing - customer behavior, targetted emailing
• Finance - credit ratings, fraud detection
• Manufacturing - optimizing processes & resources
• Health care - drug side-effects, treatment effectiveness

The support of a rule is the fraction of transactions that satisfy the rule.

support(L=>R) = support(L∪R)

The confidence of a rule is the fraction of itemsets containing L that also contain R.

conf(L=>R) = supp(L∪R) / supp(L)

1. Join(s)
2. Select(s)
3. Project(s)

Project: Sequential Scan of relation

Select:

1. Sequential Scan (full table scan, linear search)
2. Binary Search
3. Index Scan

1. Nested-Loops Join (NLJ)
2. Sort-Merge Join (SMJ)
3. Hash Join

1. Change operators (ex. Do joins w/ nested queries)
2. Insist on a join ordering (ex. Replace "from s,sp" with "s JOIN sp")

/    CPU Registers     \

/      Cache Memory      \

/    Main Memory (RAM)    \

/ Solid-State Devices (SSDs) \

/  Hard (Magnetic Disk) Drives \

/ Tapes/Optical Disks (Libraries) \