Final: Questions
[14 pts] The following two tables represent the history of presidents and the electoral college results for each election. The most recent five rows are listed for each.
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||
a. Write an SQL query to list the states that have produced presidents receiving at least 350 votes in the electoral college. Don't worry about duplicates.
b. Write an SQL query to list each president who served only one term.
[8 pts] Give an example of a relation for a job-management program (like the group project) that is not in BCNF. Explain specifically why your relation is not in BCNF.
[10 pts] For the relation R(a, b, c, d, e), convert the following FD basis to a minimal FD basis.
a b → a c e
a e → d
b c → a d
c → d e
[10 pts] Below is an entity-relationship diagram for tracking and discussing bug reports for a collection of software packages. Convert it into a corresponding set of relational schemas, underlining the primary-key attributes for each schema.
[8 pts] Programs normally store sorted data in a red-black tree (as with Java's TreeSet class) or some other form of balanced binary tree. Why is this approach unsuitable for database management systems to store their indexes (which leads to their using B+-trees instead)?
[8 pts] Suppose we have a database of customer orders, where we allow a customer to change the order up until the time it is shipped. Give an example where it would be helpful to use transactions to group multiple SQL queries together, explaining a circumstance where a failure to use transactions could lead to problems.
[8 pts] What distinguishes two-phase locking from a basic locking scheme?
[8 pts] After studying the standard DBMS logging techniques, Ben Bitdiddle proposes a much simpler technique avoiding any log: We do not save any changes by a transaction until the transaction is ready to complete, at which time we write all changes to disk as a package. Assuming that the implementation of Ben's technique ensures serializability, explain why ACID properties could be violated using Ben's scheme.
[8 pts] Suppose we are implementing a distributed database where many database elements are replicated across sites. To implement isolation, we use locks where each element's lock is maintained at each copy of that element. Any operation on the element requires acquiring locks from all copies of the element. What is a shortcoming of this technique, leading others to propose acquiring a simple majority of the locks instead?
[8 pts] Describe at least two features that distinguish an object-relational DBMS from a relational DBMS.
[10 pts] Without changing the HTML below, write a single CSS rule accomplishing each of the following.
<table>
<tr class="odd" id="first">
<td class="name">Washington<td>
<td class="year">1789</td>
</tr>
<tr class="even">
<td class="name">Adams<td>
<td class="year">1797</td>
</tr>
<tr class="odd">
<td class="name">Jefferson<td>
<td class="year">1801</td>
</tr>
<tr class="even">
<td class="name">Madison<td>
<td class="year">1809</td>
</tr>
<tr class="odd">
<td class="name">Monroe<td>
<td class="year">1817</td>
</tr>
</table>
a. Color the names only red.
b. Display every other year (1789, 1801, 1817)
in boldface. (Use font-weight: bold.)
[8 pts] Explain how AJAX-based sites differ from classical Web sites.
[8 pts] Consider the following Node.js code accessing a database.
db.all("SELECT passwd FROM users WHERE login = '" + req.body.login + "'", // rest omitted
Basic testing indicates that this works correctly. What is nonetheless wrong with it, and how can it be repaired?
[8 pts] Beth Bitdiddle reflects that writing a server-side program that does little more than accept AJAX requests and translate them to SQL seems like wasted effort. She suggests instead having the browser compose SQL, which the server would simply execute directly. Why is Beth's idea a bad one, though it is feasible and much simpler?
[8 pts] Explain the notion of templating in the context of Web development.
[8 pts] What are cookies in the HTTP protocol, and how does HTTP support them?
[10 pts] What does Memcached do, and how can it be used to reduce load on a database server in a setup with separate computers for the Web and database servers?
Final: Solutions
| a. | SELECT state |
| b. | SELECT name |
tickets(submitter_id, submitter_name, building, room, description)
The FD submitter_id → submitter_name would apply to this relation, since any two rows with the same submitter ID would also have the same name. But submitter_id is not a superkey for the relation: For example, a single submitter might submit two jobs concerning the same building. So this relation is not in BCNF.
a b → c
a e → d
c → d
c → e
bugs(project_name, id, description)
developers(login, alias)
assignments(login, project_name, id)
A node in a red-black tree has relatively little data, taking up far less than a block of disk storage. As a result, a lookup in the index will require reading many disk blocks to reach a leaf; by contrast, a B+-tree, which has a higher branching factor with each block, requires many fewer disk blocks to reach a leaf.
When a customer requests a change to an order, we would have to first check whether the order has already shipped using one SQL query before we execute an SQL query to make the change. These two queries need to be packaged as a transaction so that they happen together atomically. Otherwise, the first “check” query might indicate that the order has shipped but then the shipment might happen to be completed just in that instant before the “update” query is executed.
In two-phase locking, all locks requested by a transaction must be acquired before any locks are released.
The database system may crash (perhaps due to lost power) in the middle of writing the changes to disk. Ben's system provides no way to know which changes have taken place, so on reboot the transaction would have been only partially complete. Thus, the atomicity property of ACID is violated.
One shortcoming is that if any site is down, then all elements stored at that site are inaccessible, even if replicas exist at other sites, since no locks could be acquired for those elements. Also, requiring locks from all sites requires unnecessarily heavy communication. (And it can lead to another type of deadlock if one transaction happens to start getting its locks for an element from site A while another starts getting its locks for that same element from site B: Each is then preventing the other from acquiring all locks for the element.)
Here are three:
- Support for aggregate types like sets, lists, and structs.
- Methods can be associated with a row/object.
- References allow for direct references between tuples — essentially pointers, except that the tuples are actually stored on disk.
a. td.name { color: red }
b. tr.odd td.year { font-weight: bold }
In a classical Web site, information is only loaded from the server as the user navigates from one page to an entirely different page. In AJAX, by contrast, the JavaScript running as part of the page may request and receive information from the server “in the background” — without changing which page being displayed, though it may often change a portion of the displayed page upon receiving a response.
This is vulnerable to an SQL injection attack: One could
enter a login ID such as “'; DROP TABLE users --'”
to lead the program to execute some unintended SQL query — in
this example, to delete an entire table from the database.
Rather than build up a query using the JavaScript addition operator, one should tell the database module to insert the user-supplied value into the query. The database module will insert the appropriate escape characters so that special characters such as the quote will be treated just like quotes. The following code illustrates how this can be accomplished using the SQLite module.
db.all("SELECT passwd FROM users WHERE login = ?", [req.body.login], // rest omitted
Beth's idea is highly vulnerable to several security risks. First, a person might spoof requests containing SQL that acquires information that users should not be able to acquire directly. Or they might even send SQL that alters the database in inadvertent ways.
Templating allows one to develop the HTML generated from data in an HTML-like format, rather than by building up strings within a programming language.
A cookie is a piece of data that the server requests for the
browser to store; the server is written hoping that the browser
will send that same data back to the server on each
subsequent request. HTTP supports them by defining a
Set-Cookie header that a server may include in its
response to make its request, and the Cookie header
that a browser may include in each subsequent request.
Memcached stores a key-value mapping in memory, with the option of the mapping being distributed across multiple computers. It can reduce load on a database server by treating it like a cache: If we want to retrieve data from the database, we can instead first look into Memcached to see if the query's result is readily available, and we only go to the database server if it is not (and we store the result into Memcached so a subsequent query will hit the cache).