Relational Databases

Draft Version 547 (Mon Dec 5 17:02:01 2005)

Flat text and XML both have their place, but most of the data people really care about is stored in relational databases
- Originated with E. F. Codd's work in the late 1960s and early 1970s
- By the 1980s, Oracle and IBM's DB2 dominated the market
- Open source alternatives like MySQL and PostgreSQL emerged in the 1990s
- SQLite offers a lightweight alternative for small jobs
  - Originally designed for use in small web sites
  - Stores entire database in a single file on disk (which simplifies backup and recovery)
The bad news: it's a huge topic
- Oracle's documentation would fill this room
  - No matter what room you're in
The good news: you only need to know a little to do most of the things you need to
- A few key ideas
- A little syntax
- [Fehily 2003] is a good tutorial and reference guide
When to use a relational database:
- Lots of data
- Mostly facts, rather than objects
  - I.e., not images, video clips, etc.
  - Although a database may be the best place to store information about these
- Complex queries
  - “Find all experiments done with the Mark VII that had yields greater than 30%, that didn't use cadmium disulfide as a reagant”
  - Relational database can answer these questions directly
Comment on this slide

Getting Started

A database is a collection of zero or more tables, each of which has a name, and represents a relation
- Basically, each table stores one kind of fact
Each table has a fixed set of named columns
- Like the fields in a form, or the members of an object
- All the values in a column have the same type
- Like XML attributes, values in a column shouldn't have any internal structure
  - I.e., you shouldn't have to parse them in order to use them
Each table has zero or more rows, each of which represents a separate record
- One or more values in each record form its key
- Unlike a dictionary, database doesn't guarantee uniqueness of keys: you have to
Example: experimental data
- Figure 21.1: Database Tables
- We'll use these tables as a running example
A foreign key is a value (or set of values) in one table that identifies a record in another
- For example, the values in the Login column in Involved identify records in the Person table
The example database illustrates an important rule of database design: no redundant information
- Natural to combine Experiment and Involved tables into one
- Figure 21.2: A Combined Table
- But now some information appears in two or more places…
- …which makes updates, consistency checks, and queries all harder to do
- Frequently have to make up attributes (like InvolvedId) to relate these tables
Comment on this slide

Basic SQL

Interact with database using a specialized language called SQL (Structured Query Language)
- Several versions have been standardized…
- …and every database adds its own quirks
To create a table, specify its name, and the names and types of its columns
- Should also specify whether values in that column can be null (i.e., undefined)
- ```
CREATE TABLE Person(
	Login		TEXT		NOT NULL,
	LastName	TEXT	        NOT NULL,
	FirstName	TEXT	        NOT NULL
);
```

To insert values into a table, specify the name of the tables, and the values to be inserted

Each INSERT creates a new row

INSERT INTO Person VALUES("skol",   "Kovalevskaya", "Sofia");
INSERT INTO Person VALUES("mlom",   "Lomonosov",    "Mikhail");
INSERT INTO Person VALUES("dmitri", "Mendeleev",    "Dmitri");
INSERT INTO Person VALUES("ivan",   "Pavlov",       "Ivan");

To erase a table, use DROP TABLE name
- Remember, back up early, back up often…
Usual way to run queries like this is to put them in a file, and give it to the database manager
- E.g., sqlite < make_running_example.sql
Most database managers also provide an interactive prompt, GUI tools, etc.
Comment on this slide

Simple Queries

Suppose we want to get the login IDs of everyone in the system, along with their names
- Write this query almost exactly as we just said it
- ```
SELECT Person.FirstName, Person.LastName, Person.Login FROM Person;
```
```
Sofia|Kovalevskaya|skol
Mikhail|Lomonosov|mlom
Dmitri|Mendeleev|dmitri
Ivan|Pavlov|ivan
```
- Exact output depends on your database manager
- Usually run it through a text filter, or view it in a GUI

How about sorting rows by login ID instead of by the order they were added to the database?

SELECT   Person.FirstName, Person.LastName, Person.Login
FROM     Person
ORDER BY Person.Login ASC;

Dmitri|Mendeleev|dmitri
Ivan|Pavlov|ivan
Mikhail|Lomonosov|mlom
Sofia|Kovalevskaya|skol

Note: SQL doesn't stick to single-word keywords (e.g., ORDER BY)

Comment on this slide

Joins

A join is a query that combines information from two (or more) tables
- Construct the cross product of the tables by combining each row of the first with each row of the second
- Discard rows that don't meet some criteria
- Select columns from the surviving rows

Example: find out who has done experiments for each project

SELECT Project.ProjectName, Involved.Login
FROM   Project, Involved
WHERE  Project.ProjectId = Involved.ProjectId;

Antigravity|mlom
Antigravity|mlom
Teleportation|dmitri
Teleportation|skol
Teleportation|ivan
Teleportation|mlom
Time Travel|skol
Time Travel|skol
Time Travel|ivan

Construct cross product of Person and Involved (which has 4×9=36 rows)
Throw away those for which the project IDs taken from the two tables don't match
Select the columns of interest
Figure 21.3: Join In Action

Note: mlom appears twice for the Antigravity project because he did two experiments for it

Use the DISTINCT keyword to eliminate duplicates

SELECT DISTINCT Project.ProjectName, Involved.Login
FROM   Project, Involved
WHERE  Project.ProjectId = Involved.ProjectId;

Antigravity|mlom
Teleportation|dmitri
Teleportation|skol
Teleportation|ivan
Teleportation|mlom
Time Travel|skol
Time Travel|ivan

How to find people who have done experiments for two (or more) projects?

First attempt: use AND

SELECT DISTINCT Person.Login
FROM            Person, Involved
WHERE           (ProjectId = 1214) AND (ProjectId = 1709);

Doesn't work because ProjectId cannot simultaneously be 1214 and 1709

Second attempt: use OR

SELECT DISTINCT Person.Login
FROM            Person, Involved
WHERE           (ProjectId = 1214) OR (ProjectId = 1709);

skol
mlom
dmitri
ivan

Doesn't work because every project's ID is either 1214 and 1709

Right solution that works is to join the Involved table with itself, so that we have two project IDs in the same row
- Then select rows where the person is the same, but the project IDs are different
- Remember, everything is done row-by-row
- ```
SELECT DISTINCT A.Login
FROM            Involved A, Involved B
WHERE           (A.Login = B.Login)
AND             (A.ProjectId != B.ProjectId);
```
```
mlom
skol
ivan
```
Comment on this slide

Negation and Nested Queries

How to find everyone who hasn't been experimenting with time travel?
- Can't just select rows of Involved where ProjectId is not 1737, since both Kovalevskaya and Pavlov have worked on other projects
- ```
SELECT DISTINCT Involved.Login
FROM            Involved
WHERE           (Involved.ProjectId != 1737);
```
```
mlom
dmitri
skol
ivan
```
Solution is counter-intuitive, but well-defined:
- Select the rows we don't want
- Subtract them from all possible rows

Requires use of nested queries

Database manager runs the inner query first, then applies the outer query to the inner query's result
NOT IN means exactly what it says

SELECT DISTINCT Login
FROM            Involved
WHERE           Login NOT IN
  (SELECT Login
   FROM   Involved
   WHERE  Involved.ProjectId = 1737);

mlom
dmitri

These are useful for many other things as well
- Example: how many people have done experiments for exactly one project?
- Solution: find the people who've done experiments for none, or for two or more, and subtract them from everyone
- ```
SELECT DISTINCT Login
FROM            Involved
WHERE           Login NOT IN
  (SELECT A.Login
   FROM Involved A, Involved B
   WHERE (A.Login = B.Login)
   AND   (A.ProjectId != B.ProjectId));
```
```
dmitri
```
Comment on this slide

Aggregation

Often need to aggregate (combine) values from different rows
- Total sales, fastest trip, etc.

SQL provides built-in functions

Example: how much time has Mikhail spent on antigravity experiments?

SELECT SUM(Experiment.Hours)
FROM Involved, Experiment
WHERE (Involved.Login = "mlom")
  AND (Involved.ProjectId = 1214)
  AND (Involved.ProjectId = Experiment.ProjectId)
  AND (Involved.ExperimentId = Experiment.ExperimentId);

15.8

How much time has each scientist spent on experiments?

Use GROUP BY to apply aggregation function to specific subsets of rows

SELECT Involved.Login, SUM(Experiment.Hours)
FROM     Involved, Experiment
WHERE    (Involved.ProjectId = Experiment.ProjectId)
  AND    (Involved.ExperimentId = Experiment.ExperimentId)
GROUP BY Involved.Login;

ivan|5.5
dmitri|7
skol|4.5
mlom|23

Note: negative hours on time travel experiments really mess up budgeting…

Comment on this slide

Using Other Languages

Usually don't write entire application in SQL, or run SQL in sub-shell
Instead, embed SQL in the programming language of your choice
- Visual Basic, Java, Perl, Python, …
- PHP was designed for exactly this purpose
Key concepts:
- A connection is a way to get commands from the program to the database, and results back
  - Typically a socket, but other methods are used as well
- A cursor is a pointer to a database operation
  - Like a cursor in an editor

Example: get the names of all the scientists into a Python program

import sqlite

connection = sqlite.connect("running.db")
cursor = connection.cursor()
cursor.execute("SELECT FirstName, LastName FROM Person;")
results = cursor.fetchall();
for r in results:
    print r
cursor.close();
connection.close();

('Sofia', 'Kovalevskaya')
('Mikhail', 'Lomonosov')
('Dmitri', 'Mendeleev')
('Ivan', 'Pavlov')

Need the right driver to connect to the database
Everything else (on the Python side) is the same, regardless of the kind of database
- Although as mentioned before, the SQL might be different

Comment on this slide

Handling Null Values

Real-world data always has holes in it
- Some people don't have cell phone numbers, some authors' birth dates are unknown…
Represent this in a database using the special value NULL
- Not the same as zero, empty string, False, etc.
- Instead, means “nothing known at all”
Check to see if a value is null using IS NULL
The result of any computation involving NULL is NULL
- 2 + NULL is NULL, NULL OR True is NULL, etc.
  - Although in some databases, False AND NULL is False, and True OR NULL is True

By default, columns may contain NULL, but this can be prohibited when the table is created

An example of an integrity constraint

CREATE TABLE Experiment(
	ProjectId	INTEGER		NOT NULL,
	ExperimentId	INTEGER		NOT NULL,
	NumInvolved	INTEGER		NOT NULL,
	ExperimentDate	DATE,
	Hours		REAL		NOT NULL
);

Have to write queries to account for NULL
- Experiment.ExperimentDate <> 1901-05-01 selects all experiments that weren't conducted on May 1, 1901, and all experiments whose date is NULL (since NULL isn't equal to anything except itself)
- Have to use (Experiment.ExperimentDate <> 1901-05-01) AND (Experiment.ExperimentDate IS NOT NULL)
Comment on this slide

Concurrency

The biggest challenge in database programming isn't formulated queries—it's handling concurrency
- Two or more things happening at once
- In the database world, one user changing the database while another is making a query
A related problem is the need to ensure atomic (or indivisible) operations
- Sequence of operations is “remove $100.00 from grant #19823”, then “add $100.00 to grant #17928”
- Don't want money to disappear if computer goes down in between
Solution to both problems is to use a transaction
- A set of operations which all work as if nothing else was going on, or have no effect on the database
- ACID:
  - Atomic: either all are performed, or none
  - Consistent: database is in a legal state when the transaction ends
  - Isolated: no operation outside the transaction sees the database in any intermediate state
  - Durable: once the user is notified that the operation has completed, its effects are permanent

Transactions sometimes used for queries, but should always be used for updates

Example: change Kovalevskaya's login ID from "skol" to "kovalev"

BEGIN TRANSACTION;

  UPDATE Person
  SET    Login = "kovalev"
  WHERE  Login = "skol";

  UPDATE Involved
  SET    Login = "kovalev"
  WHERE  Login = "skol";

END TRANSACTION;

SELECT *
FROM   Person
WHERE  (Login = "kovalev") OR (Login = "skol");

SELECT *
FROM   Involved
WHERE  (Login = "kovalev") OR (Login = "skol");

kovalev|Kovalevskaya|Sofia
1709|1|2|kovalev
1737|1|1|kovalev
1737|2|1|kovalev

Wrap the changes in a transaction so that:
- No query can run after Person changes, but before Involved changes
- If database goes down in the middle of the operation, database doesn't become inconsistent

So why not use transactions everywhere?
- Because they require the database to serialize some operations
- Which slows the system down
Comment on this slide