Lossy and lossless compression

Lossless compression discards nothing — the original is restored bit for bit. Essential for text, code and executables.

• Run-length encoding (RLE) — replace runs of identical values with a (value, count) pair. AAAAABBBCCCCCCCC (16 characters) becomes A5 B3 C8 (6 characters).
• Dictionary encoding — build a dictionary of repeated sequences and transmit short index codes. The decoder rebuilds the same dictionary as it goes.

Lossy compression permanently discards data that human perception will not miss — MP3 removes inaudible frequencies, JPEG throws away fine colour detail. Far smaller files, and the discarded data is gone forever.

RLE's weakness: on data with no runs — ordinary English text, for instance — every single character becomes a (character, 1) pair, so the file gets bigger. No compression algorithm can shrink every possible input; that is a mathematical impossibility, not an engineering failure.

Your turn — run-length encoding

Encryption and hashing

Digital signatures: the sender hashes the message and encrypts the hash with their private key. Anyone can decrypt it with the public key, hash the message themselves, and compare — proving both authenticity and integrity.

Hashing is one-way: it turns input of any size into a fixed-size digest that cannot be reversed. It is used to index hash tables and, crucially, to store passwords — so a stolen database yields nothing usable.

Hashing is not encryption. Encryption is designed to be reversed by whoever holds the key. Hashing is designed never to be reversed at all. Confusing them is the single commonest error in this topic.

Relational databases and normalisation

A flat file holds everything in one table, so data is repeated in row after row. That redundancy causes update anomalies: change a customer's address and you must edit every row that mentions them — miss one and the database now contradicts itself.

A relational database splits data into linked tables:

• Primary key — uniquely identifies each record; never null, never duplicated.
• Foreign key — an attribute pointing at another table's primary key. Referential integrity means it must always match an existing record.
• Secondary key / index — an extra index to speed up common searches.

The mantra: every non-key attribute depends on the key, the whole key, and nothing but the key. A many-to-many relationship must be resolved with a link table.

SQL, transactions and ACID

A transaction must succeed or fail as one indivisible unit. The ACID guarantees:

• Atomicity — all of it happens, or none of it does (a failure triggers a rollback);
• Consistency — the database moves from one valid state to another; constraints still hold;
• Isolation — concurrent transactions do not interfere;
• Durability — once committed, the change survives a crash.

Record locking stops two users updating the same record at once (the lost update problem) — at the risk of deadlock, where each transaction waits for a lock the other holds. Redundancy (mirrored servers) protects against hardware failure.

The most dangerous line in SQL: DELETE FROM Student; — with the WHERE clause forgotten, that removes every row. Write the WHERE clause first, then the rest.

Your turn — the SQL result

ACID

Networks and the TCP/IP stack

Packet switching: data is split into packets, each routed independently and possibly by a different route, then reassembled in order using their sequence numbers. This uses the network efficiently and routes automatically around failure and congestion. Circuit switching instead reserves a dedicated path for the whole call — guaranteed bandwidth, but the line sits idle whenever nobody is speaking.

DNS is a distributed, hierarchical database that resolves a domain name to an IP address. Client-server centralises control on a server; peer-to-peer makes every machine both client and server, with no single point of failure and capacity that grows with the number of peers.

Your turn — transfer time

Web technologies

• HTML — the structure and content of the page.
• CSS — the presentation: colour, layout, typography. Separating it from HTML means one stylesheet can restyle a thousand pages.
• JavaScript — behaviour, executed client-side in the browser.

Search engine indexing: web crawlers follow links, and the pages are indexed by keyword. PageRank then ranks them: a page is important if important pages link to it. A link from a highly ranked page passes on more weight than a link from an obscure one — which is why simply creating thousands of junk pages that link to you does not work.

The security rule you must never forget: always validate on the server, even if you have already validated on the client. Client-side code runs on a machine the attacker controls completely — they can simply switch it off and post whatever they like.

Client vs server

Compression

Which TCP/IP layer?

Tap an item, then tap the layer it belongs to.

Match the technique to its purpose

Tap an item on the left, then its partner on the right.

The big ideas to know

That is the whole of OCR 1.3. Press Finish to see your score.