Databasteknik C: Solutions to the exam 2002-01-18

These are suggested solutions. There may be other correct solutions. Some of these answers may be more exhaustive than required for full points on the exam.

Problem 1

a)

_{snr, snamn} [ ( _{knamn = "Databasteknik C"} (kurs) _{knr = kurs} godkänd ) _{student = snr} student ]

Comment: Since snr is primary key in student, and knr is primary key in kurs, and reference attributes refer to primary keys, we know that the attributes student and kurs in godkänd are numbers and not names.

b)

L _{snr, snamn} [ ( _{knamn = "Databasteknik C"} (kurs) _{knr = kurs} läser ) _{student = snr} student ]

G _{snr, snamn} [ ( _{knamn = "C++"} (kurs) _{knr = kurs} godkänd ) _{student = snr} student ]

Result L - G

c)

_{snr, snamn}F_count(*) ( student _{snr = student} läser )

d)

_{snr, snamn}F_count(kurs) ( student _{snr = student} läser )

e)

EK _knr ( _{inamn = "Elektromekanik"} (kurs) _{inr = institution}kurs )

SK _{snr, snamn, kurs} ( student _{snr = student} läser )

Result SK / [ _(kurs)(EK) ]

Problem 1

a)

PROJECT_{snr, snamn} [ ( SELECT_{knamn = "Databasteknik C"} (kurs) JOIN_{knr = kurs} godkänd ) JOIN_{student = snr} student ]

b)

L <- PROJECT_{snr, snamn} [ ( SELECT_{knamn = "Databasteknik C"} (kurs) JOIN_{knr = kurs} läser ) JOIN_{student = snr} student ]

G <- PROJECT_{snr, snamn} [ ( SELECT_{knamn = "C++"} (kurs) JOIN_{knr = kurs} godkänd ) JOIN_{student = snr} student ]

Result <- L - G

c)

_{snr, snamn}F_count(*) ( student JOIN_{snr = student} läser )

d)

_{snr, snamn}F_count(kurs) ( student LEFT OUTER JOIN_{snr = student} läser )

e)

EK <- PROJECT_knr ( SELECT_{inamn = "Elektromekanik"} (kurs) JOIN_{inr = institution}kurs )

SK <- PROJECT_{snr, snamn, kurs} ( student JOIN_{snr = student} läser )

Result <- SK DIVISION [ RENAME_(kurs)(EK) ]

Problem 2

_{snr, snamn snr = student and kurs = knr and institution = inr and inamn = "Vårdmatematik"} (student kurs institution läser)

b) c)

• Push down select operations (i. e. do them earlier in the query)
• Apply the most selective selects first
• Combine selects with cartesian products to form joins
• Push down projects

Problem 3

The optimizer can be exhaustive, and examine all possible (and reasonable) execution plans, and thus always find the cheapest solution. It can also be non-exhaustive, and just examine a subset, which could be randomly chosen, but usually according to some optimization algorithm such as hill climbing.

The cost function must take into account the actual or estimated size of the data. A heuristic query optimizer (of the type covered in this course) only creates an execution plan by applying some genereal rules, such as "select operations should be performed as early as possible". Such an heuristic query optimizer has no way of knowing, e. g., if the table student is much larger than the table institution, which can be important to know when choosing a good execution plan.

A cost-based query optimizer can also compare the cost of different algorithms for join and select operations, and also take physical storage structures into account.

Problem 4

ODBC is a call-level interface, where you write SQL queries as strings in procedure calls, while ESQL attempts to integrate SQL with the host language. In ESQL, the embedded SQL queries are translated to procedure calls (similar to those in ODBC) by a pre-processor. You have to write more code in ODBC.

ODBC is available for more DBMSs than ESQL. ODBC is also more flexible: an ODBC program can talk to several databases, of the same or of different types of DBMSs, simultaneously. This is difficult to do in ESQL. You can change the databases, or types of DBMSs, that an ODBC program talks to, without re-compiling or even re-linking the program.

Problem 5

b)

knr -> knamn
knr -> institution

c) 1NF

d) Problems due to low normalization:

• Redundancy: The two facts that course number 42 is called Heuristic spoon-bending, and that it belongs to department number 17, is repeated for every student that takes the course. This makes updates difficult, and can lead to inconsistencies.
• You can't store a course in this database unless you have students enrolled in that course. This leads to insertion and removal anomalies: if you want to insert a new course, with no students so far, you can't, and if you remove the last student from a course, all information about the course disappears.
• (Perhaps also: Complicated semantics: What does this table really mean?)

Problem 6

b) None.

c)

student -> läser_kurs
student -> godkänd_kurs

d) BCNF

e) Problems due to low normalization:

• Redundancy: The fact that student number 4711 follows course number 42 has to be repeated for each course that student has passed. Also, the fact that student number 4711 has passed course number 17 has to be repeated for each course that student follows.
• It is difficult for a student to follow a course unless he or she has already passed at least one other course. What value would you put in the "godkänd_kurs" field? It is also difficult for a student to be registered as having passed a course unless he or she is following at least one other course.
• (Perhaps also: Complicated semantics: What does this table really mean?)

Problem 7

An object-oriented DBMS, sometimes called a "first-generation object-oriented" DBMS, is an object-oriented programming language (typically C++, Java or Smalltalk) with database functionality (such as persistence and some transaction functionality) added. There is no declarative query language (but OQL, an object query language, has been proposed), and the programmer has to navigate through the database with pointers, similar to any C++ program.

An object-relational DBMS, or "second-generation object-oriented" DBMS, is a DBMS with object-oriented functionality (such as inheritance). It has extensive database functionality, such as a query language, views, and advanced transaction management. Some object-relational DBMSs are relational DBMSs, with some rather limited object-oriented functionality added. This has nothing (or at least very little) to do with the Entity/Relationship model.

Object-oriented databases are suitable for applications with few, complicated transactions on few, complicated data, such as CAD systems. They can be very efficient, but unsafe, when working with checked-out data in the application's memory space. Long transactions (lasting hours or days) may be better handled by object-oriented databases, and chek-in/check-out transactions.

Similar to relational databases, object-relational databases are more suited for applications with many simple transactions on many simple data. Due to the declarative query language, object-relational databases have better data independence, making them suitable for applications where the schema changes frequently. If all you want is persistent storage for the objects in your object-oriented program, then an object-relational DBMS is probably overkill, and therefore inefficient.

Problem 8

• Attributes that are used often in join and select operations are candidates for indexes.
• Attributes with low selectivity are usually not suitable for indexes. (Keys, which always have the best possible selectivity, are often good candidates for indexes.)
• Very large attributes (i. e. many bytes) may not be suitable for indexes.
• Things that change frequently may not be suitable for indexes.
• Queries with time reuirements, or time limits, may require certain attention.
• Very small tables (i. e. few data blocks) may not require indexes.

Problem 9

None of the specified indexes can be used in the question. We assume the most efficient execution of this query, which means that we first read the table institution sequentially to find the row for the department "Vårdelektronik", and then we use the department number "inr" when sequentially reading through the table kurs.

The numerical calculations in this problem are allowed to be very approximative.

Some reasonable assumptions:

• Block size: 1024 bytes.
• Time to read a block, sequentially: 1 ms.
• Record size in the table institution: 100 bytes.
• Record size in the table kurs: 50 bytes.

Answer: 0.5 seconds, in both a and b.

Problem 10

Strict two-phase locking prevents cascadings rollbacks. A cascading rollback happens when the rollback of a transaction forces another, unrelated, transaction to be rolled back too. This happens if a transaction, T1, has written a data object, X, and then released its lock on X before T1 has committed. Another transaction, T2, may then read X. If T1 is aborted after T2's read, and the roll-back changes X back to the old value, T2, that depends on the value written by T1, is now invalid and has to be rolled back.

Problem 11

When the DBMS re-starts after a crash, we have two things: the data on the hard disk (called the materialized database), and the log file. The log file contains both committed transactions (with a commit record written in the log file) and uncommitted transactions (without a commit record written in the log file). Both committed and uncommitted transcations may hava made changes in the materialized database (if we assume immediate update). Not all changes, even from the committed transactions, are guaranteed to actually have made it into the materialized database.

To ensure durability, all write operations from all committed transactions must be re-done. Those write operations can be found in the log file.

To ensure atomicity, all write operations from all uncommitted transactions must be un-done. (Not needed if deferred update is used.) Those write operations can be found in the log file.

During recovery, it is only necessary to re-do and un-do write operations from after the last checkpoint.

After a disk crash, when there is no materialized database, the database is restored from backup, and then all committed transactions from the entire log file (from the time of the back-up) have to be re-done.

Problem 12

b) XML, the Extensible Markup Language, is a data representation format that looks a bit like HTML. It can be used on the web, or in other places where data needs to be stored or communicated.

c) A k-d tree is a type of two-dimensional index. It is a binary tree, where the levels in the tree alternate between two dimensions. The root node in the tree could, for example, split a map along the x axis, the nodes in the second level split the map along the y axis, the nodes in the third level split the map again along the x axis, and so on. There are variants of k-d trees that are based on B-trees instead of binary trees.

d) CORBA, the Common Object Request Broker Architecture. A standard for communication between object-oriented applications, letting them communicate across a network, independent of operating system, programming language, and the type of network.

e) RAID, Redundant Array of Independent Disks. We let several physical hard disks work in parallell, combining them into one "logical" hard disk. There are several types of RAID, and depending on which one we use we can increase either data transfer rate (through data striping), or security agains disk crashes (through various types of redundancy), or both.

Problem 13

CGI scripts are inefficient. Starting a new, separate program takes a long time on a computer. Also, if the CGI-generated web page contains output from a database, the CGI-script must open a new connection and log in on the database server, and this has to be done every time the web page is requested.

The alternative is to let the web server itself connect to the database, without starting a separate program. An example of this is Roxen Webserver, which lets you embed SQL statements in normal HTML or XML web pages. The web server then sends the SQL query to the database, and inserts the output from the query in the web page.

This can be more efficient than CGI scripts, since we don't have to launch a separate program. Also, the web server can keep the connection to the database server open, and re-use the same session for all queries.

Problem 14

b) student = S₁ S₂ S₃

c)

select knr, knamn
from student, läser, stad
where stad = 'Östersund'
and snr = student
and kurs = knr

_{knr, knamn} [ _{stad = "Östersund"}(student) _{snr = student} läser _{kurs = knr} kurs ]

e)

_{knr, knamn} [ _{stad = "Östersund"}( S₁ S₂ S₃ ) _{snr = student} läser _{kurs = knr} kurs ]

f)

Since no students from Östersund will be present in fragments S₁ and S₃, we can reduce them from the expression, and since no students other than from Östersund will be present in fragment S₂, we don't need the select operation:

_{knr, knamn} [ S_{1 snr = student} läser _{kurs = knr} kurs ]