CSE 414 Notes

FROM with multiple tables does an implicit cartesian join. Partnered with a WHERE clause that's similar to an ON statement, it turns into something pretty close to an INNER JOIN.

Self-Join: Join on the same table multiple times. Useful when we want to filter on multiple other rows. Say, we want to find all users who have a friend named "Jane" and a friend named "Jack" – we need to join with the friends table twice, WHERE F1.name = "Jane" AND F2.name = "Jack"

Equi-join: A subset of inner joins where only equalities are in the ON clause. A non-equi-join: We want to find all passengers whose age is greater than the senior age limit for a certain set of airlines. So, FROM airlines JOIN people

MAX, MIN, AVG, SUM

Logically, aggregates take many values and return just one.

GROUP BY: Partition table into sections where the combination of the given columns is unique, compute aggregates, then concatenate again.

HAVING: Filters the "groups" created by GROUP BY

So, the order:

1. Partition/Group based on group by
2. Calculate having filters and remove invalid partitions
3. Calculate select filters and return

UNION, INTERSECT, and EXCEPT (set difference). Operate on two relations with identical schemas. The query to create the first relation appears immediately before the keyword and the query for the second after, with no parens. eg:

SELECT name
  FROM people
 WHERE age > 20
EXCEPT
SELECT name
  FROM people
 WHERE salary < 10000

Is roughly equivalent to:

SELECT name
  FROM people
 WHERE age > 20
   AND SALARY >= 10000

Like a long-term WITH statement; can be queried like a table but automatically updates with other tables. Views can be optionally stored/cached on disk, though you are making a delicate performance trade here.

One application: Improve data partitioning. Split up a table with many columns into multiple tables with the same primary key but fewer other columns, so that the database can store them in different places, but then access them using a view that joins everything together. It's possible to go even further ("horizontal" partitioning) and give all the sub-tables the same number of columns as the original, but simply store disjoint sets in each – for example, one might store customers with an id number ending in 0, then another with id ending in 1, etc, then the view joins with UNION. I imagine that many database systems can do this sort of partitioning automatically, which simplifies UPDATEs and INSERTs, because you can't generally do that on a view.

Another application: Access control – you can give a user access only to a table that aggregates other data for research purposes, for example.

CREATE VIEW ShortFlights
    SELECT *
      FROM Flights F
     WHERE actual_time < 180

The only way to do recursion in SQL. Although the syntax uses all keywords that we already know, these keywords don't really act the way we expect and recursive CTEs cannot be understood with non-recursive SQL. Here's a simple recursive query that generates the numbers less than 10:

WITH range_10 AS (
  SELECT 1 AS n
           UNION ALL
  SELECT n+1 AS n
    FROM range_10
   WHERE n < 10
)
SELECT * FROM range_10

Once again, it's very important not to interpret the recursive syntax the same way you would any other query, or to try and slot it in nicely alongside the SQL you already know. Here's how this query is run:

1. Execute the query to the left of the UNION ALL, and assign the results the name range_10.
2. Execute the query to the right of the UNION ALL. Assign the results of the query on the right side of the union (i.e, the one that was just executed), not including the previous results of range_10, to range_10.
3. Once the query to the right of UNION ALL returns the empty set, stop recursion. Union all the rows returned both from the anchor query (left of union) and every recursive call together into the final range_10.

Analyzing our range query:

The unintuitive thing here is that the intermediate range_10 bindings are very different than the final one.

Another example:

WITH F(a,b) AS (
     SELECT 0, 1
              UNION ALL
     SELECT b, a+b
       FROM F
      WHERE b < 100
)
SELECT a FROM F;

All subquery expressions can be written as non-subquery expressions where either:

• We create a temporary table, insert the results of a subquery into it, then reference that table from a second query.
• We perform a self join, then, in a loose sense, execute the subquery on the right half of the table. We create a copy of the table for each row in the table.

Option A is an "uncorrelated" subquery, obtion B is a "correlated" subquery; correlated subqueries are logically executed for every row being selected FROM in the parent clause.

When filtering with WHERE, we think of a "selectivity factor" – which percentage of the tuples will remain after the filter.

Specifically, we'll talk about inner equijoins. Let's name the common column `com`. There are a certain number of distinct values of `com`, `V(com)`. If one relation has a value of `com` that the other relation lacks, that value will not be present in the join output. So, we define the number of distinct values of `com` as `min(V(com<sub>a</sub>), V(com<sub>b</sub>))`. Now, for each value of `com`, we can calculate the number of rows as a cartesian join between the tables `T(A) * T(B)` followed by an AND selection between two equals, so a selectivity factor of `(1/V(com<sub>a</sub>) * 1/V(com<sub>b</sub>))`, meaning a cardinality of `T(A) * T(B) / (1/V(com<sub>a</sub>) * 1/V(com<sub>b</sub>)) * min(V(com<sub>a</sub>), V(com<sub>b</sub>))`, which can be simplified (we'll get to it).

Alternatively, let's start with all the rows of table A, or `T(A)`. For each row, we will match with `T(B)/V(B)` rows from the other table, so our output cardinality is `T(A) * T(B) / V(B)`

Connect two entity classes; are a subset of the cartesian joins of those two entity classes. Eg, if we have employee and company, all possible "works for" relationships are the cartesian join of employees and companies: Every employee works for every company. A subset of that is true: These employees work for those companies.

Relationships can have attributes and data beyond just the primary keys of their connected entity classes – eg, we might include a field saying how many hours per week each employee works for their company.

It also makes sense to have multiple relationships between the same classes.

A conflict is a relationship between two operations, whether from the same transaction or different ones, that states their order cannot be changed without breaking the conflict-serializability of the schedule. It's a bit like the elementary row operations in linear algebra: Two schedules are conflict-equivalent iff one can be turned into the other only by swapping around non-conflicting operations. Note here that conflict-equivalent means not only that it seems like one transaction occured completely before the other but that the same transaction occured first. Two different conflict-serializable schedules representing the same two transactions, but executed in opposite orders, cannot necessarily reach each other by swapping non-conflicting operations.

In short: Swapping non-conflicting operations produces a schedule that leaves the database in the exact same state as the original schedule would have.

W = Write, R = Read

Atomic

All or nothing.

Consistent

Conform to constraints, such as foreign keys or data types.

Isolated

Each transaction has the same effect it would have had if all transactions were executed serially.

Durable

Handles interruption gracefully.

A mechanism to categorically prevent conflicts! It's simply this: Whenever a transaction will do anything with a resource (read or write), it locks that resource. And, a transaction does not acquire any locks after it has released its first lock.

Can we prove this works?

If there are conflicting operations on the same element, obviously, all of those operations from one transaction will have to occur before the other, because a transaction does not release its lock on that element until it is completely done with it. So, we can simplify our model of each transaction down to a sequence of "operations", one per affected element. Eg, R₁(A), W₁(A), R₂(A) turns into O₁(A), O₂(A).

Now, we just have to make sure that O₁ operations are either all before or all after their corresponding operations from O₂. So, O₁(A), O₂(A), O₁(B), O₂(B) is OK, but O₁(A), O₂(A), O₂(B), O₁(B) is not.

Two transactions both operate on elements A..Z. For now, let's assume that both transactions lock all elements in the same order. Define transaction 1 as the transaction that acquires the lock on A before transaction 2. Well, transaction 2 can't lock A until transaction 1 has locked all of the elements, So, obviously A occurs first in 1. B was locked by transaction 1 before it released A, so B also occurs first in transaction 1. Etc.

What if the order of locking of A..Z differs between the transactions? Then a transaction can acquire some locks while the other acquires some other locks, until one transaction, transaction 1, tries to acquire a lock held by transaction 2. This might be a deadlock, which is outside the scope of this proof, but if it isn't a deadlock,

SQL: SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED

Indices are separate files on disk that sit alongside the main table. For a hash index, this separate file is a hash table mapping the index key to the on-disk location of the whole tuple in the main table file.

We model this not all that differently than a nested-loop join. We scan through one table, while seeking on the other table. This means the I/O estimation is not commutative: Depending on which table you scan on and which you seek on, performance could vary dramatically.

We scan R and seek on S, using attribute t. When we talk about V(some_table), we are referring to the number of unique values of the join attribute t. The I/O estimation formula will generally be B(R) + T(R)*{ seek I/O cost on S }. These seek costs come from the I/O lookup costs for different types of indices above, where the selectivity factor is 1/V(S) (selecting all tuples that match on the join attribute). If R was sorted, you could imagine that the T(R) term would become T(R)/V(R), because we could re-use the results of the last seek on S, but we don't make that assumption in 414.

A naïve database will fully materialize the output of each RA operator at every step of the tree, writing a temporary relation to disk before beginning the next operator up. Sometimes this is required: If we are going to sort the data, we may need access to the same tuple multiple times to perform multiple comparisons on it, or if we are performing a join where it is the secondary table, we need to repeatedly scan through the table for matching tuples. Much of the time, though, we can stream tuples through to the next RA operator.

For example: Filtering usually takes B(R) time. But we only need to look at each tuple once and don't care about tuple order or anything like that, so we can take tuples as they are released from the last operator and the cost of the filter is CPU-only — I/O cost is zero.

Another example — joins. Recall they are usually B(R)+T(R)*{seek cost on S}. We can't stream in S because we need to seek on it. But we can seek in R (and perhaps should restructure the physical plan to allow for that), and if so, the cost becomes just T(R)*{seek cost on S}.

Three steps for any query:

Disable auto commit, do your queries, commit explicitly, then re-enable auto commit (if you want that to be the default in your application):

conn.setAutoCommit(false);
conn.createStatement().executeQuery("SELECT UPDATE DELETE BLAH");
conn.createStatement.executeQuery("DELETE UR MOM");
conn.commit();
conn.setAutoCommit(true);

There's also a conn.rollback() method.

We still live in a world of tuples, but now the tuples are split up across machines. How do we decide which tuples to put where?

The most interesting big data operations are grouped aggregations. We:

1. Assign each group to a machine.
2. Get all the tuples to the machine they were assigned to (Shuffle)
3. Calculate the aggregate.
4. Union the aggregate results together on a single machine. This step is quick and trivial.

The shuffle step is the most expensive and usually involves hashing the grouped attributes, then range-partitioning on the hashes (just like a normal hash partition).

How do systems actually implement the aggregation and shuffling procedure described above? In two steps.

CREATE TYPE ClassType AS CLOSED {
    department: string,
    course_num: int,
    instructor: string?
}

Instructor is optional. Can DROP TYPE as well. If OPEN instead of CLOSED (or omitted), additional fields are allowed (like &allow-other-keys in Lisp).

• Arrays: [int]
• Multiset: {{string}}

Create a dataset:

CREATE DATASET Class(ClassType)
  PRIMARY KEY unique_id AUTOGENERATED;

AUTOGENERATED means "Add a UUID field with this name". You must always specify a primary key.

Types and datasets are specific to dataverses. You cannot create a dataset with a type from another dataverse. USE DataVerseName makes it the default dataverse, so we no longer need to put DataVerseName. before everything.

Let's say our data looks like:

{
  "name": "yoop",
  "orders": [
    { "product": "bopit", "price": 14 },
    { "product": "shakeit", "price": 21 },
  ]
}

And we want output that looks like:

{{
  { "name": "yoop", "product": "bopit" },
  { "name": "yoop", "product": "shakeit" }
}}

We can use this query:

SELECT P.name, O.product
  FROM People AS P, P.orders AS O;

Alternatively:

SELECT P.name, O.product
  FROM People AS P UNNEST P.orders AS O;

It's valid to think of this as a special type of join – join people with orders when the order is contained in people. There's no way to write this with INNER JOIN syntax, though, because there's no attribute to join on.

Say we have:

{{
    { "name": "Mark", "age": 19 },
    { "name": "Shana", "age": 38 },
    { "name": "Dan", "age": 19 },
    { "name": "Zander", "age": 17 },
    { "name": "Kari", "age": 17 },
}}

And we want to group by age:

{{
    { "age": 17,
      "people": [{ "name": "Zander" }, { "name": "Kari" }]},
    { "age": 19,
      "people": [{ "name": "Mark" }, { "name": "Dan" }]},
    { "age": 38,
      "people": [{ "name": "Shana" }]}
}}

We can do this:

SELECT P.age,
       (SELECT P1.name
          FROM People AS P1
         WHERE P1.age = P.age) AS people
  FROM People AS P;

Correlated subqueries are the name of the game!

Small issue: it yields this!

{ "age": 38, "people": [ { "name": "Shana" } ] }
{ "age": 17, "people": [ { "name": "Zander" }, { "name": "Karianna" } ] }
{ "age": 19, "people": [ { "name": "Dan" }, { "name": "Mark" } ] }
{ "age": 19, "people": [ { "name": "Dan" }, { "name": "Mark" } ] }
{ "age": 17, "people": [ { "name": "Zander" }, { "name": "Karianna" } ] }

Adding DISTINCT right after SELECT fixes it.

What if we want this instead?

{{
    { "age": 17, "people": [ "Zander", "Kari" ]},
    { "age": 19, "people": [ "Mark", "Dan" ]},
    { "age": 38, "people": [ "Shana" ]}
}}

We can use the VALUE keyword to not print out column names. It only works when selecting a single column.

SELECT DISTINCT P.age,
       (SELECT VALUE P1.name
          FROM People AS P1
         WHERE P1.age = P.age) AS people
  FROM People AS P;

A monotonic query preserves containment/subset relations between tables in its results. More explicitly, the tuples returned by the query will be a subset of the tuples returned by the query when the input relation is a superset of the original relation. It's a homomorphism: The Q (perform query) operation preserves subset relations.

Resilient Distributed Dataset