SQL and the Relational Model experimental

SQL and the Relational Model The relational model and its language, taught on SQLite: joins, aggregation, windows, transactions, indexes and the query planner. Relational foundations and SELECT. Relational foundations and SELECT. Query with selection, projection and joins.. Distinguish selection, projection, and join operations from each other, and construct a SQL query that correctly combines set operations and joins to answer a stated question.. Relations, SELECT, Joins, Set operations Relations A relation is a set of tuples sharing the same attributes: in practice, a table with named, typed columns and rows with no guaranteed order. SQLite is dynamically typed (it uses type affinity rather than strict column types), but you should still design as if columns had fixed domains: an orders.customer_id column should always hold the same kind of value. A table has no inherent order; if you need rows in a particular sequence, you must say so with ORDER BY. Keys matter: a primary key uniquely identifies a row, and a foreign key (REFERENCES) constrains a column to values that exist in another relation, enforcing referential integrity. In SQLite, foreign keys are only enforced when PRAGMA foreign_keys = ON; is set per connection. SELECT SELECT performs projection (choosing columns) and, with WHERE, selection (choosing rows). The logical order of evaluation is FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY → LIMIT, which is *not* the order you type the clauses. This matters: you cannot reference a SELECT-list alias inside WHERE, because WHERE is evaluated before the alias exists. DISTINCT removes duplicate rows from the final result but is not a substitute for correct joins. LIMIT/OFFSET paginate an already-ordered result: never paginate without ORDER BY, or the order is undefined. Joins An INNER JOIN returns only rows where the join condition matches in both tables. A LEFT JOIN keeps every row from the left table, filling unmatched right-side columns with NULL. Put filters on the right-hand table in the ON clause, not WHERE, if you want to preserve unmatched left rows: a WHERE filter on a nullable right column silently turns a LEFT JOIN back into an INNER JOIN. SQLite supports CROSS JOIN (cartesian product, rows multiply) and, since 3.39, RIGHT JOIN and FULL OUTER JOIN. Self-joins compare a table to itself with different aliases, useful for hierarchies or pairwise comparisons. Set operations UNION combines result sets and removes duplicates; UNION ALL keeps duplicates and is cheaper since it skips deduplication. INTERSECT returns rows common to both queries; EXCEPT returns rows in the first query but not the second. All three require the same number of columns with compatible types in each SELECT, and the final ORDER BY applies to the combined result, not to an individual branch. SQL injection: when query construction meets untrusted input A query built by concatenating untrusted user input directly into Structured Query Language (SQL) text, rather than binding it as a parameter, lets an attacker supply input that changes the query's actual structure rather than just its data. The 2008 Heartland Payment Systems breach, one of the largest disclosed at the time, exploited exactly this class of flaw to plant network sniffers after gaining initial access, and SQL injection remained on the Open Worldwide Application Security Project (OWASP) Top 10 list of web application risks for over a decade afterward because the underlying mistake, string-concatenating input into a query, is easy to make and easy to miss in review. Parameterized queries (? placeholders bound separately from the query text) close this gap structurally: the database driver sends the query template and the values as distinct pieces, so a value can never be interpreted as query syntax no matter what characters it contains. The relational model versus earlier data models Before Codd's 1970 paper, the dominant commercial database models were hierarchical (International Business Machines' Information Management System (IMS)) and network-based (the CODASYL model), both of which required application code to navigate explicit, hardcoded pointers between records, meaning a change to the physical storage layout could break every program that queried the data. Codd's central proposal was physical data independence: express what data you want in terms of relations and predicates, and let the database system decide how to actually retrieve it, which is exactly what a SELECT statement's declarative style still does today. This separation between what a query asks for and how the engine executes it is also what makes the query planner covered later in this course possible at all: a declarative language leaves the engine free to choose a different, better execution strategy without the application's query text ever needing to change. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Aggregation and windows. Aggregation and windows. Aggregate and compute window functions.. Explain the difference between GROUP BY aggregation and window functions, and construct a window function query with the correct frame to answer a stated ranking or running-total question.. GROUP BY, HAVING, Window functions, Frames GROUP BY GROUP BY collapses rows sharing the same value(s) of the grouping expression(s) into a single output row, and aggregate functions (COUNT, SUM, AVG, MIN, MAX, GROUP_CONCAT in SQLite) then summarize the rows in each group. Every non-aggregated column in the SELECT list must appear in GROUP BY, or the result is ambiguous: SQLite is permissive here and will silently pick an arbitrary row's value, which is a common bug source, so treat the rule as if it were strictly enforced. COUNT(*) counts rows including NULLs in any column; COUNT(col) counts only non-NULL values of col; COUNT(DISTINCT col) counts distinct non-NULL values. NULL values are grouped together as a single group by GROUP BY, unlike in comparisons where NULL = NULL is unknown. HAVING WHERE filters rows before grouping; HAVING filters groups after aggregation. A condition on an aggregate (HAVING COUNT(*) > 5) cannot go in WHERE because the aggregate doesn't exist until groups are formed. Conversely, filtering on a raw column is cheaper in WHERE, since it shrinks the input before the (often expensive) grouping step. You can HAVING on an expression that isn't in the SELECT list at all, since it operates over the grouped-but-not-yet-projected data. Window functions A window function computes a value per row over a set of related rows (its "window") without collapsing them, unlike GROUP BY. The syntax is function(...) OVER (PARTITION BY ... ORDER BY ... frame). ROW_NUMBER() assigns a unique sequential integer per partition; RANK() leaves gaps after ties; DENSE_RANK() does not. LAG/LEAD access a prior/following row's value without a self-join. SUM(x) OVER (PARTITION BY g ORDER BY d) computes a running total within each group g ordered by d. Window functions run after WHERE/GROUP BY/HAVING but before the final ORDER BY, so you cannot filter directly on a window function's result in WHERE; wrap the query in a common table expression (CTE) or subquery and filter in the outer query instead. Frames The frame clause (ROWS/RANGE BETWEEN ... AND ...) narrows the window further, row by row. The default frame, when ORDER BY is present, is RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, which is why a naive running-total query works. ROWS BETWEEN 2 PRECEDING AND CURRENT ROW gives a 3-row moving average. RANGE groups peer rows with equal ORDER BY values into the same frame boundary, which can surprise you with duplicate order keys; ROWS is positional and unambiguous. Use ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING to aggregate over the entire partition per row, e.g. for a percent-of-total calculation. Common table expressions as named subqueries A common table expression, written WITH cte_name AS (SELECT ...) before the main query, gives a subquery a name that can be referenced later in the statement, which makes a multi-step query readable top to bottom instead of nested inside-out. This matters especially for the window-function filtering pattern this module introduces: computing ROW_NUMBER() inside a CTE and then filtering WHERE row_num = 1 in the outer query is both correct and far easier to read than the same logic buried in a nested subquery. A CTE can also reference itself (a recursive CTE), which is the standard Structured Query Language (SQL) mechanism for querying hierarchical data such as an organization chart or a bill-of-materials tree, a capability the relational model's flat, set-based structure does not otherwise provide directly. Window functions as a SQL standard addition Aggregate functions and GROUP BY were part of SQL from its earliest standardization, but window functions, which compute a per-row value over a related set of rows without collapsing them, were only formally added in the SQL:2003 revision of the joint ISO and International Electrotechnical Commission (IEC) standard numbered 9075, decades after basic aggregation. PostgreSQL shipped window function support in its 8.4 release in 2009, and SQLite added them considerably later, in its 3.25.0 release in 2018, which is why a query relying on RANK() or a moving-average frame will fail outright on an older SQLite build even though the same query has been valid standard SQL since 2003. This staggered rollout across engines is a useful reminder that 'standard SQL' and 'SQL your specific database version actually supports' are not always the same set of features. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Transactions. Transactions. Reason about ACID and isolation.. Distinguish the four ACID properties and the concurrency anomalies each isolation level prevents, and evaluate a given transaction scenario to identify which anomaly, if any, it exhibits.. ACID, Isolation levels, Locking, Anomalies ACID Atomicity means a transaction's writes all happen or none do: SQLite achieves this via a rollback journal or, more commonly today, write-ahead logging (WAL). Consistency means a transaction moves the database from one valid state to another, respecting constraints (CHECK, FOREIGN KEY, UNIQUE). Isolation means concurrent transactions appear not to interfere, to a degree controlled by the isolation level. Durability means once a transaction commits, it survives a crash: SQLite calls fsync (or platform equivalent) at commit unless you've explicitly weakened this with PRAGMA synchronous = OFF. BEGIN / COMMIT / ROLLBACK delimit a transaction explicitly; without BEGIN, SQLite runs each statement in its own implicit transaction. Isolation levels The Structured Query Language (SQL) standard defines four levels (READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ, SERIALIZABLE), trading concurrency for protection against anomalies. SQLite doesn't implement the standard's row-level multi-version concurrency control (MVCC) isolation levels the way Postgres does; instead, in WAL mode, each transaction sees a consistent snapshot of the database as of when it started (roughly SERIALIZABLE for a single writer), and only one writer may hold the write lock at a time, so there is no true concurrent-writer optimistic isolation. PRAGMA read_uncommitted exists but only affects in-process shared-cache mode, not cross-process behavior. The practical lesson generalizes beyond SQLite: stronger isolation prevents more anomalies but serializes more work and increases contention. Locking SQLite's rollback-journal mode uses a whole-database lock progression: SHARED (readers) → RESERVED (a writer intends to write) → EXCLUSIVE (actually writing), so with journal mode a writer blocks all other writers and, at the exclusive phase, all readers too. WAL mode decouples this: readers no longer block on a writer, since readers see the last-committed snapshot while the writer appends to the WAL file, but there is still only one writer at a time (SQLITE_BUSY is returned to a second writer if it doesn't wait). PRAGMA busy_timeout makes a blocked writer retry for a period instead of failing immediately. Anomalies A lost update happens when two transactions read the same row, each computes a new value from the old one, and the second write clobbers the first's, e.g., two UPDATE accounts SET balance = balance - 100 issued as read-then-write application code racing each other. A dirty read is reading another transaction's uncommitted write (prevented by READ COMMITTED and above). A non-repeatable read is re-reading the same row within a transaction and getting a different value because another transaction committed a change in between (prevented by REPEATABLE READ and above). A phantom read is re-running the same range query and seeing new rows appear (prevented by SERIALIZABLE). The fix for lost updates is either a single atomic UPDATE ... SET balance = balance - 100 WHERE id = ? (push the read-modify-write into the database) or explicit optimistic concurrency with a version column checked in the WHERE clause. Where the ACID acronym comes from The term Atomicity, Consistency, Isolation, Durability (ACID) was coined by Theo Harder and Andreas Reuter in their 1983 paper 'Principles of Transaction-Oriented Database Recovery,' published in ACM Computing Surveys, which drew together earlier work, notably Jim Gray's 1981 paper 'The Transaction Concept: Virtues and Limitations,' into the four-property framework this module teaches. Gray's paper had already identified the core anomalies (what this module calls lost updates, dirty reads, and the rest) that a transaction system needs to prevent; Harder and Reuter's contribution was naming and formalizing the four guarantees a system provides in order to prevent them, giving database designers and users a shared vocabulary that has remained essentially unchanged for four decades. Write-ahead logging as a durability and concurrency mechanism Write-ahead logging, the mechanism behind SQLite's WAL mode, works by appending every change to a sequential log file before (or instead of) modifying the actual database pages in place, so a crash mid-write leaves a complete, replayable record of what was intended rather than a partially-overwritten data file. This single mechanism serves two of the four ACID properties at once: durability, because the log can be replayed to recover committed-but-not-yet-applied changes after a crash, and improved concurrency for isolation, because readers can continue reading the last-consistent database state while a writer appends to the log without either blocking the other. This is why WAL mode's reader/writer concurrency improvement over the older rollback-journal locking scheme is not a separate feature bolted on top, but a direct consequence of the append-only logging design itself. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Indexes and the planner. Indexes and the planner. Read the query planner and index sensibly.. Explain how a B-tree index and the query planner interact, and evaluate an EXPLAIN QUERY PLAN output to justify whether a given index is being used effectively.. B-tree indexes, EXPLAIN, Planner decisions, When indexes hurt B-tree indexes SQLite tables are themselves stored as a B-tree keyed on rowid (or the INTEGER PRIMARY KEY, which is an alias for rowid). A secondary index is a separate B-tree keyed on the indexed column(s), with each leaf entry pointing back to the corresponding rowid, which SQLite then uses to fetch the full row from the table B-tree (unless the index alone can satisfy the query, i.e. a covering index). An index makes equality and range lookups on the indexed column(s) logarithmic instead of a full linear scan, but every insert/update/delete must also maintain the index, and each index adds storage and write cost. A composite index CREATE INDEX idx ON t(a, b) is only useful for lookups on a alone or a and b together, left to right: it does not help a query that filters on b alone, because the B-tree is sorted by a first. EXPLAIN EXPLAIN QUERY PLAN SELECT ... shows, in human-readable form, how SQLite intends to execute a query: whether it does a SCAN (reads every row of a table) or a SEARCH (uses an index to jump to matching rows), and which index it picked, if any. SCAN TABLE orders on a large table is a red flag if you expected a selective filter; SEARCH TABLE orders USING INDEX idx_orders_customer (customer_id=?) confirms the index is used. EXPLAIN (without QUERY PLAN) dumps the low-level virtual machine bytecode, useful for deep debugging but rarely needed day to day. Always check the plan before assuming an index helps: SQLite may reject a usable index if statistics suggest a full scan is cheaper. Planner decisions SQLite's query planner is cost-based but relies on table statistics gathered by ANALYZE (stored in sqlite_stat1); without running ANALYZE on a populated database, the planner guesses and may make poor choices, especially with skewed data. The planner considers index selectivity: an index on a column with only two distinct values (e.g., a boolean is_active) is rarely useful because a lookup still returns roughly half the table. The planner chooses join order and access method per table, generally preferring the plan with the lowest estimated row-visit cost, and it will use an index to satisfy ORDER BY without a separate sort step when the index order matches. When indexes hurt Indexes slow down writes: every INSERT/UPDATE/DELETE must update every index touching the changed columns, so a table with many rarely-used indexes pays a continuous tax on write-heavy workloads. Indexes also cost storage, sometimes comparable to the table itself. A low-selectivity index (few distinct values) is often worse than no index, since the planner may still choose it incorrectly, or maintaining it wastes effort for no benefit. Wrapping an indexed column in a function or expression in WHERE (WHERE lower(name) = 'x') defeats a plain index on name: you need an expression index (CREATE INDEX ON t(lower(name))) to match. The lesson: index to support your actual, measured query patterns (verified with EXPLAIN QUERY PLAN), not speculatively. The B-tree's origin Rudolf Bayer and Edward McCreight invented the B-tree in 1970 while both worked at Boeing Research Labs, publishing the structure formally in their 1972 paper 'Organization and Maintenance of Large Ordered Indexes' in the journal Acta Informatica. Their design goal was specifically disk-oriented: unlike an in-memory binary tree, a B-tree's nodes are sized to match a disk page, so each node read pulls in many keys at once and the tree's height, and therefore the number of expensive disk reads needed for a lookup, stays small even for millions of rows. More than fifty years later, this remains the dominant index structure in nearly every relational database, including SQLite, precisely because the fundamental cost asymmetry it was designed around, a disk or flash read costing far more than an in-memory comparison, has not gone away even as storage technology has changed underneath it. Cost-based optimization since System R International Business Machines' System R project, the first working implementation of Codd's relational model, published its query optimizer's design in Selinger et al.'s 1979 Special Interest Group on Management of Data (SIGMOD) paper 'Access Path Selection in a Relational Database Management System.' That paper introduced the core idea every modern cost-based optimizer, including SQLite's, still uses: estimate the cost of each candidate access path (a full scan versus one or more available indexes) using table and index statistics, and choose the cheapest estimated plan rather than a fixed rule. This is precisely why ANALYZE matters in practice: an optimizer following the System R design is only as good as the statistics it has to reason with, and a planner working from stale or absent statistics can choose a worse plan even though the underlying cost-based logic it is running is sound. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/)