Produce a normalised database design for a description of a database, a given set of data, or a given set of tables

8 Database Concepts (Cambridge AS & A Level 9618)

Learning Objective

Produce a normalised database design for a description of a database, a given set of data, or a given set of tables.

Checklist for Exam Questions

• Identify all attributes and the candidate key(s).
• Write down the functional dependencies (FDs) that can be justified from the description.
• Show the table in First Normal Form (1NF) – atomic values only.
• Apply Second Normal Form (2NF) – remove partial dependencies.
• Apply Third Normal Form (3NF) – remove transitive dependencies.
• Confirm BCNF (optional – for further study).
• Label primary keys (PK) and foreign keys (FK) in each resulting table.
• Sketch a simple ER diagram to illustrate the relationships.

1 Information Representation

1.1 Binary, BCD, ASCII/Unicode, Hexadecimal, Two’s‑Complement

• Two’s‑complement – invert bits and add 1 to obtain the negative representation.
• Example: +13 = 0000 1101; -13 = 1111 0011 (invert → 1111 0010, add 1 → 1111 0011).

1.2 Multimedia – Graphics & Sound

• Bitmap (raster) images – stored as a grid of pixels; size = width × height × bits‑per‑pixel.
• Vector images – stored as geometric primitives (lines, curves); scalable without loss.
• Sound sampling – sample rate × bit depth × duration gives data size.

Example calculation: A 44 kHz, 16‑bit mono recording lasting 30 s requires

44 000 samples × 16 bits × 30 s = 21 120 000 bits ≈ 2.65 MB.

1.3 Compression

• Lossless – original data can be perfectly reconstructed (e.g., RLE, Huffman).
• Lossy – some data is discarded for higher compression (e.g., JPEG, MP3).

Run‑Length Encoding (RLE) worksheet

Original string:  AAAA BBB CC DDDDD
RLE output:      4A 3B 2C 5D

2 Communication

2.1 Network Types & Topologies

2.2 Client‑Server vs. Peer‑to‑Peer

• Client‑Server – centralised resources (e.g., web server, database server).
• Peer‑to‑Peer – each node can act as client and server (e.g., file‑sharing).

2.3 Ethernet & CSMA/CD

• Carrier Sense Multiple Access with Collision Detection – stations listen before transmitting; collisions cause a back‑off.

2.4 IP Addressing & Subnetting

Given the network 192.168.12.0/24 and a requirement for 4 sub‑nets, the subnet mask becomes /26 (255.255.255.192). The sub‑net ranges are:

192.168.12.0  – 192.168.12.63
192.168.12.64 – 192.168.12.127
192.168.12.128– 192.168.12.191
192.168.12.192– 192.168.12.255

2.5 Additional Topics

• DNS – translates domain names to IP addresses.
• IPv4 vs. IPv6 – address length (32 bits vs. 128 bits).
• Cloud computing – delivery of services over the Internet.
• Wired vs. wireless – bandwidth, latency, security considerations.

3 Hardware

3.1 Main Components

3.2 Embedded Systems & Sensors/Actuators

• Embedded system – a computer built into a larger device (e.g., microwave controller).
• Sensor – converts a physical quantity to an electrical signal (e.g., temperature sensor).
• Actuator – converts an electrical signal into physical movement (e.g., motor).

3.3 Logic Gates & Circuits (3.2)

Design task: Build a half‑adder using an XOR gate for the sum and an AND gate for the carry. Produce the combined truth table.

4 Processor Fundamentals

4.1 Von Neumann Architecture & F‑E Cycle

• Components: Memory, Control Unit (CU), Arithmetic‑Logic Unit (ALU), Registers, Buses.
• Fetch‑Decode‑Execute (F‑E) cycle – repeated for each instruction:

  1. Fetch: PC (Program Counter) addresses memory; instruction placed in the Instruction Register (IR).
  2. Decode: CU interprets opcode; determines required operands.
  3. Execute: ALU performs operation; result stored in a register or memory.

• Interrupts – external or internal signals that temporarily suspend the current cycle.
• Cache – small, fast memory that stores frequently accessed data/instructions.

4.2 Assembly Language (two‑pass assembler, addressing modes)

Typical instruction format (simplified):

LABEL:   OPCODE   OPERAND1, OPERAND2   ; comment

• Two‑pass assembler:

  1. Pass 1 – builds the symbol table (labels → addresses).
  2. Pass 2 – generates machine code using the table.

• Addressing modes:

  • Immediate – operand is a constant (e.g., LDI R1, #5).
  • Direct – operand is a memory address (e.g., LDA 2000).
  • Indirect – address stored in a register (e.g., LDA (R2)).
  • Indexed – base address + offset (e.g., LDA 100(R3)).

Sample program (adds two numbers stored at 3000h and 3001h, stores result at 3002h)

LDA 3000h        ; load first operand
ADD 3001h        ; add second operand
STA 3002h        ; store result
HLT

4.3 Bit Manipulation

• Shift left (SHL) – multiplies by 2.
• Shift right (SHR) – divides by 2 (logical shift inserts 0).
• Masking – AND with a pattern to isolate bits.
• Set / clear a flag bit:

  ; Set bit 3 of register R0
  ORI R0, #0b00001000
  ; Clear bit 3
  ANDI R0, #0b11110111
  

5 System Software

5.1 Operating System Functions

5.2 Translators

• Assembler – converts assembly language to machine code (one‑to‑one mapping).
• Compiler – translates high‑level language to machine code; performs optimisation.
• Interpreter – executes high‑level code line‑by‑line without producing a standalone executable.

5.3 Integrated Development Environment (IDE) Features

• Source editor with syntax highlighting.
• Debugger (breakpoints, step‑through, watch variables).
• Build tools (make, automatic compilation).
• Version control integration.

6 Security & Data Integrity

6.1 Common Threats

• Malware – viruses, worms, ransomware.
• Unauthorised access – hacking, phishing.
• Data loss – hardware failure, accidental deletion.
• Denial‑of‑service (DoS) attacks.

6.2 Protective Measures

• Firewalls – filter inbound/outbound traffic.
• Antivirus/anti‑malware – signature‑based detection.
• Encryption – symmetric (AES) and asymmetric (RSA) algorithms.
• Authentication – passwords, biometrics, two‑factor.
• Validation & verification – input checking, checksum, parity bits.

6.3 Scenario Question (Practice)

Situation: A school’s student‑record system stores personal details and grades on a shared server. Identify three security controls you would recommend and justify each choice.

1. Role‑based access control – teachers can read/write grades; students can only view their own records.
2. Regular encrypted backups – protects against data loss from hardware failure.
3. SSL/TLS for all web traffic – prevents eavesdropping when users access the system remotely.

7 Database Concepts (continued)

7.1 Relational Model – Key Terminology

7.2 File‑Based vs. Relational Storage (brief comparison)

• Redundancy – Files often duplicate data; relational tables store each fact once.
• Integrity – DBMS enforce PK/FK automatically; files rely on programmer discipline.
• Query capability – SQL enables powerful ad‑hoc queries; file processing usually needs custom programs.
• Scalability & security – DBMS provide transaction control, concurrency handling, and user‑level security.

7.3 Structured Query Language (SQL) – Basic DDL & DML

7.3.1 Data Definition Language (DDL)

CREATE DATABASE University;
CREATE TABLE Student (
StudentID   CHAR(6)   PRIMARY KEY,
StudentName VARCHAR(50) NOT NULL
);
CREATE TABLE Course (
CourseCode  CHAR(6)   PRIMARY KEY,
CourseTitle VARCHAR(100) NOT NULL
);
CREATE TABLE Offering (
CourseCode CHAR(6),
Semester   VARCHAR(10),
Lecturer   VARCHAR(50),
PRIMARY KEY (CourseCode, Semester),
FOREIGN KEY (CourseCode) REFERENCES Course(CourseCode)
);
CREATE TABLE Enrollment (
StudentID  CHAR(6),
CourseCode CHAR(6),
Semester   VARCHAR(10),
Grade      CHAR(2),
PRIMARY KEY (StudentID, CourseCode, Semester),
FOREIGN KEY (StudentID)   REFERENCES Student(StudentID),
FOREIGN KEY (CourseCode, Semester) REFERENCES Offering(CourseCode, Semester)
);

7.3.2 Data Manipulation Language (DML)

INSERT INTO Student VALUES ('1001','Alice Brown');
INSERT INTO Course VALUES ('CS101','Intro to Computing');
INSERT INTO Offering VALUES ('CS101','Fall 2024','Dr. Smith');
INSERT INTO Enrollment VALUES ('1001','CS101','Fall 2024','A');
SELECT s.StudentName, c.CourseTitle, e.Grade
FROM Enrollment e
JOIN Student s   ON e.StudentID   = s.StudentID
JOIN Offering o  ON e.CourseCode  = o.CourseCode
AND e.Semester   = o.Semester
JOIN Course c    ON o.CourseCode  = c.CourseCode
WHERE o.Semester = 'Fall 2024';

7.4 Normalisation – From Un‑Normalised Data to 3NF (and optional BCNF)

7.4.1 Why Normalise?

• Eliminate redundant storage.
• Reduce update, insertion and deletion anomalies.
• Make data integrity easier to enforce.

7.4.2 Normal Forms Required by the Syllabus

1. First Normal Form (1NF) – atomic values only; no repeating groups.
2. Second Normal Form (2NF) – 1NF + no partial dependency of a non‑key attribute on part of a composite PK.
3. Third Normal Form (3NF) – 2NF + no transitive dependency.

BCNF (optional) – every determinant must be a candidate key.

7.4.3 Step‑by‑Step Procedure

1. List all attributes and identify the candidate key(s) of the original (un‑normalised) table.
2. Ensure the table is in 1NF – split any repeating groups or multi‑valued fields.
3. Write down all functional dependencies that can be justified from the description.
4. Apply 2NF – for each composite key, move attributes that depend on only part of the key to a new table.
5. Apply 3NF – remove attributes that depend on other non‑key attributes (transitive dependencies).
6. (Optional) Check BCNF – if a non‑key determinant exists, decompose further.
7. Assign primary keys and foreign keys for every resulting table.

7.4.4 Illustrative Example – University Registration System

Un‑normalised table

Functional Dependencies

• StudentID → StudentName
• CourseCode → CourseTitle
• {CourseCode, Semester} → Lecturer (lecturer can vary each semester)
• {StudentID, CourseCode, Semester} → Grade

Normalisation Result

All tables satisfy 3NF and, because every determinant is a candidate key, they also satisfy BCNF (optional).

ER Diagram (simplified)

7.5 Practice Question – Library Loans

Task: Normalise the following table to BCNF (or 3NF) and list the primary and foreign keys for each resulting table.

Solution steps

1. Candidate key: LoanID.
2. Functional dependencies:

   • LoanID → MemberID, MemberName, BookISBN, BookTitle, Author, LoanDate, DueDate
   • MemberID → MemberName
   • BookISBN → BookTitle, Author

3. 1NF – already atomic.
4. 2NF – no partial dependencies (single‑field PK).
5. 3NF – remove transitive dependencies:

   • Member(MemberID, MemberName)
   • Book(BookISBN, BookTitle, Author)
   • Loan(LoanID, MemberID, BookISBN, LoanDate, DueDate)

6. BCNF – each determinant is a candidate key, so the design is in BCNF.
7. PK/FK summary:

   • Member(PK = MemberID)
   • Book(PK = BookISBN)
   • Loan(PK = LoanID, FK = MemberID → Member, FK = BookISBN → Book)

Apply the same systematic approach for any exam scenario.

8 Action‑Oriented Review Checklist (Cambridge AS & A‑Level Computer Science 9618)

Use this checklist before each revision session to ensure every syllabus point is addressed and reinforced with an active task.