GATE databases: syllabus map and strategy

GATE examines databases in two of its papers. In the Computer Science and Information Technology paper (CS), databases is Section 9 of the syllabus: the ER model; the relational model with relational algebra, tuple calculus and SQL; integrity constraints and normal forms; file organisation and indexing, with B and B+ trees as the named example; and transactions with concurrency control. In the Data Science and Artificial Intelligence paper (DA), Section 5, “Database Management and Warehousing”, repeats most of that list, leaves out transactions and concurrency control, and adds data types, data transformation and data-warehouse modelling. This lesson maps every one of those topics to the lessons of this track, explains how the paper is marked, works out exactly when answering a question you are unsure of raises your expected score, and ends with a revision plan built on spaced reviews and timed practice sets.

Every syllabus topic and where it is taught

The CS syllabus names eleven topics in five short sentences. The DA syllabus names twelve, in one long sentence of its Section 5:

ER-model, relational model: relational algebra, tuple calculus, SQL, integrity constraints, normal form, file organization, indexing, data types, data transformation such as normalization, discretization, sampling, compression; data warehouse modelling: schema for multidimensional data models, concept hierarchies, measures: categorization and computations.

The list gives the fourteen topics in the order of the CS list, with the three that only DA names at the end: the papers that name each topic, where this track teaches it, and what you should be able to do. Where a topic’s lessons are still to come, the link goes to its module on the track page, which lists them.

• ER model (CS, DA): Conceptual design with the ER model. Draw entities, relationships, cardinality and participation, and map a diagram to the fewest tables.
• Relational model (CS, DA): Relations, tuples and domains and Keys. Tell a relation from a table, find candidate keys and count superkeys.
• Relational algebra (CS, DA): The six core operators, Joins and join sizes and Division and extended algebra. Evaluate an expression by hand, bound the size of a join, and write “for all” with division.
• Tuple calculus (CS, DA): Tuple and domain relational calculus. Translate between calculus and algebra, and recognise an unsafe expression.
• SQL (CS, DA): Logical evaluation order, NULL and three-valued logic, GROUP BY and HAVING, Subqueries and the rest of the SQL semantics module. Predict the exact result of a query with NULLs, duplicates, groups and subqueries.
• Integrity constraints (CS, DA): Integrity constraints and foreign keys. Say which change a key, foreign key or CHECK constraint rejects, and what ON DELETE does.
• Normal forms (CS, DA): the functional dependencies and normal forms modules. Compute closures and candidate keys, name the highest normal form, and decompose without losing information.
• File organisation (CS, DA): Storage and file organisation. Compute records per block and blocks per file, and compare heap, sorted and hashed files.
• Indexing (CS, which names B and B+ trees; DA): Indexing. Work out the order and height of a B+ tree, trace its splits, and count the block reads of a search.
• Transactions (CS): Transactions and schedules. Test a schedule for conflict and view serializability and for recoverability.
• Concurrency control (CS): Concurrency control. Decide whether two-phase locking or timestamp ordering allows a schedule.
• Data types (DA): Relations, tuples and domains and Storage engines, NoSQL and analytics. Give each column a type, and tell nominal, ordinal and numeric attributes apart.
• Data transformation (DA): Storage engines, NoSQL and analytics. Rescale, bin, sample and compress a column of values.
• Warehouse modelling (DA): Storage engines, NoSQL and analytics. Draw a star schema, roll a measure up a concept hierarchy, and classify measures as distributive, algebraic or holistic.

Two words in the DA list need care. “Normal form” is schema design, the same topic as the CS paper’s normal forms, while “normalization” sits among data-preparation steps and means rescaling values; the warm-up questions at the end of this lesson come back to it. “Data types” is not defined by the syllabus, so learn both readings: the column types a schema declares, and the kinds of attribute that data analysis distinguishes. The three classes of measure in the last row come from the paper that introduced the data cube operator.

The map as data, checked by a query

A table of links goes stale quietly, when lessons are added or move. So the same map is also kept as data. The program below stores the topics of both syllabi in one table and the lessons that teach them in another, then asks four questions of them. Run it, or change a row and run it again.

-- The databases sections of the CS and DA syllabi, one row per topic, and the lessons of this track that teach
-- each topic. n is the topic's place in the CS list; the three topics only DA names come after it.
CREATE TABLE syllabus (
  paper TEXT NOT NULL CHECK (paper IN ('CS', 'DA')),
  n INTEGER NOT NULL,
  topic TEXT NOT NULL,
  PRIMARY KEY (paper, topic)
);
INSERT INTO syllabus VALUES
  ('CS', 1, 'ER model'), ('CS', 2, 'relational model'), ('CS', 3, 'relational algebra'),
  ('CS', 4, 'tuple calculus'), ('CS', 5, 'SQL'), ('CS', 6, 'integrity constraints'),
  ('CS', 7, 'normal forms'), ('CS', 8, 'file organisation'), ('CS', 9, 'indexing'),
  ('CS', 10, 'transactions'), ('CS', 11, 'concurrency control'),
  ('DA', 1, 'ER model'), ('DA', 2, 'relational model'), ('DA', 3, 'relational algebra'),
  ('DA', 4, 'tuple calculus'), ('DA', 5, 'SQL'), ('DA', 6, 'integrity constraints'),
  ('DA', 7, 'normal forms'), ('DA', 8, 'file organisation'), ('DA', 9, 'indexing'),
  ('DA', 12, 'data types'), ('DA', 13, 'data transformation'), ('DA', 14, 'warehouse modelling');

-- Which lesson teaches which topic. A lesson may teach more than one topic.
CREATE TABLE teaches (topic TEXT NOT NULL, lesson TEXT NOT NULL, PRIMARY KEY (topic, lesson));
INSERT INTO teaches VALUES
  ('ER model', 'er-entities-and-attributes'), ('ER model', 'er-relationships-and-constraints'),
  ('ER model', 'weak-entities-and-eer'), ('ER model', 'er-to-relational-mapping'),
  ('ER model', 'er-design-case-study'),
  ('relational model', 'relations-tuples-and-domains'), ('relational model', 'keys-and-superkeys'),
  ('relational algebra', 'relational-algebra-basics'), ('relational algebra', 'relational-algebra-joins'),
  ('relational algebra', 'division-and-extended-algebra'),
  ('tuple calculus', 'tuple-relational-calculus'),
  ('SQL', 'sql-logical-evaluation-order'), ('SQL', 'null-and-three-valued-logic'),
  ('SQL', 'grouping-and-aggregation-semantics'), ('SQL', 'subqueries-exists-any-all'),
  ('SQL', 'views-and-materialized-views'), ('SQL', 'recursive-queries-and-datalog'),
  ('SQL', 'triggers-procedures-and-functions'), ('SQL', 'access-control-and-sql-injection'),
  ('integrity constraints', 'keys-and-superkeys'), ('integrity constraints', 'integrity-constraints'),
  ('normal forms', 'redundancy-and-anomalies'), ('normal forms', 'functional-dependencies-and-armstrong-axioms'),
  ('normal forms', 'attribute-closure-and-candidate-keys'), ('normal forms', 'canonical-cover-and-fd-equivalence'),
  ('normal forms', 'normal-forms-1nf-2nf-3nf'), ('normal forms', 'bcnf-and-3nf-tradeoff'),
  ('normal forms', 'lossless-join-and-dependency-preservation'),
  ('normal forms', '3nf-synthesis-and-bcnf-decomposition'), ('normal forms', 'multivalued-dependencies-4nf-5nf'),
  ('file organisation', 'storage-media-and-io-costs'), ('file organisation', 'pages-records-and-slotted-pages'),
  ('file organisation', 'file-organisations'),
  ('indexing', 'index-basics'), ('indexing', 'b-trees-and-b-plus-trees'),
  ('indexing', 'b-plus-tree-insertion-and-deletion'), ('indexing', 'b-tree-indexes-in-practice'),
  ('indexing', 'hashing-extendible-and-linear'),
  ('transactions', 'transactions-and-acid'), ('transactions', 'conflict-serializability'),
  ('transactions', 'view-serializability'), ('transactions', 'recoverable-and-cascadeless-schedules'),
  ('transactions', 'isolation-levels-and-anomalies'),
  ('concurrency control', 'two-phase-locking'), ('concurrency control', 'deadlock-handling'),
  ('concurrency control', 'multiple-granularity-and-phantoms'), ('concurrency control', 'timestamp-ordering-and-occ'),
  ('concurrency control', 'mvcc-and-snapshot-isolation'), ('concurrency control', 'ssi-and-concurrency-patterns'),
  ('data types', 'relations-tuples-and-domains'), ('data types', 'data-preprocessing-for-analytics'),
  ('data transformation', 'data-preprocessing-for-analytics'),
  ('warehouse modelling', 'data-warehousing-and-olap');

-- 1. Every topic, the papers that name it, and how many lessons teach it.
SELECT topic,
       CASE WHEN max(paper = 'CS') THEN 'yes' ELSE 'no' END AS in_cs,
       CASE WHEN max(paper = 'DA') THEN 'yes' ELSE 'no' END AS in_da,
       (SELECT count(*) FROM teaches t WHERE t.topic = s.topic) AS lessons
FROM syllabus AS s
GROUP BY topic
ORDER BY min(n);

-- 2. The check: syllabus rows that no lesson teaches (an anti-join). It must be 0.
SELECT count(*) AS topics_without_a_lesson
FROM syllabus AS s
WHERE NOT EXISTS (SELECT 1 FROM teaches AS t WHERE t.topic = s.topic);

-- 3. What one paper names and the other does not.
SELECT topic AS only_in_da FROM syllabus WHERE paper = 'DA'
EXCEPT
SELECT topic FROM syllabus WHERE paper = 'CS'
ORDER BY 1;

SELECT topic AS only_in_cs FROM syllabus WHERE paper = 'CS'
EXCEPT
SELECT topic FROM syllabus WHERE paper = 'DA'
ORDER BY 1;

┌───────────────────────┬───────┬───────┬─────────┐
│         topic         │ in_cs │ in_da │ lessons │
├───────────────────────┼───────┼───────┼─────────┤
│ ER model              │ yes   │ yes   │ 5       │
│ relational model      │ yes   │ yes   │ 2       │
│ relational algebra    │ yes   │ yes   │ 3       │
│ tuple calculus        │ yes   │ yes   │ 1       │
│ SQL                   │ yes   │ yes   │ 8       │
│ integrity constraints │ yes   │ yes   │ 2       │
│ normal forms          │ yes   │ yes   │ 9       │
│ file organisation     │ yes   │ yes   │ 3       │
│ indexing              │ yes   │ yes   │ 5       │
│ transactions          │ yes   │ no    │ 5       │
│ concurrency control   │ yes   │ no    │ 6       │
│ data types            │ no    │ yes   │ 2       │
│ data transformation   │ no    │ yes   │ 1       │
│ warehouse modelling   │ no    │ yes   │ 1       │
└───────────────────────┴───────┴───────┴─────────┘
┌─────────────────────────┐
│ topics_without_a_lesson │
├─────────────────────────┤
│ 0                       │
└─────────────────────────┘
┌─────────────────────┐
│     only_in_da      │
├─────────────────────┤
│ data transformation │
│ data types          │
│ warehouse modelling │
└─────────────────────┘
┌─────────────────────┐
│     only_in_cs      │
├─────────────────────┤
│ concurrency control │
│ transactions        │
└─────────────────────┘

The first result is the map at a glance: fourteen topics, the papers that name each one, and how many lessons teach it, from 1 for tuple calculus to 9 for normal forms. Normal forms has the most because the track builds up functional dependencies, closures and covers step by step before it reaches the normal forms themselves.

The second result is the check. It is an anti-join: NOT EXISTS keeps the syllabus rows that no lesson row matches, and their count must be 0. If a topic ever lost its last lesson, the count would rise above 0 on the next run. The subqueries lesson explains why NOT EXISTS is the safe way to write such a check when columns can be NULL.

The last two results use EXCEPT, the set difference of SQL, to list what one paper names and the other does not. DA alone names data types, data transformation and warehouse modelling; CS alone names transactions and concurrency control. A candidate who takes both papers studies the union of the two lists.

How the paper is marked

Every GATE paper has 65 questions worth 100 marks and lasts three hours. Ten of the questions, worth 15 marks, are General Aptitude: five of 1 mark and five of 2 marks. In the CS paper the other 85 marks are the subject, and 13 of them are engineering mathematics; in the DA paper all 85 belong to its subject sections. Each question is worth 1 or 2 marks and has one of three types:

• MCQ, multiple choice: choose the one correct option of four. A wrong answer costs 1/3 of a mark on a 1-mark question and 2/3 of a mark on a 2-mark question.
• MSQ, multiple select: choose every correct option, since one or more of the four are correct. A wrong answer costs nothing, but there are no partial marks: only the exact set of correct options earns the marks.
• NAT, numerical answer: type a signed number with the on-screen keypad; there are no options. A wrong answer costs nothing, and there are no partial marks either.

An unanswered question scores 0, whatever its type. Calculations are done on the on-screen virtual calculator, and the brochure advises rounding a NAT answer only at the end, to the number of decimal places the question asks for.

How many of the subject marks are about databases is not published: the paper pattern gives totals for General Aptitude, engineering mathematics and the subject, and nothing per syllabus section, so this lesson estimates no weights either. One figure is worth keeping instead, because it sets the pace of every practice set: 180 minutes for 100 marks is 1.8 minutes per mark.

When a guess raises your score

Negative marking turns “should I answer this?” into arithmetic. Take an MCQ worth m marks that you would get right with probability p. Answering earns m marks with probability p and loses m/3 with probability 1 − p, so on average it is worth pm − (1 − p)m/3, which simplifies to m(4p − 1)/3. That is zero when p is exactly 1/4 and positive whenever p is larger, whatever the question’s marks. A blind guess among four options has p = 1/4, so it is worth nothing on average; every option you rule out with real knowledge raises p, and with it the value of answering.

-- Expected marks from answering under the paper's marking: a right answer earns the question's marks (m), a wrong
-- MCQ answer costs a third of them, a wrong MSQ or NAT answer costs nothing, and a blank scores 0.
-- If you are right with probability p, an MCQ is worth p*m - (1 - p)*m/3 = m*(4p - 1)/3 on average.

-- 1. A random pick among the k options you have not ruled out: p = 1/k, so the value is m*(4 - k)/(3k).
WITH RECURSIVE options_left(k) AS (SELECT 4 UNION ALL SELECT k - 1 FROM options_left WHERE k > 1)
SELECT m.marks, k AS options_left, '1/' || k AS chance_right,
       round(m.marks * (4 - k) / (3.0 * k), 3) AS expected_marks
FROM (SELECT 1 AS marks UNION ALL SELECT 2) AS m, options_left
ORDER BY m.marks, k DESC;

-- 2. Net marks per MCQ attempted, by accuracy (the share of your attempts that are right).
WITH accuracy(a) AS (VALUES (0.25), (0.4), (0.5), (0.7), (0.9))
SELECT a AS accuracy,
       round((4 * a - 1) / 3, 3) AS per_1_mark_mcq,
       round(2 * (4 * a - 1) / 3, 3) AS per_2_mark_mcq
FROM accuracy;

-- 3. An MSQ with four options has 2^4 - 1 = 15 possible non-empty answers, and a wrong one costs nothing.
SELECT (1 << 4) - 1 AS possible_msq_answers,
       round(1.0 / 15, 3) AS blind_guess_right,
       round(2.0 / 15, 3) AS expected_marks_2_mark_msq;

┌───────┬──────────────┬──────────────┬────────────────┐
│ marks │ options_left │ chance_right │ expected_marks │
├───────┼──────────────┼──────────────┼────────────────┤
│ 1     │ 4            │ 1/4          │ 0.0            │
│ 1     │ 3            │ 1/3          │ 0.111          │
│ 1     │ 2            │ 1/2          │ 0.333          │
│ 1     │ 1            │ 1/1          │ 1.0            │
│ 2     │ 4            │ 1/4          │ 0.0            │
│ 2     │ 3            │ 1/3          │ 0.222          │
│ 2     │ 2            │ 1/2          │ 0.667          │
│ 2     │ 1            │ 1/1          │ 2.0            │
└───────┴──────────────┴──────────────┴────────────────┘
┌──────────┬────────────────┬────────────────┐
│ accuracy │ per_1_mark_mcq │ per_2_mark_mcq │
├──────────┼────────────────┼────────────────┤
│ 0.25     │ 0.0            │ 0.0            │
│ 0.4      │ 0.2            │ 0.4            │
│ 0.5      │ 0.333          │ 0.667          │
│ 0.7      │ 0.6            │ 1.2            │
│ 0.9      │ 0.867          │ 1.733          │
└──────────┴────────────────┴────────────────┘
┌──────────────────────┬───────────────────┬───────────────────────────┐
│ possible_msq_answers │ blind_guess_right │ expected_marks_2_mark_msq │
├──────────────────────┼───────────────────┼───────────────────────────┤
│ 15                   │ 0.067             │ 0.133                     │
└──────────────────────┴───────────────────┴───────────────────────────┘

Read the three results in turn:

1. Ruling options out. Rule out one option and a random pick among the other three is worth +0.111 of a mark on a 1-mark question and +0.222 on a 2-mark question. Rule out two and it is worth a third of the question: +0.333 and +0.667.
2. Accuracy. The second table applies the same formula to your accuracy, the share of your answers that are right. At 70 % accuracy each 1-mark MCQ you attempt is worth 0.6 marks after penalties, and at 50 % it is worth a third of a mark. Attempting stops paying only at 25 %.
3. MSQ and NAT. An MSQ with four options has 15 possible non-empty answers, so even a blind guess is right one time in 15, and a wrong one costs nothing; a wrong NAT answer costs nothing either. Your best attempt at an MSQ or a NAT question can only add marks, so never leave one blank.

Expected value is an average over many questions, not a promise for one, but the rule it gives settles most cases in the exam hall: answer an MCQ when you can honestly rule out at least one option, leave it when you cannot, and answer every MSQ and NAT question.

Here is the arithmetic on one mock. You attempted 14 MCQs, 6 of 1 mark and 8 of 2 marks, and got 4 and 5 of them right. The right answers earn 4 + 10 = 14 marks. The 2 wrong 1-mark answers cost 2/3 of a mark and the 3 wrong 2-mark answers cost 2 marks, so the MCQs scored 14 − 0.67 − 2 = 11.33. Your accuracy was 9 out of 14, about 64 %, far above the 25 % break-even, so attempting all 14 was the right call even though 5 of them were wrong.

A revision plan built on spacing and timed sets

The syllabus falls into four strands, plus the three topics that only DA adds. Inside each strand the topics build on each other, so learn them in the order shown. Across strands the order matters less, apart from keys, which the design strand needs first.

How you revise matters as much as what you revise. A large review of ten common study techniques rated two of them as the most useful: practice testing, which means answering questions rather than reading answers, and distributed practice, which means spreading study over separate sessions. It rated rereading and highlighting low, although most students report relying on them. A meta-analysis of 839 assessments of spacing in 317 experiments found that the gap between sessions that gives the best retention grows as the time you need to remember grows. For an exam some months away, that means short, repeated self-tests at widening gaps, not one long reread at the end.

A plan that follows both findings:

1. Learn a topic, then write questions, not notes. After each lesson, write three to five questions whose answers you have to produce: a closure to compute, a schedule to test, the output of a query to predict.
2. Review on a widening schedule. Answer each question again about one day, three days and a week after you first study the topic, then every two or three weeks until the exam. A question you get wrong starts the schedule again.
3. Add one timed set a week once a strand is learnt. Mix MCQ, MSQ and NAT questions and keep to the paper’s pace of 1.8 minutes a mark: 27 minutes for a 15-mark set.
4. Sort every lost mark by its cause. You did not know it, misread the question, slipped in a calculation, or ran out of time. Each cause has its own fix: a new question, slower reading of the stem, a checking step, or moving on sooner.
5. Score every set with the real marking, so the habit of answering only when your chance beats one in four is practised before the exam rather than discovered in it.

Six weeks of that plan, for a candidate who already knows some SQL, could look like this:

Reviews run every day alongside: 15 to 20 minutes of answering your own questions. With more time, give each strand longer and keep the weekly set; with less, shorten the strands but never drop the reviews.

Exercises

The exercise asks for the marking rule in SQL: one query that turns a table of your answers into a score.

-- One row: how many questions you answered, and your marks under the paper's marking.
SELECT count(*) AS attempted,
       sum(CASE WHEN result = 'right' THEN marks ELSE -marks / 3 END) AS score
FROM responses;

# Sample tests: each one builds a small mock paper, runs your query on it and compares the row it returns.
tests:
  - name: scores a ten-question mock with right, wrong and unanswered questions of every type
    setup: |
      CREATE TABLE responses (q INTEGER PRIMARY KEY, type TEXT NOT NULL, marks INTEGER NOT NULL, result TEXT);
      INSERT INTO responses VALUES
        (1, 'MCQ', 1, 'right'),
        (2, 'MCQ', 1, 'wrong'),
        (3, 'MCQ', 2, 'right'),
        (4, 'MCQ', 2, 'wrong'),
        (5, 'MSQ', 1, 'right'),
        (6, 'MSQ', 2, 'wrong'),
        (7, 'MCQ', 1, 'wrong'),
        (8, 'NAT', 2, 'right'),
        (9, 'MCQ', 1, NULL),
        (10, 'NAT', 2, NULL);
    expected:
      columns: [attempted, score]
      rows:
        - [8, 4.67]
  - name: gives an unanswered paper a score of 0, not NULL
    setup: |
      CREATE TABLE responses (q INTEGER PRIMARY KEY, type TEXT NOT NULL, marks INTEGER NOT NULL, result TEXT);
      INSERT INTO responses VALUES
        (1, 'MCQ', 2, NULL),
        (2, 'MSQ', 1, NULL),
        (3, 'NAT', 2, NULL);
    expected:
      columns: [attempted, score]
      rows:
        - [0, 0]
  - name: charges a third of the marks for wrong MCQs only, never for wrong MSQ or NAT answers
    setup: |
      CREATE TABLE responses (q INTEGER PRIMARY KEY, type TEXT NOT NULL, marks INTEGER NOT NULL, result TEXT);
      INSERT INTO responses VALUES
        (1, 'MCQ', 1, 'wrong'),
        (2, 'MCQ', 2, 'wrong'),
        (3, 'MSQ', 2, 'wrong'),
        (4, 'NAT', 1, 'wrong');
    expected:
      columns: [attempted, score]
      rows:
        - [4, -1]

The quiz is a ten-question mixed sample in the style of the paper: five NAT, three MCQ and two MSQ questions worth 14 marks in all, each labelled with its type and marks. Give it about 25 minutes, the paper’s pace for 14 marks, then score it with the marking above: by hand, with your query from the exercise, or with the calculator.

Interview questions

Fresher · Under negative marking of one third, when does answering an MCQ you are unsure of raise your expected score?

When your chance of being right is greater than one in four. A question worth m marks earns m with probability p and costs m/3 with probability 1 − p, so its expected value is m(4p − 1)/3: zero at p = 1/4 and positive above it, whatever m is. A blind guess among four options sits exactly at 1/4, so it is worth nothing on average. Ruling out one option makes a guess worth 1/9 of a mark on a 1-mark question, and ruling out two makes it worth a third of the question. MSQ and NAT questions carry no negative marking, so answering them never lowers the expected score: never leave one blank.

Fresher · In the DA databases syllabus, does “normalization” mean normal forms?

No. The DA list uses the idea twice, in two senses. “Normal form”, among the relational topics, is schema normalisation: 1NF to BCNF, built on functional dependencies, the same topic as normal forms in the CS syllabus. “Normalization” in “data transformation such as normalization, discretization, sampling, compression” sits with data-preparation steps, so it means rescaling values, for example min-max scaling to the range 0 to 1, or z-scores that subtract the mean and divide by the standard deviation. When a term has two meanings, its neighbours in the list tell you which one is meant.

Key takeaways

• The CS paper’s databases section names eleven topics. The DA paper shares nine of them, leaves out transactions and concurrency control, and adds data types, data transformation and warehouse modelling.
• Every topic maps to lessons of this track, and the map is checked by a query: an anti-join with NOT EXISTS that must count 0.
• A paper is 65 questions, 100 marks and three hours: 1.8 minutes per mark. A wrong MCQ costs a third of its marks, a wrong MSQ or NAT answer costs nothing, and no question gives partial marks.
• An MCQ answer is worth m(4p − 1)/3 on average: answer when your chance of being right beats one in four, and never leave an MSQ or NAT question blank.
• Revise by answering questions at widening gaps and by timed mixed sets scored with the real marking, not by rereading.