Entity-Relationship (ER) Modeling is a conceptual diagramming technique introduced by Peter Chen in 1976 to visually represent the logical schema of a database. Real-world business data is modeled using entities, attributes, and relationships.
A. Fundamental ER Components
| Component |
ER Symbol |
Definition & Properties |
Database Example |
| Strong Entity |
Single Rectangle |
An autonomous object that possesses its own primary key and exists independently of other entities. |
STUDENT (StudentID, Name, Email) |
| Weak Entity |
Double Rectangle |
An entity that cannot be uniquely identified by its own attributes alone and depends on an identifying relationship with a strong entity. |
DEPENDENT (DepName, Age) dependent on EMPLOYEE |
| Key Attribute |
Underlined Oval |
An attribute whose values are uniquely distinct for each entity instance in an entity set (forms primary key). |
StudentID in STUDENT |
| Composite Attribute |
Subdivided Ovals |
An attribute that can be divided into smaller sub-parts representing more basic attributes with independent meanings. |
Name (FirstName, MiddleName, LastName) |
| Multivalued Attribute |
Double Oval |
An attribute that may hold a set of values for a single entity instance. Violates 1NF if kept in table. |
PhoneNumbers {9876543210, 8765432109} |
| Derived Attribute |
Dashed Oval |
An attribute whose value is computed dynamically from another stored attribute. |
Age calculated from DateOfBirth |
B. Cardinality Ratios & Participation Constraints
Relationship cardinalities define the number of entity instances to which another entity instance can be associated:
- One-to-One (1:1): Each instance of entity A is related to at most one instance of entity B (e.g.,
CITIZEN and PASSPORT). Handled by placing the foreign key in either table with a UNIQUE constraint.
- One-to-Many (1:N): An instance of entity A can be associated with multiple instances of entity B, but entity B relates to only one instance of A (e.g.,
DEPARTMENT to EMPLOYEES). Handled by placing the primary key of A as a foreign key inside table B.
- Many-to-Many (M:N): An instance of A can relate to multiple instances of B, and vice versa (e.g.,
STUDENTS and COURSES). Cannot be represented in a single relational table; requires a junction/bridge table containing composite primary keys.
- Total Participation (Double Line): Every entity in the set must participate in at least one relationship instance (existence dependency).
- Partial Participation (Single Line): Some entities in the set may not participate in any relationship instance.
C. Relational Normalization Invariants (1NF, 2NF, 3NF, BCNF)
Database normalization systematically decomposes tables to eliminate data redundancy, update anomalies, insertion anomalies, and deletion anomalies while preserving functional dependencies and lossless joins:
| Normal Form |
Core Requirement / Invariant |
Anomaly Prevented |
Resolution Technique |
| 1NF (First Normal Form) |
All attributes must contain only atomic (indivisible) values. No multivalued attributes, repeating groups, or nested tables allowed. |
Inability to index or query specific multi-item values cleanly. |
Split multivalued columns into separate rows or create a separate child table linked by a foreign key. |
| 2NF (Second Normal Form) |
Must be in 1NF, and no partial dependency may exist: every non-prime attribute must be fully functionally dependent on the entire composite primary key. |
Redundant attribute storage across multiple rows sharing a sub-key. |
Decompose into two relations: move attributes depending on only part of the primary key into their own table. |
| 3NF (Third Normal Form) |
Must be in 2NF, and no transitive dependency may exist: non-prime attributes must not depend on other non-prime attributes (\(X \to Y \to Z\) where \(Z\) is non-prime). |
Update anomalies where changing an indirect attribute requires updating thousands of rows. |
Extract transitive attribute pairs (\(Y \to Z\)) into a separate lookup table with \(Y\) as primary key and foreign key reference. |
| BCNF (Boyce-Codd Normal Form) |
For every non-trivial functional dependency \(X \to Y\), the determinant \(X\) must be a Superkey of the relation. |
Anomalies arising when a prime attribute is functionally dependent on a non-candidate key. |
Decompose relation into \(R_1(X, Y)\) and \(R_2(R - Y)\). |
Structured Query Language (SQL) is a declarative programming language designed for managing data in relational database management systems (RDBMS). Unlike imperative languages, SQL specifies what data to retrieve, while the database query planner (cost-based optimizer) determines how to execute the query.
A. Logical Query Processing Order
While written beginning with SELECT, an RDBMS evaluates clauses in a strict logical sequence:
Standard Logical Evaluation Order:
1. FROM & JOIN: Evaluates cartesian products, executes join conditions, and constructs intermediate virtual tables.
2. WHERE: Applies row-level boolean predicates to filter individual tuples. Cannot filter aggregate results.
3. GROUP BY: Partitions remaining rows into disjoint grouping buckets based on grouping columns.
4. HAVING: Applies group-level filters on aggregate functions (e.g. COUNT(*) > 5).
5. SELECT: Projects specified output columns, evaluates scalar expressions, and assigns column aliases.
6. DISTINCT: Eliminates duplicate tuples from the projected result set.
7. ORDER BY: Sorts output rows according to collation rules. Can reference aliases assigned in SELECT.
8. LIMIT / OFFSET: Restricts the total number of returned rows.
B. SQL Joins Comparison Matrix
| Join Type |
Relational Algebra Equivalent |
Result Set Inclusion Rules |
NULL Values Handling |
INNER JOIN |
Natural Join / Equi-Join (\(R \bowtie S\)) |
Returns only tuples where the join predicate evaluates to TRUE in both tables. |
Rows with non-matching or NULL join keys are completely excluded. |
LEFT OUTER JOIN |
Left Outer Join (\(R ⟕ S\)) |
Returns all rows from the left table, along with matched columns from the right table. |
Right table columns evaluate to NULL if no match exists in the right table. |
RIGHT OUTER JOIN |
Right Outer Join (\(R ⟖ S\)) |
Returns all rows from the right table, along with matched columns from the left table. |
Left table columns evaluate to NULL if no match exists in the left table. |
FULL OUTER JOIN |
Full Outer Join (\(R ⟗ S\)) |
Returns rows when there is a match in either the left or right table. |
Missing values from either side are padded with NULL. |
CROSS JOIN |
Cartesian Product (\(R \times S\)) |
Returns every possible combination of rows between both tables (produces \(|R| \times |S|\) rows). |
No join condition required; produces combinatorial multiplication. |
C. Database Indexing & B+ Trees
Without an index, querying an unsorted table requires a Full Table Scan (Sequential Scan) with time complexity \(O(N)\). Relational databases employ B+ Tree indexes to accelerate searches:
- Self-Balancing Structure: All leaf nodes reside at the exact same depth. Internal nodes contain only keys and child pointers, maximizing fan-out (order \(M\)) and minimizing disk I/O operations.
- Search Complexity: Finding any single key requires \(O(\log_M N)\) node accesses, where \(M\) is typically between 100 and 500 in database disk block pages.
- Range Query Efficiency: All leaf nodes are linked sequentially via a bidirectional linked list, allowing efficient execution of range queries (e.g.
WHERE age BETWEEN 20 AND 30) by finding the lower bound in \(O(\log N)\) and scanning along the leaf chain.
An IPv4 Address is a 32-bit binary number traditionally represented as four 8-bit decimal octets separated by dots (e.g. 192.168.1.1). Classless Inter-Domain Routing (CIDR) replaced legacy class-based addressing (Class A, B, C) by using an explicit prefix length notation (\(/n\)) indicating the number of contiguous leading bits assigned to the Network ID.
A. Mathematical Formulas for Subnet Calculation
Given a 32-bit IPv4 address with CIDR prefix length \(n\) (where \(0 \le n \le 32\)):
• Host Bits: \(h = 32 - n\)
• Total IP Addresses in Subnet: \(N_{\text{total}} = 2^h = 2^{(32 - n)}\)
• Usable Host Addresses: \(N_{\text{usable}} = 2^h - 2 = 2^{(32 - n)} - 2\) (except for \(/31\) and \(/32\) special point-to-point links).
• Subnet Mask: An octet string with \(n\) contiguous leading 1 bits and \(32 - n\) trailing 0 bits.
• Network Address (Network ID): Computed by taking the bitwise binary AND of the IP address and the Subnet Mask.
• Directed Broadcast Address: Computed by setting all \(h\) host bits in the Network Address to binary 1.
B. Step-by-Step Worked Subnetting Problem
Problem: Determine the Network ID, Subnet Mask, First Usable Host, Last Usable Host, and Directed Broadcast Address for the host IP 172.16.45.130/26.
Step 1: Determine Prefix and Host Bits:
\(n = 26 \implies h = 32 - 26 = 6\) host bits.
Step 2: Calculate Total and Usable Hosts:
\(N_{\text{total}} = 2^6 = 64\) addresses per subnet block.
\(N_{\text{usable}} = 64 - 2 = 62\) usable hosts.
Step 3: Calculate Subnet Mask:
26 ones = 11111111.11111111.11111111.11000000 \(\implies\) 255.255.255.192.
Step 4: Determine Subnet Boundaries:
Block size in the 4th octet = \(256 - 192 = 64\).
Subnet multiples: \(0, 64, 128, 192\).
Since 4th octet is \(130\), it falls into the block starting at \(128\):
• Network Address: 172.16.45.128
• First Usable Host: 172.16.45.129
• Last Usable Host: 172.16.45.190
• Broadcast Address: 172.16.45.191
The Transmission Control Protocol (TCP) is a connection-oriented, byte-stream transport protocol operating at Layer 4 of the OSI model. It guarantees in-order delivery, error detection, data retransmission, flow control, and congestion mitigation across unreliable IP networks.
A. TCP 3-Way Handshake (Connection Establishment)
Before transferring application data (such as HTTP), a client and server synchronize sequence numbers through a 3-step handshake:
| Step |
Sender → Receiver |
Flags Set |
Sequence & Acknowledgment Numbers |
State Transition |
| 1 |
Client → Server |
SYN = 1 |
Seq = J (Client Initial Sequence Number - ISN) |
Client: CLOSED → SYN_SENT Server: LISTEN → SYN_RCVD |
| 2 |
Server → Client |
SYN = 1, ACK = 1 |
Seq = K (Server ISN), Ack = J + 1 |
Server remains in SYN_RCVD Client enters ESTABLISHED |
| 3 |
Client → Server |
ACK = 1 |
Seq = J + 1, Ack = K + 1 |
Server enters ESTABLISHED. Connection is live and ready for data. |
B. TCP 4-Way Teardown & the TIME_WAIT State
Because TCP connections are full-duplex (data can flow in both directions simultaneously), each transmission direction must be closed independently:
- Step 1: Active closer sends a
FIN segment indicating it has finished sending data. Enters FIN_WAIT_1.
- Step 2: Passive receiver replies with an
ACK and enters CLOSE_WAIT. Active closer enters FIN_WAIT_2.
- Step 3: Once the passive receiver has finished transmitting remaining buffers, it sends its own
FIN segment and enters LAST_ACK.
- Step 4: Active closer sends a final
ACK and transitions into the TIME_WAIT state for a period of \(2 \times \text{MSL}\) (Maximum Segment Lifetime, typically 60 to 120 seconds).
Why is the TIME_WAIT state essential?
1. Ensures Reliable Final ACK Delivery: If the active closer's final ACK is lost in transit, the passive side retransmits its FIN. If the closer had immediately closed, it would reply with an error (RST), causing an abnormal connection abort.
2. Prevents Delayed Duplicate Packet Confusion: It guarantees that any delayed duplicate packets still traveling across the network expire before a new socket connection can be instantiated with the identical four-tuple (Source IP, Source Port, Dest IP, Dest Port).
The Domain Name System (DNS) is a distributed, hierarchical naming database that translates human-readable domain names (e.g. vab-code.in) into machine-routable IP addresses (e.g. 199.36.158.100).
A. The 4-Tier DNS Server Hierarchy
| Tier Level |
Server Designation |
Responsibility & Scope |
Global Example |
| 1 |
Recursive Resolver (Local DNS) |
First point of contact for client devices. Checks local cache; if missing, initiates resolution chain on behalf of client. |
ISP DNS, Google DNS (8.8.8.8), Cloudflare (1.1.1.1) |
| 2 |
Root Nameservers (.) |
Directs resolvers to Top-Level Domain (TLD) servers based on the domain extension. Operated by 12 independent organizations across 13 root letter clusters (A to M). |
a.root-servers.net to m.root-servers.net |
| 3 |
TLD Nameservers |
Manages records for generic TLDs (.com, .org) and country-code TLDs (.in, .uk). Returns NS records for authoritative nameservers. |
Verisign (.com), National Internet Exchange of India (.in) |
| 4 |
Authoritative Nameservers |
Final stop in the resolution query. Holds the actual Resource Records configured by domain owner and returns the definitive IP address. |
Cloudflare DNS, Route53, Firebase Hosting NS |
B. Essential DNS Resource Record (RR) Types
| Record Type |
Binary Code |
Record Value Description |
Production Syntax Example |
A |
Type 1 |
Maps a hostname to an IPv4 32-bit address. |
vab-code.in. 300 IN A 199.36.158.100 |
AAAA |
Type 28 |
Maps a hostname to an IPv6 128-bit address. |
vab-code.in. 300 IN AAAA 2606:4700::6810:85e5 |
CNAME |
Type 5 |
Canonical Name alias: maps an alias domain name to a canonical domain name. |
www.vab-code.in. 300 IN CNAME vab-code.in. |
MX |
Type 15 |
Mail Exchange: specifies mail server responsible for receiving emails for domain, ordered by priority preference. |
vab-code.in. 300 IN MX 10 mail.vab-code.in. |
NS |
Type 2 |
Name Server: delegates a DNS zone to use specific authoritative nameservers. |
vab-code.in. 86400 IN NS ns1.cloudflare.com. |
TXT |
Type 16 |
Arbitrary text data used for domain ownership verification, SPF, DKIM, and DMARC email security. |
vab-code.in. 300 IN TXT "v=spf1 include:_spf.google.com ~all" |