Uiuc - Cs 411

Front 1

DBMS capabilities (3)

Back 1

Persistant storage
Programming interfaces
Transaction management

Front 2

DBMS should allow (4)

Back 2

schemas
queries
preserves large amounts of data
many users

Front 3

Wrote a paper describing “relations” in 1970

Back 3

Ted Codd

Front 4

DDL

Back 4

data-definition language

Front 5

DML

Back 5

data manipulation language

Front 6

Wrote a 1996 paper "Evolution of Data Management"

Back 6

Jim Gray

Front 7

What is a query plan?

Back 7

Sequence of actions sent from the compiler to the execution engine

Front 8

What are durable transactions?

Back 8

Completed only when a crash will not destroy them.

Front 9

Information components in a database (4)

Back 9

Data
Metadata
Statistics
Indexes

Front 10

What does ACID stand for?

Back 10

atomicity
isolation
durability
consistency

Front 11

Parts of the query compiler (3)

Back 11

query parser
query preprocessor (semantic checks, algebraic tree)
query optimizer

Front 12

Transaction processing tasks (3)

Back 12

Logging
Concurrency control
Deadlock resolution

Front 13

Slow storage of huge amounts of data. (Maybe using an arm to swap DVDs)

Back 13

tertiary storage

Front 14

Type of tree indexes use.

Back 14

A B-tree is much more efficient than a binary-tree search.

Front 15

Conditions for replacing an entity set with an attribute.

Back 15

Only "one" relations on E
No dependencies between E's attributes.
No relationship involves E more than once.

Front 16

Constraint Classes (5)

Back 16

Keys
Single-value constraints
Referential integrity constraints
Domain constraints
General contstraints

Front 17

Wrote a paper "The Entity-Relationship Model - Toward a Unified View of Data" in 1976

Back 17

Peter Chen

Front 18

Give two examples of single-value constraints

Back 18

keys
many-one relationships

Front 19

Referencial integrity constraints

Back 19

Ensure that a reference must exist.

Front 20

Multiplicity Constraints

Back 20

Look this up....

Front 21

How is a Weak Entity Set Notated. (5)

Back 21

The Weak Entity Set has a double box around it.
Any supporting relationships have a double diamond around them.
Supporting relations must have referential integrity.
Underlined attributes on a weak entity set participate in but are not the complete key.
A weak entity set can have multiple relationships with another entity.

Front 22

What is the name for the value in a column of a tuple?

Back 22

A component.

Front 23

What factors should be considered when choosing between ER, OO, and null-value approaches.

Back 23

Would a query involve multiple relations? Are there more relations than we want to manage? Are we wasting space?

Front 24

A functional dependency is what kind of restraint?

Back 24

single-value restraint

Front 25

What is the difference between a key and a superkey?

Back 25

A key is the minimal attributes needed to identify a unique tuple. Every key is a superkey. A superkey can also have extra attributes.

Front 26

What is the primary key?

Back 26

A primary key is the default key when there are more than one keys.

Front 27

What is the difference between a minimal and minimum key?

Back 27

Minimal = nothing can be thrown out.
Minimum = smallest possible

Front 28

What is the Object oriented approach?

Back 28

Each relation clones all of the attributes of the parent.

Front 29

What is the straight E/R approach?

Back 29

Each relation includes the parent's key. The data is split across the relations.

Front 30

What is the null value approach

Back 30

All entities in one big relation where some values are empty or null.

Front 31

What is the splitting/combining rule?

Back 31

If two functional dependecies have the same attributes on the left, the attributes on the right can be combined, and vice-versa for the splitting rule.

Front 32

Trivial dependencies are?

Back 32

When the B's are a subset of the A's

Front 33

Nontrivial dependencies are?

Back 33

When at least one of the B's is not among the A's.

Front 34

Completely nontrivial dependencies are?

Back 34

When no B's are A's. When there is only one B, this is the same as a nontrivial dependencies.

Front 35

How do you determine the key for a relation based on a many-many relationship?

Back 35

The keys of both connected entity sets are the key attributes of R.

Front 36

How do you determine the key for a relation based on a many-one relationship?

Back 36

Use the key from the entity on the "many" side but not the "one" side.

Front 37

How do you determine the key for a relation based on a one-one relationship?

Back 37

The new relation uses the key from either connected entity, it does not have it's own.

Front 38

What are Armstrong's Axioms?

Back 38

Reflexivity
Augmentation
Transitivity

Front 39

What is Reflexivity?

Back 39

The A's can always determine a subset of themselves. (trivial FDs)

Front 40

What is Augmentation?

Back 40

We can add something to the right side (B's) if we also add it to the left side (A's).

Front 41

What is Transitivity?

Back 41

If A->B and B->C then A->C.

Front 42

What is the Union rule?

Back 42

If X->Y and X->Z then X->YZ

Front 43

What is the Decomposition rule?

Back 43

If X->YZ then X->Y and X->Z

Front 44

What is the Pseudo-transitivity rule?

Back 44

If X->Y and YZ->U then XZ->U

Front 45

What is a "basis" for a relation?

Back 45

A minimal set of FD's that determine the complete set of FD's. (There can be more than one)

Front 46

What are the principle kinds of anomalies that occur when too much information is in one relation?

Back 46

Redundancy
Update anomalies
Delete anomalies

Front 47

What is 1st Normal Form?

Back 47

Atomic attribute values, and each row has the same columns.

Front 48

What is 2nd Normal Form?

Back 48

1NF plus all non-key attributes must depend on the primary key.

Front 49

What is 3rd Normal Form?

Back 49

2NF
left side must be a superkey or the right side must be a member of some key.

Front 50

What is Boyce-Codd Normal Form?

Back 50

The left side of the FD must be a superkey. Trivial FD's are allowed.

Front 51

What is 4th Normal Form?

Back 51

The left side of the MVD must be a superkey. Trivial MVD's are allowed.

Front 52

How do you find the closure of functional dependencies?

Back 52

S+ =
Loop foreach f in S, apply reflexivity and augment.
add the new FDs to S+ foreach pair of FDs in S, apply the
transitivity rule
add the new FD to S+
Until S+ does not change any further

Front 53

What is the BCNF decomposition algortihm?

Back 53

Input: relation R, set S of FDs over R
1) Compute S+
2) Compute keys for R (from ER or from S+)
3) Use S+ and keys to check if R is in BCNF, if not:
a) pick a violation FD f: A  B
b) expand B as much as possible, by computing A+
c) create R1 = A union B,R2 = A union (others in R)
d) compute all FDs over R1, using R and S+,
then compute keys for R1.
Repeat similarly for R2
e) Repeat Step 3 for R1 and R2
4) Stop when all relations are BCNF, or are two-attributes

Front 54

What do you call an attribute that is a member of a key?

Back 54

A prime attribute.

Front 55

What is object relational mapping?

Back 55

A way to simplify SQL statements by putting data into objects. Done by frameworks.

Front 56

What are the basic operations in relational algebra? (5)

Back 56

Union
Difference
Selection
Projection
Cartesian Product

Front 57

Who initially proposed relation algebra as an algebra on sets of tuples.

Back 57

T. Codd

Front 58

What is a dangling tuple?

Back 58

A tuple that fails to pair with the second relation in a natural join.

Front 59

How do you express the intersection of R and S using only the 5 basic operations?

Back 59

R - (R - S)

Front 60

How do you express assignment statements?

Back 60

T(A,B,C,D) := Project on L(Selection on c(R X S))
Answer(title, year) := Projection on a,b(T)

Front 61

What is a natural join?

Back 61

For each tuple in the first set, a new tuple is created in the result for each tuple in the second set which matches on identical attributes.

Front 62

What is a theta-join?

Back 62

A cartesian product followed by a selection.

Front 63

What does the duplicate elimination operator look like?

Back 63

Greek d?

Front 64

What does the grouping operator look like?

Back 64

Dentist pick with a bayonet?

Front 65

What does the sorting operator look like?

Back 65

A little hammer? Greek t?

Front 66

What is the precedence for relational operators?

Back 66

1. Unary operators (select, project, rename)
2. Products and joins
3. Intersection
4. Union and set difference

Front 67

Union on bags does what with duplicate values?

Back 67

Adds the number of occurrences.

Front 68

Difference on bags does what with them?

Back 68

Subtracts the number of occurrences.

Front 69

Intersection on bags does what with them?

Back 69

Produces the minimum of the number of occurrences.

Front 70

What do selection and projection do to bags?

Back 70

Preserve the original number of duplicates.

Front 71

What do Cartesian product and join do to bags?

Back 71

No elimination of duplicates.

Front 72

What is an assertion?

Back 72

any SQL boolean expression

Front 73

What is a tuple-based constraint?

Back 73

relationship among components

Front 74

How is a foreign key specified?

Back 74

FOREIGN KEY (<list of attributes>) REFERENCES (<attributes>)

The referenced attributes must be declared primary key or unique.

Front 75

How can you enforce foreign-key restraints? (3 ways)

Back 75

Default: Reject modifications
Cascade: Make changes to all tuples with the key
Set NULL: For a changed key, set referencing tuples to NULL

Front 76

What is the syntax for foreign-key constraints?

Back 76

CREATE TABLE Sells (
bar CHAR(20),
beer CHAR(20),
price REAL,
FOREIGN KEY(beer)
REFERENCES Beers(name)
ON DELETE SET NULL
ON UPDATE CASCADE );

Front 77

What is the symbol for a single letter wild card in a like statement.

Back 77

_ (underscore)

Front 78

What are the 3 most common interpretations of NULL?

Back 78

Unknown
Inapplicable
Witheld

Front 79

The arithmetic result when NULL is an operands is always...

Back 79

NULL

Front 80

The boolean result when NULL in an operand is always...

Back 80

UNKNOWN

Front 81

How do you do boolean operations where a NULL is involved?

Back 81

AND is the Min
OR is the Max

Front 82

What are the 3 ways to interpret multi-relation queries?

Back 82

Nested loops
Parallel assignment
Conversion to relational algebra

Front 83

What is the SQL term for relational subtraction?

Back 83

EXCEPT

Front 84

What is the syntax for the 4 operators involving relations?

Back 84

EXISTS R
s IN R
s > ANY
s > ALL

Front 85

What do you call it when a subquery gets evaluated multiple times?

Back 85

Correlated subqueries

Front 86

How is EXCEPT used?

Back 86

SELECT *
FROM branch_book_list
WHERE branch_name = 'Branch A'
EXCEPT
SELECT *
FROM branch_book_list
WHERE branch_name = 'Branch B'

Front 87

What is the SQL for cartesian product?

Back 87

CROSS JOIN

Front 88

What is the SQL for an outerjoin?

Back 88

NATURAL FULL OUTER JOIN

Front 89

How would you tell the DBMS to use bags on a UNION instead of the default sets?

Back 89

UNION ALL

Front 90

How can you handle circular constraints?

Back 90

By deferring the constraint check by temporarily using NULLs.