Core CS · DBMS

Six ways a folder of files loses your data

Every feature of a DBMS is an answer to one of six failures of the file-processing system it replaced. You will watch two of those failures happen to one student’s record, then name the mechanism that closes each one.

Change one address, then lose 5,000 rupees →

One fact stored in two files is not a copy. It is a second fact, free to disagree with the first, and nothing on disk knows the two were ever related.

01 The idea

The rules lived inside the programs

Before database systems, an organisation kept its records in ordinary operating-system files and wrote one program per job to read them. A college had an admissions file and an admissions program, a library file and a library program, a fees file and a fees program. That is a file-processing system, and for one office with one file it works perfectly well.

It stops working the moment there are two. The layout of admissions.dat is not recorded anywhere on disk. It lives inside the admissions program as byte offsets and field widths, compiled in. So the library cannot read that file, and does the only thing available to it: it creates its own file with the fields it needs. Asha’s address is now written in two places by two programs that have never heard of each other.

Six problems come out of that, and the interview version of this topic is to list them. The list is easy to memorise and easy to spot as memorised. What turns it into an answer is that each problem has one named mechanism that closes it, and every one of those mechanisms moves the guarantee out of the programs and into the store. Three of them are rules you declare once beside the data, so every program that connects gets them whether it knows about them or not. The other three are services the store runs on your behalf: a query engine, a recovery log, a lock manager. No program can supply those for itself, which is why care and discipline never closed them.

In a file-processing system the data is on disk and everything that protects it lives inside a program. A DBMS moves that protection to where the data is: three of the six as a rule you declare once, three as a service the store runs for you. Either way, nothing that connects can skip it.

File-processing systemRecords kept in ordinary operating-system files, with one or more programs per file that know its layout by heart. Each new requirement got a new file and a new program, written by whoever needed it.

RedundancyThe same fact stored in more than one place. It costs almost nothing in disk and everything in trust, because nothing keeps the copies in step and nothing records which one is current.

AtomicityA group of writes that must all take effect or none of them. A transfer is two writes, and there is no correct state of the world in which only the first one reached disk.

02 Worked example

Two offices, two files, one address

The college keeps admissions records and library records in two files, written years apart by two teams. Here are the two record layouts exactly as the two programs know them: fixed byte offsets and fixed widths, with nothing on disk to describe either.

-- admissions.dat · written by the admissions office, one record per student  sid        CHAR(4)      bytes  0..3  name       CHAR(30)     bytes  4..33  address    CHAR(40)     bytes 34..73  course     CHAR(6)      bytes 74..79 -- library.dat · written by the library, six years later, different team  member_id  CHAR(4)      bytes  0..3    -- the same sid, another name  addr       CHAR(30)     bytes  4..33   -- the same address, ten bytes shorter  books_out  CHAR(2)      bytes 34..35 -- S1 Asha lives in both files. Nothing on disk says so.

Lines 8 and 9 are the whole lesson in two lines. member_id and sid are one fact under two names, and addr and address are one fact at two widths. Asha’s address today is 12 MG Road, Bengaluru 560001, twenty-eight characters, so it fits both fields. The new one she files in March is 8 Park Lane, Kondapur, Hyderabad 500084, thirty-nine characters, so it fits one of them.

1 · One officeadmissions writes admissions.dat; one program holds the byte offsets

→

2 · A second officethe library cannot read that layout, so it creates library.dat with the fields it wants

→

3 · The same fact twicethe address is now in both files, at two widths, under two column names

→

4 · A question across bothwho has books out and owes fees? no program reads both files, so somebody writes a third

→

5 · Rules everywherefive programs, five private copies of how wide an address is and when an advance may go negative

Read the highlighted node as a ratchet, not a mistake. Nobody sat down and decided to store the address twice. The library needed data it could not read and made a copy, which was the correct local decision at the time. The system got worse one reasonable step at a time, and by node 5 there is no single place left to change anything.

Everything in the next section is a consequence of nodes 3 and 5. Node 3 is why two records can disagree, and node 5 is why no amount of care inside any one program can stop it.

03 Mechanics

Six problems, and the mechanism that closes each

One row per problem, same college, same student. Two more files join the two from section 02, because the money has to sit somewhere: fees.dat holds Asha’s fee advance and hostel.dat holds her hostel deposit. The middle column is the one that matters and the one candidates skip: it says why a careful programmer cannot fix this from inside the file world. The right-hand column is what you say out loud in an interview, and it is a keyword, not a virtue.

Problem	In our two files	Why being careful does not fix it	The mechanism, named
1 · Redundancy and inconsistency	`the address is in admissions.dat bytes 34..73 and library.dat bytes 4..33`	Nothing on disk says those two byte ranges hold the same fact, so no check can compare them and no error can be raised when they drift apart.	`A single source of truth: one column, and FOREIGN KEY on every table that refers to it`
2 · Difficulty of access, and data isolation	`who has books out and owes advance? no program reads both, and one key is sid, the other member_id`	The layout is compiled into each program, so every new question needs a new program, and that program has to understand every format it touches.	`A query language over a shared schema: SELECT ... FROM student JOIN loan USING (sid)`
3 · Integrity problems	`"an advance may never go negative" is an if in the fees program; the accounts import script does not have it`	A rule written in code binds only the code that contains it. A second program, a hand edit or a one-off script walks straight past it.	`Declared constraints: NOT NULL, CHECK (amount >= 0), VARCHAR(60), FOREIGN KEY, tested on every write`
4 · Atomicity problems	`move 5,000 from a 9,000 advance to a 3,000 deposit: debit written, power cut, credit never written, 4,000 + 3,000 = 7,000`	Two writes to two files are two independent events. Nothing on disk marks them as one unit, so a restart has nothing to finish and nothing to undo.	`Transactions: BEGIN ... COMMIT, with log-based recovery at startup. All of it or none of it`
5 · Concurrent-access anomalies	`two clerks open the fees file, both read 9,000, both save their own edit; the second save replaces the first`	A file hands out a copy and records nothing about who is holding one, so it cannot make the second writer wait or tell it the value has moved.	`Locking and isolation levels: the second writer waits for the row, then works from the committed value. Take the lock when you read a value you mean to write back: SELECT ... FOR UPDATE, or one UPDATE that does the arithmetic itself. The cost is real. Waiting is throughput you do not get back, and two transactions that take the same two rows in opposite order deadlock, so the database aborts one and your code has to retry it`
6 · Security problems	`the library program needs one column, so whoever runs it can open library.dat and read every address in it`	The operating system’s unit of protection is a file. There is no way to say “this login may read two of these four fields”.	`GRANT and REVOKE per table and per column, and a view for a slice of rows`

Three of the six close inside the schema definition itself. The other three are one keyword each from whoever connects, and they sit here as comments so you can see where they go. Nothing in this block is a rule you have to remember to call. The declared ones run on every write on their own, and the three you do type are asking the database for a guarantee rather than implementing one.

CREATE TABLE student (  sid      TEXT PRIMARY KEY,  name     TEXT NOT NULL,  address  VARCHAR(60) NOT NULL       -- 3: one width, declared once, for everybody);CREATE TABLE loan (  sid        TEXT PRIMARY KEY REFERENCES student(sid),  -- 1: no second address here  books_out  INT NOT NULL CHECK (books_out >= 0));GRANT SELECT (sid, books_out) ON loan TO librarian;   -- 6: two columns, not a file-- 2: SELECT s.address FROM student s JOIN loan l USING (sid) WHERE l.books_out > 0;-- 4 and 5: BEGIN; two UPDATEs; COMMIT;  -- one unit, and one writer per row

Line 4 replaces two field widths with one. Line 7 is the line that ends problem one: the library’s row holds a sid and a count, and reads the address by joining, so there is no second copy to forget about. Line 8 is the same shape as the “an advance may never go negative” rule from row three, applied here to the book count: one CHECK, sitting in the one place every writer has to pass through. Line 10 is problem six at column granularity, which no file permission can express.

One vendor difference worth naming, because interviewers do. Column-level SELECT grants like line 10 work in PostgreSQL and MySQL. Oracle allows column lists only on INSERT, UPDATE and REFERENCES, so there you create a view over the two columns and grant on the view instead. The mechanism is the same; the syntax is not.

None of the six is closed by your application. Three are declared in the schema and checked on every write; three are guarantees you ask the database for and it delivers. That is the sentence behind all of them: whatever sits beside the data applies to every program, every script and every person who ever connects, including the ones written after you have left.

05 Cheat sheet

The six on one card

Learn it as pairs. Nobody is impressed by the left-hand column on its own, and nobody asks a follow-up when you have already given the right-hand one.

Problem	What it looks like when it bites	The mechanism to name
Redundancy and inconsistency	`one address in two files, updated in one of them`	`one column as the source of truth, FOREIGN KEY on every reference`
Difficulty of access and data isolation	`a new question means a new program`	`a query language over a shared schema, JOIN instead of a new file reader`
Integrity problems	`the rule is an if somebody remembered`	`NOT NULL, CHECK, VARCHAR(n), FOREIGN KEY in the schema`
Atomicity problems	`debit written, credit lost to a power cut`	`BEGIN ... COMMIT, with log-based recovery at startup`
Concurrent-access anomalies	`two writers, last save wins, no error raised`	`row locks and isolation levels, plus SELECT ... FOR UPDATE on a value you will write back; READ COMMITTED is the default in PostgreSQL, Oracle and SQL Server, REPEATABLE READ in MySQL InnoDB`
Security problems	`per file, per operating-system user, all columns or none`	`GRANT and REVOKE per table and column, views for rows`

Six, or seven?Silberschatz lists “difficulty in accessing data” and “data isolation” as separate entries, which is why you will also see this given as a list of seven. They are one wound: the data sits in files that only their own programs can read. Either count is accepted, as long as every item arrives with its mechanism attached.

Two of the six survive perfect codeRedundancy, access, integrity and security are the four a careful team can hold together by convention for a while, at a cost that grows with every program added. Atomicity and concurrency are not like that. A power cut between two writes, and two writers who both read the same value, break programs that contain no bugs at all. That is why transactions and locking are the two you cannot replace with discipline.

The rule has to sit where the data isA CHECK constraint applies to the clerk’s app, the accounts import, and an UPDATE you type by hand at 2am. The same rule written inside the fees program applies to the fees program. That difference is the entire argument, and it is one sentence long.

06 Where & why

Where the six answers actually live

None of the six mechanisms is a diagram from a textbook. Each one is a keyword you can type into a system that is running right now, and an interviewer can hear the difference between a candidate who has typed them and one who has read about them.

PostgreSQL · MySQL

All six, and three of them declared once

FOREIGN KEY closes one, CHECK and NOT NULL close three, GRANT closes six: three declarations you write once and never repeat. The other three you write per statement or per session. BEGIN and COMMIT over a write-ahead log close four, row locks close five, and SELECT with a join closes two. PostgreSQL calls that log the WAL; MySQL InnoDB calls it the redo log. Same job, different word in the interview.

SQLite

One file on disk, and still atomic

SQLite keeps a rollback journal or a WAL file beside the database, so a transfer interrupted by a power cut is undone the next time the file is opened, with no server and no DBA anywhere. Its one trap is that foreign keys are ignored unless the connection runs PRAGMA foreign_keys = ON, which lets problem one back in quietly.

MongoDB

Five of the six, and the first one is your job

You get a query language, one shared store, declared validation rules, per-role access control, atomic single-document writes, and multi-document transactions from version 4.0 onward. What you do not get is a foreign key. Choosing whether the address is embedded in each document or referenced by id is you doing problem one by hand, on every collection, forever.

Excel · CSV

The file-processing system you will meet next month

Two teams keeping the same customer list in two sheets is problem one in the present tense. The rule that a discount is at most forty per cent lives in whoever maintains the sheet, and the only recovery from a half-finished edit is whichever copy somebody happened to email last week. Every argument in this lesson is about a system somebody is running today, not about the 1970s.

Name the mechanism, not the virtue. “A DBMS gives you data consistency” is a sentence anyone can say. “The address is one column, and every table that needs it holds a foreign key instead of a copy, so there is no second copy to go stale” is an answer, and it takes the same amount of breath.

07 Interview questions

What they actually ask

This is usually the second question in a DBMS interview, straight after “what is a DBMS”, and it is usually answered as six memorised nouns. The candidates who get through name the mechanism beside each problem and can produce one concrete failure on demand.

What is a file-processing system?

Records kept in ordinary operating-system files, with application programs that know each file’s layout by heart. Before database systems that is how organisations stored data: the admissions office had its file and its program, the library had its own, and every new requirement got a new file and a new program. Everything that goes wrong follows from where the layout and the rules were kept, which was inside the programs.

List the problems with keeping data in files instead of a database.

Redundancy and inconsistency; difficulty of access and data isolation; integrity problems; atomicity problems; concurrent-access anomalies; security problems. Say each one with its mechanism attached rather than as a list of nouns: a single source of truth with foreign keys, a query language over a shared schema, declared constraints, transactions, locking with isolation levels, and GRANT and REVOKE. Silberschatz splits the second item in two, so you will also see this given as seven.

Redundancy wastes disk space. Is that really the problem?

No, and saying so is what separates a real answer from a recited one. Disk is cheap. The cost is that two copies are allowed to disagree, so updating one of them is a complete, successful, silent operation that leaves the data wrong. No check can catch it, because nothing on disk records that the two fields were ever the same fact.

What does data isolation mean here?

That the data you need for one question is scattered across files in different formats, so no single program can read all of it. In this lesson the admissions file calls the key sid and gives the address 40 bytes; the library file calls it member_id and gives it 30. Any question spanning both needs a program that understands both layouts, which is why it is usually grouped with difficulty of access.

Give me a concrete atomicity problem.

Move 5,000 rupees from a fee advance of 9,000 to a hostel deposit of 3,000, with the two balances in two files. The debit is written, the power goes out, the credit is never written. On restart the files hold 4,000 and 3,000, which is 7,000 where 12,000 was. Each write is correct on its own; there is no correct world in which only the first one happened.

A database server can crash too. Why can it recover when a file system cannot?

Because a database keeps a record of its own intentions and a file system does not. Every transaction is marked in a log as committed or not, and recovery at startup uses that log to decide which changes to keep and which to undo. Two writes to two files leave nothing behind that says they belonged together, so a restart has nothing to reason about and the half-finished state becomes the new truth.

Two programs write the same file at the same time. What exactly goes wrong?

The classic case is a lost update. Both read advance = 9000, one saves 9000 minus 5000 and the other saves 9000 plus 2000, and whichever writes second overwrites the first. Nothing failed and no error was raised. A file hands out a copy and records nothing about who is holding one, so it cannot make the second writer wait; a database can, and SELECT ... FOR UPDATE is how you ask it to.

Locking closes the concurrency problem. What does it cost you?

Waiting, and the risk of deadlock. A row lock makes the second writer sit and wait, so under contention your throughput is set by how long each transaction holds its locks rather than by how fast the machine is. And two transactions that take the same two rows in opposite order each end up holding what the other needs: the database detects that, aborts one with an error, and your code has to be written to retry it. Raising the isolation level buys fewer anomalies and more of both, which is why no mainstream database ships with SERIALIZABLE as its default.

Is a foreign key just documentation?

No, it is a check that runs on every insert, update and delete. loan.sid REFERENCES student(sid) is what turns “the address lives in one place” from a convention into something enforced: you cannot record a loan for a student who does not exist, and you cannot delete the student out from under the loan. Remove it and the single source of truth goes back to being a habit.

File permissions already exist. Why is that not enough security?

Because the operating system protects a file, and a file is the wrong unit. The library’s program needs one column, so whoever runs it can open the whole file and read every field in it, including fields that were never their business. A database grants per table, per column, and through views per row: GRANT SELECT (sid, books_out) ON loan TO librarian. PostgreSQL and MySQL support column-level SELECT; on Oracle you grant on a view instead.

Which of these problems does a DBMS not solve?

Hard

You may not use a database. Using files only, make the 5,000-rupee transfer across fees.dat and hostel.dat atomic with an intentions file, which this lesson has already told you is how a database survives a crash. Give the exact bytes of one record in that file, the exact order of the writes across all three files, and, for each of the three states a startup program can find that record in, what it must do. Then name two guarantees from this lesson that your scheme still does not give you.

Follow-up

Your scheme has to survive a crash landing in the middle of the write to your own extra file, and that single constraint is what decides its format. A half-written intention is worse than no intention at all.

Show the hint

Whatever you write first has to be recognisable as complete or incomplete by a program that was not running when it was written.