Core CS · DBMS

A relation is a set, and the rest follows

Four properties, four words of vocabulary, and one pair of numbers that half a room gets backwards under pressure. You will read both numbers off one four-column table, then watch five operations land differently on a relation and on the SQL table pretending to be one.

Run five operations against a relation, then against a table →

A relation is a set of tuples over named attributes. Every property you will be asked to list is that one sentence unpacked: no duplicates, no order, no opening a value up, and two numbers that count two different things.

01 The idea

Codd threw away the pointers

In 1970 Edgar Codd published A Relational Model of Data for Large Shared Data Banks. The systems of the day stored records as chains: to reach a student’s marks you followed a pointer from the student record to the marks record, and your program had to know that the chain existed and which direction it ran. Change the storage layout and every program broke. Codd’s proposal was that data should be presented to the user as nothing but tables of values, with no pointer and no access path visible anywhere, so that a program asks for data by what it is rather than by where it sits.

One of those tables is a relation. It has a fixed list of named columns, each called an attribute, and each attribute draws its values from a domain, which is the pool of values that attribute is allowed to hold. One row is a tuple: exactly one value from each attribute’s domain. That is the whole vocabulary, and none of it mentions files, pages, order or pointers.

The load-bearing word is set. A relation is not a list of tuples, it is a set of them, and mathematics has already decided what that means: a set holds each member once, a set has no first member, and adding a member the set already has changes nothing. Three of the four properties you will be asked to list are not extra rules at all. They are what the word set already said. The fourth, that a value cannot be opened up, comes from a tuple holding one member of one domain per attribute.

Degree is a property of the schema and cardinality is a property of the instance. An INSERT moves cardinality and never degree; an ALTER TABLE ADD COLUMN moves degree and never cardinality. If you can say which statement moves which number, you cannot get the pair the wrong way round.

RelationA set of tuples over one fixed list of named attributes. One relation is what SQL shows you as one table, and the word set is doing all the work in that sentence.

DomainThe pool of values one attribute may draw from. Marks draw from the integers 0 to 100; a city draws from the names of cities. A value outside the domain is not a legal value, whatever the column type happens to accept.

TupleOne row: exactly one value from each attribute’s domain, reached by attribute name rather than by position. No two tuples of a relation can be identical, because the relation is a set.

02 Worked example

One tiny table, and the two numbers you read off it

Three students. Four columns. This is the table for the rest of the lesson, including the console, so it is worth ten seconds of looking at rather than scrolling past.

sid	name	city	marks
S1	Asha	Pune	78
S2	Ravi	Delhi	65
S3	Meera	Pune	82

Four attributes, so the degree is 4. Three tuples, so the cardinality is 3. Those two numbers came from two different places, and the notation below puts them side by side so you can see where each one was read.

-- relation schema · the names and their domains. Degree is read off here.STUDENT( sid   : CHAR(2),         name  : VARCHAR(30),         city  : VARCHAR(30),         marks : INT 0..100 )              -- 4 attributes  =>  degree 4 -- relation instance · the set of tuples right now. Cardinality is read off here.STUDENT = { (S1, Asha,  Pune,  78),            (S2, Ravi,  Delhi, 65),            (S3, Meera, Pune,  82) }       -- 3 tuples  =>  cardinality 3 -- braces, not brackets. Members of a set, not items in a list.

Now the keys, because this is where sloppy material does the most damage. Look at sid: it holds S1, S2, S3, and no two tuples share a value, so no two tuples can be confused. A set of attributes whose values are unique in every legal instance is a superkey. So {sid} is a superkey, and you cannot make it any smaller without emptying it, so it is also a candidate key, which is the name for a superkey that is minimal.

Add a column to it. {sid, name} is still unique, so it is still a superkey. It is not a candidate key, because dropping name leaves {sid}, which still identifies a row. That single word, minimal, is the entire difference between the two terms, and it is the clause candidates leave out. If sid is the only uniqueness the schema declares, then a set of attributes is a superkey exactly when it contains sid, and there are three other attributes, so there are 2³ = 8 superkeys and exactly one candidate key. The primary key is sid because the designer picked that one and declared it.

Then look at name. Asha, Ravi and Meera are three different values as well. That does not make name a superkey. A key is a rule about every legal instance of the schema, not an observation about the three rows in front of you, and the fourth student the college admits may perfectly well be another Asha. Sample rows can disprove a key by showing you a repeat. They can never prove one.

1 · Domainthe pool an attribute may draw from: city from city names, marks from 0 to 100

→

2 · Attributea name attached to one domain. There are four here, which is where the degree comes from

→

3 · Tupleone value from each attribute’s domain, reached by name: (S1, Asha, Pune, 78)

→

4 · Relation instancethe set of tuples at this moment. Three of them, which is where the cardinality comes from

→

5 · Relation schemathe name, the attributes and their domains. Every INSERT in the lesson leaves this untouched

Read node 2 and node 4 again, because they are the answer to the question that gets asked. Degree is counted on the schema side of that picture and cardinality on the instance side. Students swap them under pressure because both are taught as “a number about the table”, and they are not: they are numbers about two different objects, and only one of them moves when you insert a row.

Everything in the next section is a consequence of node 4 being a set and node 3 being a mapping from names rather than positions.

03 Mechanics

Four properties, and the two a SQL table gives up

One row per property. The third column is the one worth memorising, because it says why rather than what, and the fourth is the one that turns this from definition-recall into an answer: a real SQL table does not obey all four, and an interviewer who asks “is a table a relation” is asking exactly this column.

Property	What it forbids	Why the model says so	Does a real SQL table obey it?
1 · No duplicate tuples	two rows identical in every attribute	A relation is a set, and a set holds each member once. Inserting a tuple it already has is not an error, it is a no-op.	`No. With no PRIMARY KEY and no UNIQUE constraint, the same row goes in twice and COUNT(*) counts both`
2 · Tuples are unordered	the phrase “the third row”	A set has no first member and no last one, so no tuple has a position to be referred to by.	`Yes. No stored row order is promised; ORDER BY sorts the result handed back, it does not order the table`
3 · Attributes are unordered	the phrase “the second column”	A tuple maps attribute names to values. A name is how you reach a value, so position carries no meaning.	`No. SELECT * returns declaration order, and INSERT ... VALUES matches columns by position`
4 · Every value is atomic	a list, a repeating group or a nested table inside one cell	An attribute value is one member of one domain. A comma-separated pair is not a member of the domain of cities.	`Only by convention. The rule is first normal form, but SQL:1999 added ARRAY, and PostgreSQL arrays, JSONB and composite types put structure in a cell on purpose`

Property 4 is worth one extra sentence, because it is the one people treat as tidiness. It is not. The moment a cell holds a list, every operator stops working on that column: WHERE city = 'Mumbai' misses the row, GROUP BY city groups on a string nobody chose, and a join on it matches nothing. Atomicity is what keeps the algebra usable. A relation satisfies first normal form by construction, which is why 1NF is the one normal form you never have to test for in the model and always have to watch for in the product.

Now the two numbers, under the operations that move them. Amber marks the number that changed. Every row below starts from our three-student table, and every result is countable by hand from the rows in section 02. Read the first four rows as the numbers for STUDENT itself, because INSERT, DELETE and ALTER TABLE change the stored table. Read the last three as the numbers for the result: a query returns a new relation and leaves STUDENT exactly as it was.

Operation on STUDENT	Degree after	Cardinality after
INSERT one new student	`4, unchanged`	`3 → 4`
DELETE one student	`4, unchanged`	`3 → 2`
ALTER TABLE ADD COLUMN phone	`4 → 5`	`3, unchanged`
ALTER TABLE DROP COLUMN marks	`4 → 3`	`3, unchanged`
SELECT sid, name FROM student	`4 → 2`	`3, unchanged`
SELECT city FROM student	`4 → 1`	`3 rows back, but only 2 distinct tuples`
SELECT DISTINCT city FROM student	`4 → 1`	`3 → 2`

The last two rows are the whole SQL-is-not-a-relation argument in miniature. Our cities are Pune, Delhi, Pune. Projected onto city, the relational answer is the set {Pune, Delhi}, cardinality 2. SELECT city FROM student hands you three rows, because SQL evaluates over multisets, also called bags, where a member can appear more than once. DISTINCT exists as a keyword precisely to buy the set back, and it is not free: the server has to sort or hash the result to find the repeats.

A SQL table is a bag of rows with ordered, named columns. That is not a criticism of SQL, which chose duplicates deliberately so that a projection would not have to deduplicate on every query. It is the gap you are being asked about, and the whole of it is closable inside the schema you write.

05 Cheat sheet

Twelve rows, one table, no guessing

Every term defined against the same three students, so nothing here is abstract. The right-hand column is what you would say if an interviewer put our table on a whiteboard and pointed at it.

Term	What it is	In our STUDENT table
Relation	a set of tuples over one schema	`STUDENT`
Tuple	one row: one value per attribute	`(S1, Asha, Pune, 78)`
Attribute	a named column bound to one domain	`city`
Domain	the set of legal values for an attribute	`marks: the integers 0 to 100`
Degree	the number of attributes, read off the schema	`4`
Cardinality	the number of tuples, read off the instance	`3`
Relation schema	name, attributes, domains; moves only on DDL	`STUDENT(sid, name, city, marks)`
Relation instance	the set of tuples right now; moves on every write	`the three rows above`
Superkey	any attribute set unique in every legal instance	`{sid}, {sid,name}, {sid,city}, ... 8 in all`
Candidate key	a minimal superkey: drop one attribute and uniqueness goes	`{sid}, and nothing else`
Primary key	the one candidate key the designer declares	`sid`
Cartesian product	degrees add, cardinalities multiply	`R(m attrs, x tuples) x S(n, y) => degree m+n, cardinality x*y`

Degree is schema, cardinality is instanceThis is the line that stops the swap, and it is testable rather than mnemonic. INSERT and DELETE move cardinality and never degree; ALTER TABLE ADD COLUMN moves degree and never cardinality. Name the statement and the number follows.

An instance can disprove a key, never prove onename is unique across our three rows and that tells you nothing at all, because a key is a constraint on every legal instance. Interviewers hand you four sample rows and wait to see whether you declare a candidate key from them. The right move is to ask whether two students are allowed the same name.

The three key words are nested, not parallelEvery candidate key is a superkey; the primary key is one chosen candidate key. Minimality is the only thing separating the first two. {sid, name} identifies a row so it is a superkey, but dropping name leaves something that still works, so it is not a candidate key.

06 Where & why

Where the gap between table and relation is visible

None of this is theory you meet only on a question paper. Each of these four systems exposes degree, cardinality or one of the four properties somewhere you can type at it, and in every case the exposure is a small betrayal of the model.

PostgreSQL

Degree is exact, cardinality is a guess

pg_class.relnatts holds the attribute count, so the degree of a table is a lookup. pg_class.reltuples holds a row-count estimate that VACUUM and ANALYZE refresh and the planner trusts; it is not a live count, and SELECT COUNT(*) is the only exact answer. That asymmetry is the schema-versus-instance split showing through the catalogue: one number is declared, the other has to be counted.

MySQL

Column order is real enough to move

ALTER TABLE student MODIFY COLUMN marks INT AFTER name repositions a column, which is a statement that could not mean anything if attribute order were immaterial. PostgreSQL has no equivalent. Separately, an InnoDB table with no primary key and no non-null unique index gets a hidden six-byte row id of its own, so duplicate rows are stored happily and are internally distinguishable while remaining identical to every query you can write.

SQLite

Every row has a secret identity

An ordinary SQLite table carries an implicit rowid, so two textually identical rows are still separate objects with separate addresses. SQLite also uses type affinity rather than strict types, so a value that does not belong to a column’s domain is stored anyway rather than rejected. Both of those are convenient and both of them are the storage engine disagreeing with the model about what a tuple is.

Oracle

A domain with a hole in it

SELECT COUNT(*) FROM user_tab_columns WHERE table_name = 'STUDENT' reads a degree off a live schema, and USER_TABLES.NUM_ROWS is a stale statistic exactly like PostgreSQL’s. The wrinkle worth naming is that Oracle stores an empty VARCHAR2 string as NULL, so the domain of an Oracle string column contains no empty string. No other mainstream database does this, and code ported to Oracle finds it the hard way.

The relational model is not what any of these products hands you by default. It is what you get back when you use the product deliberately, and every gap this lesson found between the model and the table is a gap you close somewhere in your own schema.

07 Interview questions

What they actually ask

This is the opening minute of most DBMS interviews, and it is where a candidate either sounds like they have used a database or like they have highlighted a chapter. The difference is almost always whether the definitions arrive with a reason attached.

What is a relation, in one sentence?

A set of tuples over a fixed list of named attributes, where each attribute draws its values from a domain. The word set carries three of the four properties on its own: no duplicate tuples, no order among them, and inserting a tuple that is already there changes nothing. The fourth, that every value is atomic, comes from a tuple holding one member of one domain per attribute.

Degree and cardinality. Which is which?

Degree is the number of attributes and cardinality is the number of tuples. STUDENT(sid, name, city, marks) with three rows has degree 4 and cardinality 3. The way to stop swapping them is to notice where each is read: degree comes off the schema and only a DDL statement moves it, cardinality comes off the instance and every INSERT and DELETE moves it.

What is the difference between a relation schema and a relation instance?

The schema is the relation’s name plus its attributes and their domains; the instance is the set of tuples in it at one moment. The schema is written once and changes only when you run DDL; the instance changes on every committed write. That is also why a question about degree has one answer and a question about cardinality quietly has a timestamp attached to it.

Name the properties that make a relation a relation.

No duplicate tuples, no ordering of tuples, no ordering of attributes, and every value atomic. The first two follow from a relation being a set. The third follows from a tuple mapping attribute names to values rather than holding a numbered list. The fourth is first normal form, which a relation therefore satisfies by construction rather than by passing a test.

Why does the model insist that values are atomic?

Because an attribute value is defined as one member of one domain, so ‘Pune, Mumbai’ is not a legal city. The practical reason is stronger than the definitional one: once a cell holds a list, every operator stops working on that column. WHERE city = ‘Mumbai’ misses the row, GROUP BY city groups on a string nobody chose, and a join on it matches nothing. Atomicity is what keeps the algebra usable.

Is a SQL table a relation?

Not strictly. A SQL table is a bag of rows with ordered, named columns: with no primary key and no unique constraint it will hold the same row twice, and its column order is observable through SELECT * and through positional INSERT. It does agree with the model on row order, since nothing is promised without ORDER BY. Declare a key and always name your columns and the table behaves like a relation.

Our table has cities Pune, Delhi, Pune. What does SELECT city FROM student return, and does that break the model?

Three values, two of them the same, and it shows that SQL evaluates over multisets rather than sets. The relational projection onto city is the set {Pune, Delhi}, cardinality 2, but SELECT does not deduplicate. SELECT DISTINCT city is the operation that gives you the relational answer, and that is the reason DISTINCT exists as a keyword at all.

Superkey, candidate key, primary key. Say the difference.

A superkey is any set of attributes whose values are unique in every legal instance. A candidate key is a minimal superkey: remove any attribute from it and uniqueness is lost. The primary key is the one candidate key the designer declares. In our table {sid, name} is a superkey but not a candidate key, because dropping name leaves {sid}, which still identifies a row.

I show you three rows and every name in them is different. Is name a candidate key?

You cannot tell from that. A key is a constraint on every legal instance, so sample data can only disprove one: two rows sharing a name would prove name is not a key, but three distinct names say nothing about the fourth student. The answer that earns marks is to ask whether two students are allowed to have the same name, which is a question about the business rather than about the rows on the screen.

Where does NULL sit in the relational model?

Hard

You inherit one table attendance(student_id, name, course_list, present_on), where course_list holds strings like ‘C1, C2’ and there is no key of any kind. Produce a replacement design of three relations in which no cell holds a list and no two rows can be identical, and for each one give its degree and its candidate key. Then take the question the old table answered with a single SELECT and no join, "which courses is student S1 taking", and write it against your design. Finally, state which of your three relations is in trouble if a student can attend the same course twice on the same date.

Follow-up

That last part decides whether your third relation’s key is the three columns you probably chose or something you have to add, and it is settled by what the world allows rather than by which columns are convenient.

Show the hint

Before writing any DDL, list every distinct kind of fact the old table records. Each kind of fact becomes one relation, and the columns that identify one instance of that fact become its key.