CIS Exam 2

union

an element appears as the sum of the number of times it appears in each bag

tuple t appears n+m times

intersection

an element appers as the minimum of the number of times it appears in either

tuple t appears min(n,m) times

difference

tuples t appears max(0, n-m) times

elimination operator

R1 consists of one copy of each tuple that appears in R2 one or more times

turns into a set

sorting operator

R1 is the list of tuples of R2 sorted first on the value of the first attribute

breaks ties arbitrarily

becomes a sorted list not a relation

grouping operator

Group R according to all grouping attributes

within each group, compute agg(A) for each aggregation in list L

results as one tuple for each group

1

true

0

false

.5

unknown

in

true IFF the tuple is a member of the relation produced by the subquery

exists

true IFF the subquery result is not empty

any

boolean condition that is true IFF X equals at least one tuple in the subquery results

all

true IFF for every tuple t, in the relation X, it is not equal to t

aggregations

nulls ignored

gets a single value

inserting a tuple

insert into <relation> (attributes)

values()

inserting many tuples

insert into <relation>

(<subquery>)

functional dependency

if 2 tuples in R agree on attributes A1, A2 then they must agree on B1, B2

key

{A1, A2} functionally determines all other attributes of R(A1, A2, unique)

candidate key

no proper subset of {A1, A2} functionally determines all other attributes of R(A1, A2, … is minimal)

no attributes can be removed without losing the ability to uniquely identify a record (it is a minimal superkey). [1, 2, 3]

superkey

superset of keys (carries key and any other attributes)

may not be minimal

transitivity

if X→Y and Y→Z then X→Z

augmentation

if X→Y then XZ→YZ for any Z

equivalency

the set of relation instances satisfying S is the exact same as the set of relation instances satisfying T

trivial

the left side is a subset of the right side

closure test

look for FD’s on the left side X that is a subset of the current Y+

if the FD is X→A add it to Y+

minimal basis

all FDs have singleton right sides

if any FD is removed, the result is not longer a basis

if for any FD we remove one or more attributes from the left side, the result is not longer a basis

first normal form

atomic values- each cell must contain a single value

no repeating groups

uniqueness of records

second normal form

no partial dependency- all nonkey attributes must depend on the entire key, not just part of it

applies to just composite primary keys

X→Y where X is a full key and Y is nonkey

third normal form

no transitive dependencies- a nonkey attribute should not depend on another nonkey

X→Y where X is a key and Y is a nonkey

Boyce codd normal form

for every nontrivial FD X→A, X is a superkey

nontrivial- A is not a member of set X

superkey- any superset of a key

3NF vs BCNF

3NF allows a relation to have nonprime attributes dependent on a candidate key as long as the nonprime attribute is not transitively dependent on a nonkey attribute

properties of decomposition

recovery and dependency preservation

recovery

it should be possible to project the original relations onto the decomposed schema, and then reconstruct the original data

dependency preservation

it should be possible to check in the projected relations whether all the FDs given are satisfied

BCNF

satisfy recovery

cannot always satisfy recovery and dependency preservation

3NF

can satisfy recovery and dependency preservation

atomicity

all or nothing fashion (at transaction level)

consistency

constraints applied before and after running transactions

each client, each transaction

• can assume all constraints hold when a transaction begins

• must guarantee all constraints hold when a transaction ends

isolation

serialized

concurrent access but final behavior is in some serial order

use locking mechanism

durability

transactions that committed changes only

at system level

system initiated or client initiated

dirty read

a data item written by uncommitted transactions

phantom tuples

tuples that emerge during execution

serializability

most consistent

decreased performance

less concurrency

read uncommitted

allows for dirty read

wont ensure global serialization

non-repeatable read and phantom tuples

read committed

dont allow for dirty read

wont ensure global serialization

non-repeatable read and phantom tuples

repeatable read

dont allow for dirty read

wont ensure global serialization

same read items cannot change values (no non-repeatable read)

yes phantom tuples

committed

system saved changes, transaction was processed

uncommitted

system was interrupted with rollback to last committed transaction

0

count(all Null values)

count(*)

nulls included- how many tuples in the relation

delete

1) mark all tuples for which WHERE condition is satisfied

2) delete marked tuples

> ANY

> minimum value

< ANY

< maximum value

> ALL

> maximum value

< ALL

< minimum value

transaction

a group of sql statements that are treated as a unit and executed in isolation