BSc CSIT (TU) Science Database Management System (BSc CSIT, CSC260) Question Paper 2080 Nepal

The Entity-Relationship (ER) Model

The ER model, proposed by Peter Chen (1976), is a high-level conceptual data model that describes the structure of a database in terms of entities, their attributes, and the relationships among them. It is a graphical, DBMS-independent way to design a database before mapping it to a logical schema (tables).

Building Blocks

1. Entities and Entity Sets

An entity is a real-world object that is distinguishable from others (e.g., a particular student Ram). An entity set is a collection of similar entities (e.g., STUDENT). It is shown as a rectangle.

• Strong entity: has its own primary key (e.g., STUDENT, COURSE).
• Weak entity: cannot be uniquely identified by its own attributes and depends on an owner entity; drawn as a double rectangle (e.g., DEPENDENT of an instructor).

2. Attributes

Properties that describe an entity, shown as ellipses:

3. Relationships

An association among entities, shown as a diamond. Cardinality describes how many entities participate:

• 1:1 – one student heads one club.
• 1:N – one department offers many courses.
• M:N – many students enroll in many courses.

Participation can be total (double line, every entity must participate) or partial (single line).

ER Diagram for a University Database (described)

Entities and their key attributes:

• STUDENT ( StudentID, Name(First,Last), DOB, derived Age, multivalued Phone )
• COURSE ( CourseID, Title, Credits )
• INSTRUCTOR ( InstID, Name, Salary )
• DEPARTMENT ( DeptID, DName )
• DEPENDENT (weak: Name) of INSTRUCTOR

Relationships:

• STUDENT —< Enrolls (M:N, with attribute Grade) >— COURSE
• INSTRUCTOR —< Teaches (1:N) >— COURSE
• DEPARTMENT —< Offers (1:N) >— COURSE
• DEPARTMENT —< Employs (1:N) >— INSTRUCTOR
• INSTRUCTOR ═< Has (1:N, identifying) >═ DEPENDENT (weak)

[STUDENT] >===<Enrolls(Grade)>===< [COURSE] >---<Teaches>--- [INSTRUCTOR]
                                      |                          |
                                  <Offers>                   <Employs>
                                      |                          |
                                 [DEPARTMENT] -----------------+ 
                                                           [DEPENDENT]==<Has>==(weak)

This ER design captures the rules of the university and is later reduced to relational tables.

Reducing an ER Diagram to Relational Tables

After conceptual design, each component of the ER diagram is mapped to relations (tables) using the following systematic rules.

1. Strong (Regular) Entity Set

Create one table with all simple attributes as columns; the entity's key becomes the primary key.

STUDENT(StudentID PK, Name, DOB)

2. Weak Entity Set

Create a table containing the weak entity's attributes plus the primary key of the owner as a foreign key. The primary key = {owner PK + partial/discriminator key}.

DEPENDENT(InstID FK, DepName, Relationship)  -- PK = (InstID, DepName)

3. Composite Attributes

Store only the leaf (component) attributes as separate columns; the composite itself is dropped. Name(First, Last) → columns FirstName, LastName.

4. Multivalued Attributes

Create a separate table holding the owner's PK plus the multivalued attribute; PK = both columns together.

STUDENT_PHONE(StudentID FK, Phone)  -- PK = (StudentID, Phone)

5. Derived Attributes

Not stored; computed when needed (e.g., Age from DOB).

6. 1:1 Relationship

Add the PK of one entity as a foreign key into the other table (preferably on the total-participation side); add relationship attributes there.

EMPLOYEE(EmpID PK, ..., MgrOfDeptID FK)

7. 1:N Relationship

Post the "1" side's primary key as a foreign key into the "N" side table; relationship attributes go to the N-side table. No new table is needed.

COURSE(CourseID PK, Title, DeptID FK)   -- DEPARTMENT offers COURSE (1:N)

8. M:N Relationship

Create a new junction table containing the primary keys of both participating entities (as foreign keys) plus any relationship attributes. PK = combination of both keys.

ENROLLS(StudentID FK, CourseID FK, Grade)  -- PK = (StudentID, CourseID)

9. N-ary Relationship

Create a table with the PKs of all participating entities as a composite key, plus descriptive attributes.

10. Generalization / Specialization

• ER-style: table for superclass + table for each subclass (subclass holds superclass PK).
• Single-table: one table with all attributes + a type discriminator.

Applying these rules converts the conceptual ER schema into a complete, redundancy-controlled relational schema.

Normalization

Normalization is the process of organizing the attributes and relations of a database to minimize data redundancy and eliminate anomalies (insertion, update, deletion). It decomposes a poorly structured ("un-normalized") relation into smaller, well-structured relations based on functional dependencies (FDs) and candidate keys, while preserving information (lossless join) and dependencies.

First Normal Form (1NF)

Rule: Every attribute must contain only atomic (single, indivisible) values — no repeating groups or multivalued attributes.

After 1NF:

Second Normal Form (2NF)

Rule: Be in 1NF and have no partial dependency — i.e., no non-prime attribute depends on only part of a composite primary key.

Relation STUDENT_COURSE(StudentID, CourseID, StudentName, Marks) with PK (StudentID, CourseID). Here StudentName depends only on StudentID (partial dependency). Decompose:

STUDENT(StudentID PK, StudentName)
SC(StudentID, CourseID, Marks)   PK=(StudentID,CourseID)

Third Normal Form (3NF)

Rule: Be in 2NF and have no transitive dependency — no non-prime attribute depends on another non-prime attribute.

STUDENT(StudentID, DeptID, DeptName): StudentID → DeptID → DeptName, so DeptName transitively depends on the key. Decompose:

STUDENT(StudentID PK, DeptID FK)
DEPARTMENT(DeptID PK, DeptName)

Why Normalization is Necessary

• Eliminates redundancy → saves storage and avoids inconsistent duplicate data.
• Avoids update anomaly — a fact stored once need not be updated in many rows.
• Avoids insertion anomaly — can store an entity without unrelated data.
• Avoids deletion anomaly — deleting a row does not lose unrelated facts.
• Improves data integrity and consistency and yields a cleaner logical design.

Data redundancy is the unnecessary repetition of the same data in multiple places within a database. It wastes storage and, more seriously, leads to inconsistency and anomalies: if a duplicated value is updated in one place but not the others (update anomaly), the data becomes contradictory.

How normalization reduces it: Normalization decomposes a relation that contains redundant data into smaller relations based on functional dependencies, so that each fact is stored exactly once. For example, repeating DeptName against every employee is removed by splitting into EMPLOYEE(EmpID, DeptID) and DEPARTMENT(DeptID, DeptName), where the department name is stored only once and referenced by a foreign key. Removing partial and transitive dependencies (2NF, 3NF) thus eliminates the duplication and the resulting insertion, update, and deletion anomalies.

Multivalued Dependency (MVD)

A multivalued dependency $X \twoheadrightarrow Y$ holds in a relation when, for each value of $X$, there is a set of values of $Y$ that is independent of the other attributes ($Z$). In other words, $Y$ and $Z$ are independent multivalued facts about the same $X$. MVDs cause redundancy that FDs alone cannot describe.

Example: STUDENT(SID, Course, Hobby) — a student's courses and hobbies are unrelated, so SID \twoheadrightarrow Course and SID \twoheadrightarrow Hobby. This forces a cross-product of courses and hobbies, creating redundant rows.

Fourth Normal Form (4NF)

A relation is in 4NF if it is in BCNF and, for every non-trivial multivalued dependency $X \twoheadrightarrow Y$, $X$ is a superkey. 4NF removes redundancy caused by multiple independent multivalued attributes.

Decomposition of the example:

STUDENT_COURSE(SID, Course)
STUDENT_HOBBY(SID, Hobby)

This eliminates the spurious combinations and the redundancy.

Join

A join is a relational operation that combines rows from two (or more) tables based on a related column (usually a primary key–foreign key match), producing a single result set.

Inner Join

Returns only the rows that have matching values in both tables; non-matching rows are excluded.

SELECT s.Name, c.Title
FROM Student s
INNER JOIN Enroll e ON s.SID = e.SID
INNER JOIN Course c ON e.CID = c.CID;

Outer Join

Returns matching rows plus unmatched rows from one or both tables, filling missing columns with NULL.

• LEFT OUTER JOIN – all rows of the left table + matches from the right.
• RIGHT OUTER JOIN – all rows of the right table + matches from the left.
• FULL OUTER JOIN – all rows from both tables.

SELECT s.Name, e.CID
FROM Student s
LEFT OUTER JOIN Enroll e ON s.SID = e.SID;  -- students with no enrollment show NULL

Difference: an inner join keeps only matched rows, whereas an outer join also preserves the unmatched rows from the preserved side(s) using NULLs.

Strong vs. Weak Entity

Summary: A strong entity is uniquely identifiable on its own, while a weak entity cannot exist or be identified without its associated strong (owner) entity; its full key is formed by combining the owner's primary key with its own discriminator.

File System vs. DBMS

Summary: A file system stores data in flat OS files with logic embedded in application programs, leading to redundancy, inconsistency, and poor sharing. A DBMS is centralized software providing controlled redundancy, integrity, security, concurrency, recovery, and data independence.

Roles of a Database Administrator (DBA)

The DBA is the person responsible for the overall management, design, and control of the database system. Key roles:

1. Schema definition – designs the conceptual/logical schema and storage structure using the DDL.
2. Storage structure & access-method definition – decides physical organization and indexes for performance.
3. Granting authorization & security – creates users and assigns access privileges (GRANT/REVOKE), enforcing data security and privacy.
4. Integrity-constraint specification – defines and enforces rules to maintain data accuracy and consistency.
5. Backup and recovery – plans periodic backups and restores the database after failures.
6. Performance monitoring & tuning – monitors usage and reorganizes/optimizes the database (indexing, query tuning).
7. Concurrency control & maintenance – manages multi-user access, applies patches/upgrades, and routine maintenance.

In short, the DBA ensures the database remains available, secure, consistent, and efficient.

Types of Database Users

1. Naive / Parametric (End) users – interact through ready-made application interfaces (e.g., a bank teller, ATM user) without knowing the underlying database; they only invoke pre-written transactions.
2. Application programmers – professional developers who write application programs (in host languages with embedded SQL) that access and manipulate the database.
3. Sophisticated users – analysts, engineers, and scientists who interact directly using a query language (SQL) or analytics/reporting tools, without writing full programs.
4. Specialized users – write specialized database applications such as CAD, GIS, expert systems, or knowledge bases that do not fit the traditional data-processing model.
5. Database Administrator (DBA) – has central control over the database: defines the schema, manages security, integrity, backup/recovery, and tuning.

Thus database users range from non-technical end users to highly technical DBAs.

Primary Key vs. Candidate Key vs. Foreign Key

Example: In STUDENT(SID, Email, Name, DeptID), both SID and Email are candidate keys; SID is chosen as the primary key; DeptID is a foreign key referencing DEPARTMENT(DeptID).

Summary: Candidate keys are all possible minimal unique identifiers; the primary key is the selected one (no NULLs); a foreign key creates a link to another relation's primary key and enforces referential integrity.

Weak Entity Set

A weak entity set is an entity set that does not have a primary key (sufficient attributes) of its own and therefore cannot be uniquely identified by its own attributes alone. Its existence depends on an associated owner (strong/identifying) entity set through an identifying relationship, and it participates totally in that relationship.

• A weak entity has only a partial key (discriminator) that distinguishes its instances within a given owner.
• Its full primary key = owner's primary key + partial key.
• Notation: double rectangle (entity), double diamond (identifying relationship), double line (total participation).

Example: DEPENDENT(Name, Relationship) of an EMPLOYEE. Two employees may each have a dependent named "Sita", so Name alone is not unique. The partial key Name combined with the owner EmpID gives the full key:

DEPENDENT(EmpID FK, Name, Relationship)   -- PK = (EmpID, Name)

Without the parent EMPLOYEE, a DEPENDENT cannot exist or be identified.