Databases Conceptual Things Exam 2

0.0(0)
Studied by 2 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/54

encourage image

There's no tags or description

Looks like no tags are added yet.

55 Terms

1
New cards

Selection Operator

R1 := σC (R2) (Sigma)

2
New cards

Projection Operator

R1 := πL(R2) (Pi)


3
New cards

Natural Join Operator

 R3 := R1 ⋈ R2 (Bowtie)

4
New cards

Theta Join Operator

R3 := R1 ⋈C R2 (Bowtie + condition)

5
New cards

Bag algebra differs from set algebra because it allows ____

Duplicates

6
New cards

Union in Bag Algebra

Take the “sum” of times an entry appears in result

<p>Take the “sum” of times an entry appears in result</p>
7
New cards

Intersection in Bag Algebra

Take the minimum amount of times an entry appears in either set

<p>Take the minimum amount of times an entry appears in either set</p>
8
New cards

Difference in Bag Algebra

#Occurences in A - #Occurences in B

<p>#Occurences in A - #Occurences in B</p>
9
New cards

Duplicate Removal Operator (Bag Algebra)

δ(R) (Delta)

10
New cards

Sort Tuples to List Operator (Bag Algebra)

τA1,A2..(R) (Tau)

Important! Ties are broken by the order of columns listed after tau

11
New cards

Extended Projection Operator (Bag Algebra)

πA1,A2..(R) (Pi)

<p><span>π<sub>A1,A2..(R)</sub> (Pi)</span></p>
12
New cards

Grouping Operator (Bag Algebra)

γA1,A2..(R) (Gamma)

Can use SUM, AVG, COUNT, MIN, MAX

<p>γ<sub>A1,A2..(R)</sub> (Gamma)</p><p>Can use SUM, AVG, COUNT, MIN, MAX</p>
13
New cards

Natural Outer Join (Bag Algebra)

An outer join which includes nonmatching / dangling tuples as well

<p>An outer join which includes nonmatching / dangling tuples as well</p>
14
New cards

Theta Outer Join (Bag Algebra)

A theta join which includes nonmatching / dangling tuples (after joining matches)

<p>A theta join which includes nonmatching / dangling tuples (after joining matches)</p>
15
New cards

How outer joins / theta outer joins notated in comparison to their set algebra counterparts

Dot above the bowtie:]

16
New cards

Update Anomaly

Updating certain records in a DB while failing to update other related records, leading to conflicts

17
New cards

Deletion Anomaly

The potential to lose information by deleting a tuple / value not stored anywhere else in a DB

18
New cards

Definition of a Functional Dependency

  • If two tuples of R agree on attributes A1, A2 … An, they must agree on B1, B2, … Bn

  • Attribute A determines B denoted A -> B (Leftside -> Rightside)


19
New cards

Armstrong Axioms of a Functional Dependency

  • Reflexivity

  • Augmentation

  • Transitivity


rat?

20
New cards

Is the Superkey Valid?

Relation Home = {address, owner, residents, floors, bedrooms, bathrooms, has_backyard, has_pool}

Key = {address, owner}

Superkey = {address, owner, bedrooms, bathrooms}

True

21
New cards

Is the Superkey Valid?

Relation Home = {address, owner, residents, floors, bedrooms, bathrooms, has_backyard, has_pool}

Key = {address, owner}

Superkey = {owner, residents, floors}

False

22
New cards

Is the Superkey Valid?

Relation Gamer = {username, platform, favorite_game, winrate, showers, peripherals_broken}

Key = {username, platform}

Superkey = {favorite_game, peripherals_broken}

False

23
New cards

Is the Superkey Valid?

Relation Gamer = {username, platform, favorite_game, winrate, showers peripherals_broken}

Key = {username, platform}

Superkey = {username, platform, favorite_game, winrate, showers, peripherals_broken}

True

24
New cards

Transitivity Rule of Functional Dependencies

If A → B, and B → C, then A → C

(A functionally determines B, B functionally determines C, thus A functionally determines C)

25
New cards

Augmentation Rule of Functional Dependencies

If A → B, then AX → BX for any set of attributes defined under X

26
New cards

Reflexivity Rule of Functional Dependencies

If B is a subset of A (B ⊆ A) then A → B

27
New cards

Splitting Rule of Functional Dependencies

If A → BC, we may say

A → B

A → C

28
New cards

Combining Rule of Functional Dependencies

If A → B and A → C, we may say

A → BC

29
New cards

Trivial Functional Dependency

The right side (determined) attributes are a subset of the left side (determining) attributes

30
New cards

Is the functional dependency trivial?
{A, Z, F} → A

True

31
New cards

Is the functional dependency trivial?

{A, Z, F} → C

False

32
New cards

Algorithmic Steps to Calculate Closure

Given set of FD, and value X, add X+ to closure of X

  1. For each set of attributes X, compute X+

  2. Add X→A for all A in X+ - X

  3. Drop XY → A whenever we discover X → A

    • XY → A follow from X → A in any projection

  4. Use only FD's involving projected attributes


<p>Given set of FD, and value X, add X<span><sup>+</sup></span> to closure of X</p><ol type="1"><li><p><span>For each set of attributes X, compute X<sup>+</sup></span></p></li><li><p><span>Add X→A for all A in X<sup>+</sup> - X</span></p></li><li><p><span>Drop XY → A whenever we discover X → A</span></p><ul><li><p><span>XY → A follow from X → A in any projection</span></p></li></ul></li><li><p><span>Use only FD's involving projected attributes</span></p></li></ol><p></p>
33
New cards

Basis in Functional Dependencies

The minimum set of Functional Dependencies for a given relation.

34
New cards

Minimal basis for functional dependencies satisfies which attributes

  • All FD's in B have singleton right sides

  • Any FD removed from B, result is no longer a basis

  • Any FD in B, we remove one+ attributes from left side of F, result is no longer a basis


<ul><li><p><span>All FD's in B have singleton right sides</span></p></li><li><p><span>Any FD removed from B, result is no longer a basis</span></p></li><li><p><span>Any FD in B, we remove one+ attributes from left side of F, result is no longer a basis</span></p></li></ul><p></p>
35
New cards

1NF (Normal Form 1) Requires

  • Atomic values (each cell contains only one value)

  • No repeating groups

  • No repeating tuples


36
New cards

2NF (Normal Form 2) Requires

  • Holding previous normal form requirements

  • Having no partial dependencies (all non-key attributes must depend on a primary key)

    • If X → Y, X should be entire key


37
New cards

3NF (Normal Form 3) Requires

  • Holding previous normal form requirements

  • Having no transitive dependencies: non-key attributes cannot depend on other non-key attributes, must depend on primary key

    • If X → Y, X should be a superkey OR prime attribute


38
New cards

Boyce Codd Normal Form (BCNF) Requires

For any X → Y, X is a superkey

Utilizes recursive algorithm to decompose

39
New cards

Recall the ACID properties of DBMS / transactions

Atomicity
Concurrency
Isolation
Durability

40
New cards

Atomicity

All or nothing transactions, every step passes or none do

41
New cards

Consistency

Each client and transaction must ensure all constraints hold when a transaction begins AND all constraints hold when a transaction ends

42
New cards

Isolation

Concurrent transactions should not interfere with each other

43
New cards

Durability

A transactions changes are permanent, and if interrupted they may be rolled back and started from the beginning

44
New cards

Order of isolation levels (least → most isoalted)

  1. Read uncommitted

  2. Read committed

  3. Repeatable read

  4. Serializable


Additionally, top to bottom:

Better → Worse performance, Lower → Higher consistency, Lower → Higher overhead


45
New cards

Dirty read

A data item can be written by uncommitted transactions (i.e., reading BEFORE external transaction modifying the read commits)

46
New cards

Non-Repeatable Read

Reading a tuple multiple times and getting different values due to a concurrent committ

47
New cards

Isolation levels are per ____

Transaction

48
New cards

Read Uncommitted Isolation Level

  • Permit dirty reads

  • Permit non-repeatable reads

  • Do NOT ensure global serialization


<ul><li><p>Permit dirty reads</p></li><li><p>Permit non-repeatable reads</p></li><li><p>Do NOT ensure global serialization</p></li></ul><p></p>
49
New cards

Read Committed Isolation Level

  • Do NOT permit dirty reads

  • Permit non-repeatable reads

  • Do NOT ensure global serialization


<ul><li><p>Do NOT permit dirty reads</p></li><li><p>Permit non-repeatable reads</p></li><li><p>Do NOT ensure global serialization</p></li></ul><p></p>
50
New cards

Repeatable Read Isolation Level

  • If a value is read more than once, ALWAYS use the same value as the initial read (Prevent non-repeatable read)

  • Do NOT permit dirty reads

  • Do NOT ensure global serialization

  • Permit phantom tuples


<ul><li><p>If a value is read more than once, ALWAYS use the same value as the initial read (Prevent non-repeatable read)</p></li><li><p>Do NOT permit dirty reads</p></li><li><p>Do NOT ensure global serialization</p></li><li><p>Permit phantom tuples</p></li></ul><p></p>
51
New cards

Serializable Isolation Level

  • Do NOT permit dirty reads

  • Ensure global serialization

  • Do NOT permit non-repeatable reads

  • Concurrent transactions are effectively the same as if they were ordered


52
New cards

Phantom Tuples

Tuples emerging during a transaction’s execution

53
New cards

Isolation levels that permit dirty reads

Read uncommitted

54
New cards

Isolation levels that permit non-repeatable reads

Read uncommitted, read committed

55
New cards

Isolation levels that permit phantom tuples

Read uncommitted, read committed, repeatable read