What's in a Name?

Conversation 1.1 — The Database Before the Query

Modern Query ProcessingFall 2026

What's in a name?

Ada · 01

What is a database?

Alice

My first guess is software that stores and manages data on a computer.

Ada · 02

Keep that guess. What is data?

Alice

I use the word every day, but it is hard to say. Perhaps data is information stored on a computer.

Ada · 03

Suppose Rust evaluates this statement:

let road = ("Logan", "Salt Lake City");

Is this data?

Alice

The statement is code. The tuple value it produces can serve as data.

So data need not be a file sitting on a disk. It can also be a value used by a running program.

Ada · 04
type City = &'static str;
type Road = (City, City);

Is this data?

Alice

No. They describe shapes that data may have; neither line creates a value.

Optional feature conversation Would a quick review of Rust string literals help?
No Continue with the main conversation
Yes Open 2 short exchanges Review Rust string literals Open detour Close detour
Optional feature conversation R1 · Rust string literals
Ada · R1.1

What type does the string literal "Logan" have? Is it a String?

Alice

I would have guessed String, because it is a string.

Ada · R1.2

Rust gives a string literal such as "Logan" the type &'static str: a reference to text that remains valid for the entire program. An owned String is a different type.

Does "Logan" fit City as we defined it?

Alice

Yes. City is exactly that alias. We can postpone the rest of the lifetime story.

Ada · 05

Are these roads?

("Apple", "Salt Lake City");
("Apple", "Banana");
Alice

Neither. But each has the shape required by Road; Rust would accept either where a Road value is expected.

So Road distinguishes shape, not geography.

Ada · 06

Exactly. Road is a type. It describes a decidable property: whether a value has the required shape.

You can answer “yes” to whether a road exists by searching for a road in the world: if you find one, you have proved that it exists. But answering “no” to this question requires enumerating all roads in the world, which is not possible.

Therefore, this question is semi-decidable and cannot be captured by a type.

But being unable to say “no” does not mean that we cannot answer anything.

Alice

For a program that needs an answer now, we must keep track of the roads it is allowed to know:

use std::collections::HashSet;

let roads = HashSet::from([
    ("Logan", "Salt Lake City"),
    ("Salt Lake City", "Provo"),
]);

We surrender the grand question, “Is this a road?” and ask a smaller one: “According to what we have recorded, is this a road?”

Ada · 07

Let us call “what we have recorded” our world. Reading a question as “according to what we have recorded” uses the closed-world assumption. We will define these terms formally later.

Now, are these roads?

("Apple", "Salt Lake City");
("Apple", "Banana");
Alice

No. According to what we have recorded, they are not roads.

Ada · 08

Good. That was easy for you, but computer scientists also want to know whether this question is computable. Under the CWA, it is. How?

Alice

Perhaps with a named function:

fn is_road(
    roads: HashSet<Road>,
    road: Road,
) -> bool {
    roads.contains(&road)
}

Then I can ask:

is_road(
    roads,
    ("Logan", "Salt Lake City"),
)
Optional feature conversation Would a quick review of Rust borrowing help?
No Continue with the main conversation
Yes Open 6 short exchanges Review Rust borrowing Open detour Close detour
Optional feature conversation R2 · Rust borrowing
Ada · R2.1

Recreate roads, then ask the same question twice:

is_road(
    roads,
    ("Logan", "Salt Lake City"),
);
is_road(
    roads,
    ("Logan", "Salt Lake City"),
);
Alice

Ahhh—Rust rejects the second call. It says the first call moved roads.

Ada · R2.2

The compiler points to roads in the first call and says value moved here.

Did moving roads mutate the HashSet value, or did it only transfer who owns that value?

Alice

The move itself only transferred ownership; it did not change the members. Because this function does not return the set, Rust drops it when the call ends.

Ada · R2.3

A HashSet<Road> is not Copy. A parameter of type HashSet<Road> therefore takes ownership of the set passed to it. After the first call, the caller no longer owns the binding named roads.

But is_road only needs permission to inspect the set. What could it ask for instead of owning the set?

Alice

Perhaps a reference to the set.

Ada · R2.4

Yes. Replace only the first parameter:

fn is_road(
    roads: &HashSet<Road>,
    road: Road,
) -> bool {
    roads.contains(&road)
}

Can we keep the old call?

is_road(
    roads,
    ("Logan", "Salt Lake City"),
)
Alice

No. The function now expects &HashSet<Road>, so I need to pass &roads.

Ada · R2.5

Then can we ask twice this way?

is_road(
    &roads,
    ("Logan", "Salt Lake City"),
);
is_road(
    &roads,
    ("Logan", "Salt Lake City"),
);
Alice

Yes. Both calls compile, and the caller can still use roads afterward.

Ada · R2.6

Evaluating &roads borrows the stored set and produces a shared reference. The caller keeps ownership.

There is another reference inside the function:

roads.contains(&road)

Does &road borrow the stored set again?

Alice

No. This & is attached to road, not roads. It must refer to the candidate.

Ada · 09
is_road(&roads, ("Logan", "Provo"))

This is concrete Rust code, but scientists are lazy. When roads is understood, they abbreviate it as:

road("Logan", "Provo")

They call road—not Road—a relation, and is_road its membership predicate.

Alice

I am surprised they are not tired of writing:

HashSet::<Road>::from([
    ("Logan", "Salt Lake City"),
])
Ada · 10

They are. They write:

I(road) = {
    ("Logan", "Salt Lake City")
}

They call I(road) a relation instance of road. It is also the interpretation of the relation name road in I.

Alice

Neat. So I is something larger than the road relation alone.

Ada · 11

Yes. Before we give I a name, consider:

I0(road) = {
    ("Logan", "Salt Lake City"),
    ("Logan", "Salt Lake City")
}

Is I0(road) the same relation as I(road)?

Alice

Yes. The braces denote a set, just as our HashSet did. Duplicates do not count.

So a relation is mathematically a *set*.

Ada · 12
I1(road) = {
    ("Logan", "Salt Lake City"),
    ("Salt Lake City", "Logan")
}

Does I1(road) describe one road or two?

Alice

That depends on what road means. Are I-15 South and I-15 North the same road? If they are, I would say one; if not, two.

Ada · 13

Good. As a set, I1(road) contains two distinct tuples. Whether those tuples describe one physical road or two depends on their interpretation. We will study that distinction more deeply later.

Alice

Okay.

Ada · 14

Is

I2(road) = {
    ("Logan", "Salt Lake City"),
    ("Logan", 1, 2)
}

an instance of road?

Alice

No. There are two problems:

  1. 1 and 2 do not have type City.
  2. A road row supplies values for two attributes, not three.
Ada · 15

Right. Before giving an instance, we must declare the relation's name and its attributes. This is called its relation schema.

relation road(src: City, dst: City);

src and dst name the two attributes and state that both contain cities. The number of attributes is the relation's arity. We write attributes in an order so that positional row notation and query atoms have an unambiguous interface; the named schema identifies them by name.

Alice

I see. In Rust, we can represent rows in that declared order:

let road: HashSet<(City, City)> = HashSet::new();
Ada · 16

Good. Now it is your turn to write like a database researcher.

I want to record distances between cities in Utah. What relation schema and example relation instance should I use?

Alice
relation road_length(src: City, dst: City, miles: u32);

I(road_length) = {
    ("Logan", "Salt Lake City", 82)
}
Ada · 17

In Rust?

Alice
let road_length: HashSet<(City, City, u32)> = HashSet::from([
    ("Logan", "Salt Lake City", 82)
]);
Ada · 18

Now put the relations we care about, and one instance of each, together:

{
    relation road(src: City, dst: City);
    relation road_length(src: City, dst: City, miles: u32);
}
{
    I(road) = {
        ("Logan", "Salt Lake City"),
        ("Salt Lake City", "Provo")
    }
    I(road_length) = {
        ("Logan", "Salt Lake City", 82)
    }
}

We can now refine your earlier guess about a database.

Alice

A database!

Ada · 19

Is a database a piece of software?

Alice

No. These expressions describe organized data, including its schema and its current instance. The software that stores and manages that data must have another name.

Ada · 20

What have we described now?

Alice

We have described a database schema and one current database instance: the permitted shapes of its relations and the finite contents assigned to each one.

The DBMS is the software that would store and manage them. We have not yet given it a language for asking questions.

Recap

What the database is

Rust source text, Rust types, Rust values, and logical objects are distinct. Road names the required shape of one Rust row; a HashSet<Road> represents a finite set of such rows.

A declaration

relation r(A1: T1, ..., An: Tn);

specifies a relation name, distinct attribute names \(A_1,\ldots,A_n\), and the type of each attribute, but no current tuples. Its arity is \(n\). A tuple assigns each \(A_i\) a value from \(T_i\), and a relation instance is a finite set of such tuples. Positional row notation uses the declaration order as a shorthand; the logical attributes remain named.

A database schema is a finite collection of relation schemas with distinct relation names. A database instance \(I\) assigns each declared name \(r\) one matching relation instance, written \(I(r)\). Together, the schema and \(I\) describe the database at this logical level; a DBMS is the software that manages such data.