Relation, tuple, attribute, domain, degree, cardinality, schema; properties of relations

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What is a relation, in terms of domains and the Cartesian product? from Lesson 0.2.2
2. How are entity types and attributes drawn in Chen notation? from Lesson 1.1.1
3. How do you map "each X has exactly one Y" to constraints? from Lesson 1.3.1

1 · The Hook

The ER diagram is a sketch for people. The DBMS needs something it can store and query: tables. The relational model, proposed by E. F. Codd in 1970, says a database is just a collection of tables, and a table is a mathematical relation: a set of tuples. Because it is a set, some properties come free, and GATE asks about them: no duplicate rows, no row order, one value per cell.

2 · Predict First

Below, which rows can appear together in one relation STUDENT(roll, name, dept)? (a) (1, Asha, CS) twice; (b) (1, Asha, CS) and (2, Asha, CS); (c) (3, Chirag, {CS, EE}).

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

(a) No: a relation is a set, so the same tuple cannot appear twice. (b) Yes: the tuples differ in roll. (c) No: every value must be a single (atomic) value from the domain, not a set of values.

Vocabulary

Schema and state

• A relation schema R(A₁, A₂, …, Aₙ) gives the relation's name and attributes, each with a domain: STUDENT(roll, name, dept, cgpa). It is part of the schema.
• A relation state (or relation instance) r(R) is the set of tuples stored now. It changes with every insert and delete.
• A relational database schema is a set of relation schemas plus constraints: {STUDENT, COURSE, ENROLL, DEPT}.

Formally r(R) ⊆ dom(A₁) × dom(A₂) × … × dom(Aₙ) (Lesson 0.2.2). Degree is fixed by the schema; cardinality changes with the state.

Properties of a relation

1. No duplicate tuples: a relation is a set.
2. Tuples are unordered: {t₁, t₂} = {t₂, t₁}. Displaying rows in some order does not make the order part of the relation.
3. Attributes are named, so their order does not matter when tuples are read as name → value mappings. (In the plain tuple notation, the schema fixes the order.)
4. Values are atomic: each cell holds one indivisible value from its domain, or NULL. No sets, no lists, no nested tables. This is called first normal form (1NF); Lesson 4.4.1 returns to it.

So a composite ER attribute must be flattened into its parts, and a multivalued ER attribute cannot be a column (Lesson 2.4.1 shows where it goes).

Notation

t[A] means the value of attribute A in tuple t: for t = (1, Asha, CS, 9.1), t[name] = Asha. t[A, B] is the sub-tuple of those attributes.

Limits

For domains of sizes d₁, …, dₙ the cardinality of any state is at most d₁ × d₂ × … × dₙ (all possible tuples), and the number of possible states is 2^(d₁·…·dₙ).

4 · Visual

          attributes (degree = 4)
           |      |      |      |
         roll   name   dept   cgpa        <- relation schema STUDENT(roll, name, dept, cgpa)
        ------ ------ ------ ------
tuple ->   1   Asha    CS    9.1   \
tuple ->   2   Bhavin  EE    7.8    |  relation state:
tuple ->   3   Chirag  CS    8.4    |  cardinality = 4
tuple ->   4   Diya    ME    6.9   /   (rows in any order; no two identical)

5 · Worked Examples

Example 1 Easy

ENROLL(roll, cid, grade) currently holds 7 tuples. Give its degree and cardinality. Which one can change tomorrow without changing the schema?

Solution

Degree 3, cardinality 7. Cardinality changes with every insert or delete; degree changes only if the schema changes.

Example 2 Medium

Two displays of STUDENT list the same four tuples in different orders. Are they the same relation? What if one display shows Asha's row twice?

Solution

Same tuples in different orders: the same relation (tuples are unordered). A display with a repeated row is not a relation at all; a relation cannot contain a tuple twice.

Example 3 GATE

R(A, B, C) where dom(A) = {0, 1}, dom(B) = {0, 1, 2}, dom(C) = {x, y}. What is the maximum cardinality of a state of R, and what is the degree?

Solution

Maximum cardinality = 2 × 3 × 2 = 12; degree = 3.

8 · Connect the Dots

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Degree

EMPLOYEE(eid, name, dept, salary, phone) holds 250 tuples. What is its degree?

Numerical answer: ________

Q2 · MCQ · 1 mark(s) — Properties

Which is not a property of a relation in the relational model?

1. (A) Each attribute has a domain
2. (B) Tuples have a fixed order
3. (C) No two tuples are identical
4. (D) Each value is atomic

Q3 · NAT · 2 mark(s) — Max cardinality

R(A, B, C, D): dom(A) has 3 values, dom(B) 2, dom(C) 4, dom(D) 1. What is the largest possible cardinality of a state of R?

Numerical answer: ________

Q4 · MSQ · 2 mark(s) — Schema vs state

Which change the state of STUDENT but not its schema?

1. (A) Inserting a new student
2. (B) Adding a column email
3. (C) Updating Asha's CGPA
4. (D) Deleting a student

Q5 · MCQ · 1 mark(s) — Atomicity

A cell holding {Hindi, English} for languages_spoken violates:

1. (A) the atomic-values property (1NF)
2. (B) the unordered-tuples property
3. (C) the no-duplicate-tuples property
4. (D) nothing; this is allowed

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

relationtupleattributedegree (arity)cardinalityrelation schemarelation state (instance)relational database schemaatomic valuefirst normal form (1NF, informal)t[A] notation