Prerequisites: Data Modelling, the Relational Model & SQL

01 · Motivation

What TIS assumes you already know

The TIS exam is two parts: three open theory questions (15 pts) and a design exercise (17 pts). The design exercise is always either a data-integration design or a data-warehouse design — and both of them open by handing you a relational or ER schema and expecting you to read it fluently. Marks are lost on the prerequisites far more often than on the TIS material itself.

Here is the ledger. Every row is something TIS uses without introducing, together with the first chapter that needs it and the concrete skill the exam tests.

The running example: PoliBooks

One example runs through the whole chapter, chosen because it grows into both TIS exam exercises. It is a small bookshop chain: shops in cities, books by authors in genres, and a sales record.

PoliBooks — the operational (transactional) world

  AUTHOR ──< WRITTEN_BY >── BOOK ──> GENRE
                              │
                              │ sold in
                              ▼
  REGION <── CITY <── STORE ──< SALE >
                                 (date, quantity, unit price, discount)

By the end of the chapter you will have drawn this in ER, in UML, translated it to tables, checked its normal form, queried it in algebra and in SQL — and seen exactly where chapter 07 will pick it up to build a fact schema.

02 · Conceptual model

The Entity-Relationship model

The ER model describes what the world contains, independently of any DBMS. It has six constructs worth memorising.

Cardinality — read it on the entity’s own side

This is the single most misread piece of notation in the whole prerequisite set, so state it precisely. Given a relationship $R$ between entities $E_1$ and $E_2$, the pair written next to $E_1$ answers:

So min is a participation constraint (0 means optional, 1 means mandatory), and max is a multiplicity constraint (1 means at most one, N means unbounded). For PoliBooks:

The type of a relationship is named from the two max values: WRITTEN_BY is many-to-many (N:M), BELONGS_TO and LOCATED_IN are many-to-one (N:1).

Weak entities and external identifiers

An entity that cannot be identified on its own borrows an identifier through a relationship. A SALE line is only identified by its receipt and its line number:

SALE  identifier: (lineNo, RECEIPT via ISSUED_ON)
      i.e. lineNo alone repeats across receipts; receipt + lineNo is unique

The rule to remember for the translation in section 05: an external identifier always turns into a composite primary key containing the owner’s key.

Generalizations

A generalization is described by two orthogonal flags:

• Total (every parent instance is in some child) versus partial.
• Exclusive (a parent instance is in at most one child) versus overlapping.

The four combinations lead to different translation strategies — section 05 covers them, and the choice is examinable in any course that grades a logical schema.

03 · Notation

UML class diagrams, and the ER dictionary

Polimi teaches conceptual modelling in both notations, and TIS mixes them: integration papers tend to show ER, while wrapper and ontology material (chapter 04) and any industrial deck lean on UML. They express nearly the same information, so the safe move is to keep a translation table in your head.

The UML totality and disjointness flags map straight onto the ER generalization flags:

04 · Logical model

The relational model

Where ER describes the world, the relational model describes what a relational DBMS actually stores. TIS lives at the seam between the two, so be precise about the vocabulary.

Domain

A set of atomic values, e.g. the integers, or strings of length at most 60.

Relation schema

A name plus a set of typed attributes, written BOOK(isbn, title, price, genreCode). This is the intensional level — it does not change as data arrives.

Relation instance

A finite set of tuples over that schema. The extensional level — it changes with every insert. Because it is a set, there are no duplicate tuples and no tuple order.

Tuple

One row; t[A] denotes the value of tuple t on attribute A.

Superkey

Any attribute set whose values are unique across the instance, for every legal instance.

Candidate key

A minimal superkey — remove any attribute and uniqueness is lost.

Primary key

The candidate key the designer picks; it may not contain NULL.

Foreign key

An attribute set in one relation constrained to appear as a key value in another (or be NULL).

Integrity constraints

A schema is not just structure; it is structure plus the constraints a legal instance must satisfy.

• Domain constraint — every value lies in its attribute’s domain.
• Key constraint — no two tuples agree on the primary key.
• Entity integrity — no primary-key attribute is NULL.
• Referential integrity — every non-NULL foreign-key value matches an existing key value in the referenced relation. Violations are handled with CASCADE, SET NULL, or rejection.
• Check constraints — arbitrary tuple-level predicates, e.g. quantity > 0.

NULL and three-valued logic

NULL means no value here, and it is neither zero nor the empty string. Any comparison against NULL yields unknown, not true or false. The consequences bite in every SQL exercise:

• WHERE price = NULL never matches; you must write WHERE price IS NULL.
• WHERE price <> 10 silently drops rows where price is NULL.
• COUNT(*) counts rows; COUNT(price) counts rows where price is not NULL.
• SUM, AVG, MIN, MAX ignore NULLs — so AVG over a column with NULLs is not SUM(col) / COUNT(*).

05 · The bridge

Translating ER to a relational schema

This is the mechanical bridge between the two previous sections, and chapter 04 asks you to run it after reverse-engineering an XML DTD or a JSON document into a conceptual schema. Four rules cover almost everything.

Weak entities follow from rule 2 with one addition: the borrowed foreign key becomes part of the primary key rather than a plain column.

AUTHOR(authorId PK, name, country)
GENRE (genreCode PK, genreName, section)
BOOK  (isbn PK, title, price, pages)
REGION(regionCode PK, regionName)
CITY  (cityCode PK, cityName, population)
STORE (storeId PK, storeName, address)

BOOK (isbn PK, title, price, pages, genreCode FK -> GENRE  NOT NULL)
STORE(storeId PK, storeName, address, cityCode FK -> CITY  NOT NULL)
CITY (cityCode PK, cityName, population, regionCode FK -> REGION NOT NULL)

WRITTEN_BY(isbn FK -> BOOK, authorId FK -> AUTHOR, role)
           PK = (isbn, authorId)

SALE(receiptNo, lineNo, saleDate, quantity, unitPrice, discount,
     storeId FK -> STORE, isbn FK -> BOOK)
     PK = (receiptNo, lineNo)

06 · Dependencies

Functional dependencies and normal forms

This section is short but it is the highest-leverage part of the chapter, because chapter 07’s attribute tree is nothing but a functional-dependency graph and chapter 08’s star versus snowflake decision is nothing but a normalization trade-off.

The definition

A functional dependency $X \to Y$ holds on relation $R$ when any two tuples that agree on the attributes $X$ also agree on the attributes $Y$:

An FD is a statement about every legal instance, not about the rows you happen to see. It comes from the meaning of the data, so you infer it from the domain, never from a sample.

Keys fall straight out of the definition: $K$ is a superkey of $R$ exactly when $K \to R$, and a candidate key when no proper subset of $K$ also determines $R$. In PoliBooks:

isbn         -> title, price, pages, genreCode
genreCode    -> genreName, section
storeId      -> storeName, address, cityCode
cityCode     -> cityName, population, regionCode
regionCode   -> regionName
(receiptNo, lineNo) -> saleDate, quantity, unitPrice, discount, storeId, isbn

Anomalies and the normal forms

Denormalized tables suffer three classic anomalies: update (change Milan’s population in one row and not the others), insertion (cannot record a city with no store), and deletion (removing the last store erases the city). The normal forms exist to eliminate them.

An attribute is prime when it belongs to some candidate key. BCNF is strictly stronger than 3NF; the two differ only when a schema has overlapping candidate keys, which is rare in practice and common in exams.

STOREFLAT(storeId PK, storeName, address, cityCode, cityName,
          population, regionCode, regionName)

cityCode   -> cityName, population, regionCode
regionCode -> regionName

STORE (storeId PK, storeName, address, cityCode FK)
CITY  (cityCode PK, cityName, population, regionCode FK)
REGION(regionCode PK, regionName)

07 · Query semantics

Relational algebra

Relational algebra is the mathematical query language whose operators consume relations and produce relations. TIS needs it for one specific reason: a GAV mapping defines each global relation as an algebraic view over the sources, and chapter 02 grades exactly that.

σ (selection)

Keeps the tuples satisfying a predicate. σ picks rows.

π (projection)

Keeps the listed attributes, then removes duplicates (the result is a set). π picks columns.

ρ (rename)

Renames a relation or its attributes — the operator that resolves the name conflicts chapter 01 asks you to detect.

× (product)

Every pairing of tuples from two relations; almost always followed by a selection.

∪ − ∩ (set operators)

Union, difference, intersection — defined only for union-compatible relations, i.e. same arity and matching domains.

⋈ (join)

A product followed by a selection. The natural join equates all same-named attributes; a theta join takes an explicit predicate.

Outer join

Like a join, but tuples with no match are kept and padded with NULL — left, right, or full. Indispensable when integrating sources that do not fully overlap.

γ (grouping)

Partitions by the grouping attributes and applies aggregates; the algebraic form of SQL’s GROUP BY.

Only six of these are primitive — selection, projection, rename, product, union, difference — and everything else is derived. That is worth knowing because a theory question may ask you to express one operator in terms of others.

08 · Query language

The SQL you must be able to write cold

Chapter 08 grades a full OLAP query in most DW sessions. These are the shapes it assumes.

The evaluation order that explains everything

Written order and evaluation order are different, and almost every SQL confusion dissolves once you internalise the second:

written:    SELECT ... FROM ... WHERE ... GROUP BY ... HAVING ... ORDER BY ...
evaluated:  FROM -> WHERE -> GROUP BY -> HAVING -> SELECT -> ORDER BY

Three consequences follow immediately:

• WHERE filters rows, HAVING filters groups. WHERE runs before grouping exists, so it cannot mention an aggregate; HAVING runs after, so it can.
• A SELECT alias is not visible in WHERE or GROUP BY, because SELECT is evaluated later. It is visible in ORDER BY.
• Every column in SELECT must be grouped or aggregated. After GROUP BY each group is one output row, so an ungrouped, unaggregated column has no single value to show.

Joins

-- inner: only matching pairs survive
SELECT B.title, G.genreName
FROM   BOOK B JOIN GENRE G ON B.genreCode = G.genreCode;

-- left outer: every book survives, genre columns NULL when unmatched
SELECT B.title, G.genreName
FROM   BOOK B LEFT OUTER JOIN GENRE G ON B.genreCode = G.genreCode;

Use an outer join whenever the question says “including those with none” — books with no sales, stores with no staff. An inner join silently deletes exactly the rows such a question is asking about.

Grouping and aggregation

SELECT   C.cityName, COUNT(*) AS numSales, SUM(S.quantity) AS totalQty
FROM     SALE S
         JOIN STORE T ON S.storeId  = T.storeId
         JOIN CITY  C ON T.cityCode = C.cityCode
WHERE    S.saleDate >= DATE '2025-01-01'
GROUP BY C.cityName
HAVING   SUM(S.quantity) > 500
ORDER BY totalQty DESC;

That is the canonical warehouse query shape: fact joined to its dimensions, filtered, grouped by a dimension attribute, aggregated over a measure. Chapter 08 varies it — WITH CUBE, WITH ROLLUP, window functions, greatest-per-group — but the skeleton never changes.

Subqueries and views

-- scalar subquery: books priced above average
SELECT title FROM BOOK
WHERE  price > (SELECT AVG(price) FROM BOOK);

-- correlated EXISTS: genres that have at least one book over 50
SELECT G.genreName FROM GENRE G
WHERE  EXISTS (SELECT 1 FROM BOOK B
               WHERE B.genreCode = G.genreCode AND B.price > 50);

-- a view: a named query, and the mechanism behind GAV
CREATE VIEW ExpensiveBooks AS
SELECT isbn, title, price FROM BOOK WHERE price > 50;

09 · Practice

Exercises

Work each one on paper before opening its solution. They are ordered to mirror the chapter, and the last three are deliberately in the shape TIS will use them.

SELECT   R.regionName, COALESCE(SUM(S.quantity), 0) AS totalQty
FROM     REGION R
         LEFT OUTER JOIN CITY  C ON C.regionCode = R.regionCode
         LEFT OUTER JOIN STORE T ON T.cityCode   = C.cityCode
         LEFT OUTER JOIN SALE  S ON S.storeId    = T.storeId
                                AND S.saleDate >= DATE '2025-01-01'
                                AND S.saleDate <  DATE '2026-01-01'
GROUP BY R.regionName;

10 · Recap

Next: chapter 01 picks up exactly here, handing you two operational schemas of this kind and asking what it takes to merge them into one.