Databases

Question 1

Entity-relationship model

Answer 1

Graphical description of a database, represented in UML notation. An entity type is a group of objects with the same properties and independent existence. An entity occurrence is a uniquely identifiable instance of an entity type.

Question 2

Candidate and primary keys

Answer 2

A primary key is one which has been chosen to uniquely identify an entity occurrence, a candidate key is one that could.

Question 3

Simple and composite keys

Answer 3

A candidate key that consists of one attribute
A candidate key that consists of many attributes

Question 4

Advantages of EER model over ER

Answer 4

Avoids describing similar concepts more than once
Can have relations that include a subclass but not the superclass
More semantic information in the design (e.g. manager IS-A member of staff)

Question 5

How does the EER model work?

Answer 5

A subclass is a subgrouping of occurrences of an entity type, which need to be represented separately. A superclass is an entity type that has two or more distinct subclasses. Example: Staff contains Manager and Secretary.

All attributes of the superclass are also attributes of the subclasses, and a subclass has additional attributes than its superclass.

Question 6

Specialisation

Answer 6

Top-down process of maximising the differences between entity occurrences by identifying their distinguishing characteristics. Given superclasses, it leads to identifying subclasses.

Question 7

Generalisation

Answer 7

Bottom-up process of minimising the differences between entity occurrences, by identifying their common characteristics.

Question 8

Participation constraint

Answer 8

Determines whether every member in the superclass must participate as a member of one of the subclasses (either mandatory or optional)

Question 9

Disjoint constraint

Answer 9

Determines whether a member of a superclass can be a member of one or more subclasses (or=disjoint=only one subclass, and=non-disjoint=multiple subclasses)

Question 10

Structured data

Answer 10

This is data represented in a strict format, such as the relational data model. The database management system checks to ensure that the data follows the structures and referential constraints specified in the schema.

Question 11

Semi-structured data

Answer 11

This is data that may be irregular or incomplete and may have a structure that changes rapidly/unpredictably. It may have some structure, but not all parts may have the same structure and each data object can have different attributes that are not known in advance. We end up with such data when we collect data ad-hoc. Information that usually belongs to the schema is now mixed in with the data itself

Question 12

Advantages of XML

Answer 12

Simple standard, human-legible, extensible (can define own tags), platform-independent, separation of content and presentation (allows custom view of data), allows repeated attributes

Question 13

Well-formed XML

Answer 13

Well-formed: single root element, matching tags (properly nested), initial XML declaration including XML version number, encoding, and standalone status (DTD or no DTD)

Question 14

Type-valid XML

Answer 14

Well-formed and the elements must follow the pre-defined structure defined in the DTD.

Question 15

Schema-valid XML document

Answer 15

Must be well-formed and conforms to an XML schema

Question 16

DTD attribute syntax

Answer 16

<!ATTLIST BAR topic (sushi | sports) “sushi”>

This means that a BAR has an attribute “topic” which can either be “sushi” or “sports” but the default is sushi

Question 17

XQuery syntax

Answer 17

FOR $variableName in <XPath>
WHERE <condition>
RETURN {<expression>}</expression></condition></XPath>

Question 18

Write “doc(“bib.xml”)/bib/book[year > 1995]/title” in XQuery

Answer 18

FOR $x IN doc(“bib.xml”)/bib/book
WHERE $x/year > 1995
RETURN {$x/title}

Question 19

XQuery LET statement

Answer 19

Binds collection variables, meaning it returns one value consisting of a list of values (e.g. LET $S := /STAFFLIST/STAFF)

Question 20

XQuery for finding all books by the coauthors of the book “Database Theory”

Answer 20

FOR $x IN bib/book [title/text() = “Database Theory”] / author
$y IN bib/book [author/text() = $x] / title
RETURN <answer> { $y/text() } </answer>

Question 21

Existential qualifier

Answer 21

WHERE SOME $p IN <collection> SATISFIES <condition>
WHERE EVERY $p IN <collection> SATISFIES <condition></condition></collection></condition></collection>

Question 22

What is a transaction?

Answer 22

An action carried out by a single user/program which reads or updates the database

Question 23

What is referential integrity

Answer 23

A property of a database stating that all its references are valid according to the EER diagram

Question 24

What are the ACID properties of transactions?

Answer 24

Atomicity: a transaction is either performed entirely or not at all
Consistency: a transaction must transform the database from one consistent state to another
Isolation: Transactions execute independently (partial effects of incomplete transactions should not be visible to other transactions)
Durability: The effects of a committed transaction are permanently recorded

Question 25

What is concurrency control?

Answer 25

The process of managing simultaneous operations on the DB without having them interfere with each other

Question 26

What is the lost update problem?

Answer 26

An apparently successfully completed update operation by one user is overridden by another

Question 27

What is the uncommitted dependency problem?

Answer 27

A transaction is allowed to see the intermediate results of another transaction before it has committed

Question 28

What is the inconsistent analysis problem?

Answer 28

A transaction read some values while they are being updated by another transaction

Question 29

What is a schedule?

Answer 29

A sequence of operations from a set of n concurrent transactions such that the order of the operations in each transaction Ti is preserved in the schedule. A serial schedule is one where the operations of any two transactions are not interleaved (they all happen one after the other)

Question 30

How do we check whether a non-serial schedule is #conflict serialisable#?

Answer 30

Construct the precedence graph: a directed graph G = (N, E) with a set of nodes N and a set of directed edges E, with:

• A node for each transaction
• A directed edge from Ti to Tj whenever Tj reads a value of an item written by Ti, or Tj writes a value into an item after it has been read/written by Ti (Ti “pokes” Tj for reading something it wrote, or overwriting something it touched)

An edge from Ti to Tj means that in the equivalent serial schedule, Ti must appear before Tj

A schedule is serialisable if and only if there is no directed cycle in the precedence graph

Question 31

What does it mean if two schedules are view equivalent?

Answer 31

For each data item x, if transaction Ti reads the initial value of x in S1, then Ti reads the initial value of x also in S2

For each data item x, if the last write operation on x in S1 was done by Ti, then T1 also performs the last write operation on x in S2

For a read operation on data item x by transaction Ti in S1, if the value of x read by Ti was written by transaction Tk, then Ti must also read the value of x produced by Tj in S2.

First read, last write, if Ti reads a value written by Tj somewhere then it does everywhere

View equivalent schedules return the same results

Question 32

What does it mean if a schedule is view serialisable?

Answer 32

It’s view equivalent to a serial schedule, meaning that conflict serialisable implies view serialisable

Question 33

Conservative/pessimistic methods for concurrency control

Answer 33

Actively avoid conflicts, delay or restart transactions when they are in conflict.

Question 34

Optimistic methods for concurrency control

Answer 34

Assume that transactions are rarely in conflict, check for conflicts just before the transaction commits.

Question 35

Shared lock vs exclusive lock

Answer 35

Shared lock = transaction is only allowed to read some data item (not write), and any other transaction can also only read this item (not write)

Exclusive lock = transaction is allowed to read and write the same data item, while any other transaction has no access

Question 36

When does the DBMS grant a lock?

Answer 36

When either the item is not currently locked, or a shared lock is being requested on a share-locked item.

A transaction holds a lock until it explicitly releases it, either during its execution or when it terminates. The effects of a write operation are only made visible when the lock is released. Sometimes locks may be upgraded/downgraded.

Question 37

What is two-phase locking?

Answer 37

A system where for every transaction, there is a growing phase (acquire all needed locks, no unlocks), and shrinking phase (release all locks, no new locks). If we use this protocol, then the schedule will always be conflict serialisable. Problems can still occur if locks are released early.

Question 38

What is the cascading rollback problem?

Answer 38

Where a transaction T1 causes a failure and a rollback must be performed. Other transactions dependent on T1’s actions must also be rolled back.

Question 39

Rigorous and strict two-phase locking

Answer 39

Rigorous: we release all locks at the end of every transaction (when it commits), allowing us to serialise the transactions in the order they commit

Strict: the DBMS releases all write locks at the end of every transaction, but read locks can be released earlier.

Question 40

What is a deadlock?

Answer 40

A problem where two or more transactions wait for each other to give up locks

Question 41

Dealing with deadlocks

Answer 41

Timeouts: requests for locks time out after a maximum period of time, and then the transaction rolls back and restarts

Choosing the victim: it’s better to abort a short transaction, one which has made few changes, and one which doesn’t have much data left to update. This can lead to starvation (one process always being chosen as the victim). The common solution is to store how many times each transaction has been aborted, and then use different selection criteria when an upper limit is reached.

Question 42

Deadlock detection

Answer 42

Construct the wait-for graph G = (N, E), where the nodes N are the transactions and there is a directed edge from Ti to Tj when transaction Ti is waiting for a lock that is kept by transaction Tj (Ti pokes Tj to ask it to remove the lock)
A deadlock exists if and only if the wait-for graph contains a directed cycle. Once a deadlock is detected, the DBMS rolls back the transaction.

Question 43

Recoverable schedules

Answer 43

A recoverable schedule is one that ensures that once a transaction T is committed, it should never be necessary to roll it back.
A schedule S is recoverable if no transaction T commits unless all the transactions that it reads commit first.
And if Tj reads Ti then the commit operation of Ti appears before the commit operation of Tj.

Question 44

What does it mean when a transaction T “reads from” a transaction T’ in schedule S

Answer 44

Some data item x is first written by T’, and then read by T.

Question 45

When is a schedule cascadeless?

Answer 45

If Tj reads Ti then the commit operation of Ti appears before the read operation of Tj. Cascadeless implies recoverable.