Database Management Systems exam preparation.
Practice questions for every unit in the style of the R23 end exam, a model answer for each, and a one-page revision summary. Built on the official syllabus units.
- Practice questions in the exam's style
- Drafted with AI and checked by a second AI pass. Doubtful points were verified against public sources. Report a mistake
- Units
- 5
- Questions
- 60
- 2-mark
- 30
- 10-mark
- 30
- Done
- Checked on
Exam guide
Paper pattern
Semester-end theory paper, 70 marks, from the JNTUK B.Tech R23 Regulations, end-examination pattern for theory subjects.
- Question 1 · 20 marksTen compulsory short-answer questions of 2 marks each (two from every unit).
- Questions 2 to 6 · 50 marksFive either/or questions of 10 marks each, one per unit. You answer one of the two in each.
- The semester-end examination carries 70 marks; internal assessment carries 30.
- Mid-semester examinations are separate: a 20-minute objective paper (10 marks) and a 90-minute subjective paper with three either/or questions of 10 marks (condensed to 15 marks).
- The regulations text does not state the length of the end examination. Use the duration printed on your hall ticket or question paper.
How to split your time
This plan assumes a 3-hour paper. If yours is different, keep the same proportions. Marks per minute stay roughly even across Question 1 and the 10-mark answers.
- 10 minRead the paper and choose one option in each either/or question
- 30 minQuestion 1: ten short answers (about 3 minutes each)
- 130 minQuestions 2 to 6: one 10-mark answer per unit (about 26 minutes each)
- 10 minFinal check of numbering, calculations and diagrams
Study tips for Database Management Systems
- Practise SQL by running it: create two or three small tables, write each query on paper first, then run it and compare the rows you predicted with the rows you get, especially for joins, grouping and nested queries.
- For normalization, work the same few steps every time: compute attribute closures, find every candidate key, then test each functional dependency against 2NF, 3NF and BCNF before you decompose.
- Draw ER diagrams with the standard symbols (rectangle, ellipse, diamond, double lines for total participation) and convert at least one full diagram into relations with their primary and foreign keys.
- For transactions, draw the precedence graph for every schedule you practise, and trace two-phase locking and timestamp ordering step by step, noting where a transaction waits or is rolled back.
Introduction and the Entity-Relationship Model
Syllabus: Database system and its characteristics (database versus file system); Database users; Advantages of database systems; Database applications; Data models: a brief introduction; Schema, instance and data independence; Three-tier schema architecture for data independence; Database system structure and environment; Centralized and client-server architectures for databases; ER model: entities, attributes and entity sets; Relationships, relationship sets and constraints; Subclasses, superclasses and inheritance; Specialization and generalization in ER diagrams
One-page revision summary
- A database is a collection of related data; a DBMS is the software that defines, builds, queries, updates and shares it; together with application programs they form a database system.
- A file-processing system suffers from redundancy and inconsistency, difficult data access, data isolation, integrity, atomicity, concurrent-access and security problems.
- The database approach is self-describing (system catalog), insulates programs from data, supports multiple views and allows shared multiuser transaction processing.
- DBMS advantages: controlled redundancy, restricted access, efficient queries through indexes, backup and recovery, integrity enforcement, multiple interfaces and faster application development.
- Database users: DBA, database designers, end users (casual, naive, sophisticated, standalone), system analysts and application programmers, while DBMS implementers, tool developers and operators build and run the system software.
- The DBA defines the schema and storage structures, grants authorisation, takes backups and monitors performance.
- Databases are used in banking, railway and airline reservation, universities, online shopping, telecommunication, human resources and manufacturing.
- Data models are conceptual (ER model), representational (relational, network, hierarchical) or physical; the relational model stores data as tables of rows and columns.
- A schema is the description of the database and changes rarely; an instance (database state) is the data at one moment and changes often.
- The three-schema architecture has an internal level (physical storage), a conceptual level (whole database for all users) and an external level (user views), linked by two mappings.
- Physical data independence protects the conceptual schema from internal changes; logical data independence protects external schemas from conceptual changes and is harder to achieve.
- The query processor has the DDL interpreter, the DML compiler with its query optimizer, and the query evaluation engine.
- The storage manager has the authorization and integrity manager, transaction manager, buffer manager and file manager; disk storage holds data files, the data dictionary and indices.
- In a centralized architecture everything runs on one computer; in two-tier client-server the client runs the application; in three-tier an application server holds the business rules.
- An entity is a distinguishable real-world object, an entity set is a collection of entities of the same type, and attributes may be simple or composite, single-valued or multivalued, stored or derived.
- A relationship set has a degree (binary, ternary), may be recursive with role names, may carry attributes and is constrained by cardinality ratio and participation.
- A weak entity set has no key of its own; it is identified by its owner's key plus a partial key, through an identifying relationship with total participation.
- A subclass is linked to its superclass by an IS-A relationship and inherits all the superclass's attributes and relationships, adding local attributes of its own.
- Specialization is top-down and generalization is bottom-up; their constraints are disjoint or overlapping, and total or partial.
- ER notation on paper: entity set as rectangle, attribute as ellipse, relationship set as diamond, multivalued attribute as double ellipse, weak entity as double rectangle, total participation as double line.
Learn these by heart
- Data independence: a schema at one level can change without forcing a change in the schema at the level above; only the mapping between the two changes.
- Three levels of the three-schema architecture: internal, conceptual and external, with external/conceptual and conceptual/internal mappings.
- Cardinality ratios of a binary relationship set: 1:1, 1:N, N:1 and M:N.
- Total participation (double line): every entity takes part; partial participation (single line): only some entities take part.
- A weak entity is identified by the owner's key plus its own partial key (discriminator).
- Specialization constraints: disjoint (d) or overlapping (o), and total or partial, giving four combinations.
2-mark questions
1 Define a database and a database management system (DBMS). Name any four applications of databases. 2 marks
A database is a collection of related data that is stored permanently, organised for easy retrieval and shared by many users. A DBMS is the software that lets users define, create, query, update and protect a database. Applications include banking, railway and airline reservation, university student records and online shopping.
2 What is a data model? Name its main categories. 2 marks
A data model is a set of concepts used to describe how a database is structured: what data it holds, how the data items are related, what they mean and which constraints they must satisfy. By level of abstraction the categories are conceptual or high-level (ER model), representational or implementation (relational, network, hierarchical) and physical or low-level (storage details).
3 Distinguish between a database schema and a database instance. 2 marks
A schema is the description of the database: its record types, fields, data types and constraints. It is fixed at design time and changes rarely. An instance (database state) is the data stored at one moment; it changes with every insertion, deletion or update. Example: STUDENT(roll_no, name, branch) is a schema, and today's student rows form an instance.
4 Differentiate between two-tier and three-tier client-server architectures for databases. 2 marks
In a two-tier architecture the client runs the user interface and application programs and sends queries to the database server through an interface such as ODBC or JDBC. A three-tier architecture adds an application (web) server in the middle: the client only presents data, the middle tier holds the business rules, and only it talks to the database server.
5 Distinguish between composite and multivalued attributes, with an example of each. 2 marks
A composite attribute can be divided into smaller meaningful parts, for example address into door_no, street, city and pin_code. A multivalued attribute can hold several values for one entity, for example a student's phone numbers. In an ER diagram a composite attribute's parts are ellipses joined to it, and a multivalued attribute is a double ellipse.
6 What is a weak entity set? How are its entities identified? 2 marks
A weak entity set has no key attribute of its own. Each weak entity is identified by its owner entity's key plus its partial key (discriminator). Example: room 101 exists in every hostel block, so a ROOM is identified by block_id plus room_no. It is drawn as a double rectangle and its identifying relationship as a double diamond.
10-mark questions
1 What is a database system? Compare the database approach with the traditional file-processing system, and explain the main characteristics and advantages of the database approach. 10 marks
A database system consists of a database (a collection of related data), the DBMS software that manages it and the application programs that use it. Before DBMSs, an organisation kept its data in separate files, each written and read by its own programs; this is the file-processing system. Consider a college where the fees section and the exam section each keep their own file of student details.
1. Problems of the file-processing system:
- Redundancy and inconsistency: the same student's address is stored twice, once in each file; if only one copy is updated, the two disagree.
- Difficulty in accessing data: every new request, such as a list of students who have fee dues and have also passed all subjects, needs a new program.
- Data isolation: data is scattered over many files in different formats.
- Integrity problems: rules such as "attendance cannot exceed 100 percent" are buried inside program code and are hard to add or change.
- Atomicity problems: if the system fails halfway through a fund transfer, one account may be debited without the other being credited.
- Concurrent-access anomalies: two clerks updating the same record at the same time can overwrite each other's changes.
- Security problems: it is hard to let a user see only part of the data.
2. Characteristics of the database approach:
- Self-describing nature: the database stores its own description (metadata) in the system catalog, so the same DBMS software can serve many different databases.
- Insulation between programs and data: the storage structure can change without rewriting programs (program-data independence), and data abstraction hides storage details from users.
- Support for multiple views: each user group sees only the part of the data it needs.
- Sharing of data and multiuser transaction processing: many users work on the same data at once, and concurrency control keeps it correct.
3. Advantages of a DBMS:
- Controlled redundancy, so each fact is stored once and stays consistent.
- Restricted unauthorised access through user accounts and privileges.
- Efficient query processing using indexes and query optimisation.
- Backup and recovery after hardware or software failures.
- Multiple user interfaces: query languages, forms, menus and programming interfaces.
- Enforcement of integrity constraints such as keys and allowed value ranges.
- Faster application development and up-to-date information for every user.
Conclusion: a file-processing system ties data to programs and leaves redundancy, integrity, concurrency and security to each program. A DBMS stores the data once, describes it in a catalog and manages sharing, security and recovery centrally, so it is preferred whenever data is large, shared and valuable.
2 Explain the different types of database users and the duties of the database administrator (DBA). List some typical applications of database systems. 10 marks
A database is used by many kinds of people with different skills and needs. They fall into two broad groups: people who design, administer and use a particular database, and people who build and run the DBMS software and its tools.
1. Database administrator (DBA): the person or team in overall charge of the database and of who may use it. The main duties are:
- Defining the conceptual schema by writing DDL statements.
- Choosing storage structures and access methods, such as indexes.
- Changing the schema or the physical organisation when requirements change.
- Granting and revoking access rights, so that each user reaches only permitted data.
- Routine maintenance: regular backups, ensuring enough free disk space, monitoring performance and tuning the system.
2. Database designers: they identify the data to be stored and choose suitable structures for it. They talk to each user group and design views that meet each group's needs before the database is built.
3. End users:
- Casual users access the database occasionally and need different information each time, so they use a query language.
- Naive or parametric users, such as bank clerks and reservation agents, repeatedly run ready-made (canned) transactions through forms and menus.
- Sophisticated users, such as engineers, scientists and business analysts, write their own queries or use analysis tools.
- Standalone users keep personal databases with ready-made software packages.
4. System analysts and application programmers: analysts find out what naive users need and specify the canned transactions; application programmers write, test, document and maintain these programs.
5. People who build and run the DBMS: DBMS designers and implementers build the DBMS itself; tool developers build packages for database design, performance monitoring and report generation; operators and maintenance staff run the hardware and software environment.
6. Applications of database systems:
- Banking: customer details, accounts, loans and transactions.
- Railway and airline reservation: trains or flights, seats, schedules and bookings.
- Universities: student details, course registration and results.
- Online shopping: product catalogues, orders and payments.
- Telecommunication: call records and monthly bills.
- Human resources: employee details, salaries and tax deductions.
- Manufacturing: inventory, orders and the supply chain.
Conclusion: the DBA controls the database as a whole, designers shape its structure, analysts and programmers build its applications and end users work through those applications, while a separate group builds the DBMS software itself. Together they let one shared database serve applications as varied as banking, reservations and university records.
3 Explain the three-schema architecture of a database system with a neat diagram. How does it provide logical and physical data independence? 10 marks
The three-schema architecture, also called the ANSI/SPARC architecture, separates the users' view of the data from the way the data is physically stored. A schema is a description of the database, and in this architecture the database is described at three levels.
1. Internal level: the internal schema describes the physical storage structure of the database, such as how records are stored in files, the record layout, the indexes and the access paths. It uses a physical (low-level) data model.
2. Conceptual level: the conceptual schema describes the structure of the whole database for the entire community of users: the entities, their attributes and data types, the relationships and the constraints. It hides the physical storage details and is usually written in a representational data model such as the relational model.
3. External (view) level: each external schema, or user view, describes only the part of the database that one user group is interested in and hides the rest. For example, the exam section view may show only roll_no, name and marks, while the accounts section view shows roll_no, name and fee_paid.
4. Mappings: the DBMS transforms a request on an external schema into a request on the conceptual schema (the external/conceptual mapping), and then into a request on the internal schema (the conceptual/internal mapping) to reach the stored database. Results travel back the same way and are reformatted to match each user's view.
5. Data independence: a change in the schema at one level does not force a change in the schema at the level above it; only the mapping between the two levels is changed.
- Logical data independence: the conceptual schema can be changed, for example by adding an attribute or a new entity, without changing the external schemas or the application programs written on them. Only the external/conceptual mapping is updated.
- Physical data independence: the internal schema can be changed, for example by adding an index or moving files to a different disk, without changing the conceptual schema. Only the conceptual/internal mapping is updated.
Of the two, logical data independence is the harder one to provide: programs are written against the logical structure, so changing that structure is more likely to disturb them.
Conclusion: by describing the database at three levels and keeping mappings between them, the three-schema architecture lets the storage structure and the logical design change while user views and application programs stay the same.
4 With a neat diagram, explain the structure of a database system and its environment. Also explain the centralized and client-server architectures for databases. 10 marks
A DBMS is built from modules. Its two main parts, the query processor and the storage manager, sit between the users and the data on disk.
1. Users: naive users run, through forms, application programs written by application programmers; these compiled programs go straight to the query evaluation engine. Sophisticated users send their own queries through the DML compiler, and the DBA works through DDL and administration tools.
2. Query processor:
- DDL interpreter: reads schema definitions written in DDL and stores them in the data dictionary.
- DML compiler: turns each DML query into an evaluation plan of low-level steps; its query optimizer chooses the plan expected to cost least.
- Query evaluation engine: runs the chosen plan and returns the result.
3. Storage manager: the module that reads and writes the stored data on behalf of queries and programs. Its components are:
- Authorization and integrity manager: checks access rights and integrity constraints.
- Transaction manager: makes sure a failure never leaves the database half-updated and that transactions running at the same time do not interfere.
- Buffer manager: copies disk blocks into main memory when needed and decides which blocks to keep there.
- File manager: allots space on disk and organises the files in which the data is kept.
4. Disk storage: the data files contain the actual records; the data dictionary (system catalog) keeps metadata, above all the schema; indices let the system find records without scanning whole files.
5. Environment: around the DBMS are utilities for loading data, backup, file reorganisation and performance monitoring; design tools; application development environments; and communication software for remote users.
6. Centralized architecture: the DBMS, the application programs and the user interface all run on a single central computer, and users reach it through terminals that only display output. It is easy to control, but the central computer is a bottleneck and a single point of failure.
7. Client-server architectures: work is split between client and server machines connected by a network.
- Two-tier: the client runs the user interface and application programs; the database server runs query processing and transaction management. Clients connect through standard interfaces such as ODBC or JDBC.
- Three-tier: an application server, often a web server, sits in the middle and holds the business rules. The client, often a web browser, handles only presentation, and only the application server talks to the database server. This improves security and keeps application logic in one place.
Conclusion: the query processor plans each request, the storage manager carries it out safely on disk, and the system can run on one central computer or be split across clients and servers in two or three tiers.
5 Explain entities, attributes, entity sets, relationships and relationship sets in the ER model, and the constraints on relationship sets. Draw an ER diagram for a college in which students belong to departments and enroll in courses. 10 marks
The entity-relationship (ER) model describes a database at the conceptual level as entities, their attributes and the relationships among them.
1. Entities and entity sets: an entity is any real-world thing, such as one student, that can be told apart from every other thing. An entity set (entity type) groups all entities of one kind that are described by the same attributes, such as STUDENT.
2. Attributes: the properties that describe an entity; each takes its values from a domain (value set).
- Simple attributes cannot be divided (roll_no); composite attributes have parts (address into street, city and pin_code).
- Single-valued attributes have one value per entity (dname); multivalued attributes can have several (phone).
- Stored attributes are kept in the database (dob); derived attributes are computed from them (age from dob).
- A key attribute has a different value for every entity (roll_no) and is underlined.
3. Relationships and relationship sets: a relationship links two or more entities, such as student Ravi enrolled in course CS201. A relationship set collects all relationships of one kind, such as ENROLLS. Its degree is the number of entity sets taking part: binary (two) or ternary (three). A relationship set can have its own attributes, such as grade in ENROLLS. When one entity set takes part twice, the relationship is recursive and role names tell the two roles apart.
4. Constraints on relationship sets:
- Cardinality ratio (mapping cardinality): the largest number of entities on the other side that one entity can be linked to: one-to-one (1:1), one-to-many (1:N), many-to-one (N:1) or many-to-many (M:N). A student belongs to one department and a department has many students, so BELONGS_TO is N:1 from STUDENT to DEPARTMENT, while ENROLLS is M:N.
- Participation constraint: total participation means every entity must take part (every student belongs to some department; drawn as a double line); partial participation means only some entities take part (a new course may have no students yet; single line).
5. ER diagram: on paper an entity set is drawn as a rectangle, an attribute as an ellipse (double ellipse if multivalued) and a relationship set as a diamond, with the cardinality written beside each line and key attributes underlined. In the figure, entity sets are boxes, attributes are rounded shapes and relationship sets are circles.
The diagram has three entity sets: STUDENT (roll_no, name, multivalued phone), DEPARTMENT (dept_id, dname) and COURSE (course_code, title). STUDENT is linked to DEPARTMENT through BELONGS_TO (N and total on the STUDENT side, 1 on the DEPARTMENT side) and to COURSE through ENROLLS (M:N), which carries the attribute grade.
Conclusion: entities, attributes, relationships and their constraints give a clear conceptual design that is later mapped to relational tables.
6 Explain subclasses, superclasses and attribute inheritance in the EER model. Describe specialization and generalization, and their constraints, with an example diagram. 10 marks
The enhanced ER (EER) model adds subclasses, superclasses, specialization and generalization to the basic ER model.
1. Superclass and subclass: an entity set often has subgroups needing extra attributes or relationships. Each subgroup is a subclass, and the entity set it belongs to is its superclass. In a college, STAFF is a superclass, and TEACHING_STAFF and SUPPORT_STAFF (non-teaching staff) are its subclasses. They are linked by an IS-A relationship: a teaching staff member IS-A staff member. A subclass entity is not a new object: it is the same staff member seen in a particular role, so every member of a subclass is also a member of the superclass.
2. Attribute inheritance: a subclass inherits all the attributes and relationships of its superclass. TEACHING_STAFF therefore has staff_id, name, salary and job_type from STAFF, plus its own (local) attribute designation; SUPPORT_STAFF adds section. Only TEACHING_STAFF takes part in the specific relationship TEACHES with COURSE.
3. Specialization: a top-down step that splits an entity set into subclasses by some property that tells its members apart. Here STAFF is specialized on the attribute job_type, which is written on the line from STAFF to the specialization circle.
4. Generalization: the reverse, bottom-up process. If TEACHING_STAFF and SUPPORT_STAFF had been modelled first, their common attributes staff_id, name and salary would be pulled up into one generalized superclass, STAFF. The same hierarchy results; only the direction of design differs.
5. Constraints on specialization and generalization:
- Condition-defined or user-defined: membership decided by a condition on an attribute such as job_type, or by the user who enters the entity.
- Disjointness: disjoint (d) means an entity belongs to at most one subclass; overlapping (o) means it may belong to several. TEACHING_STAFF and SUPPORT_STAFF are disjoint.
- Completeness: total means every superclass entity must belong to some subclass (double line); partial means some need not (single line). Every staff member is teaching or support staff, so this specialization is total.
6. Notation: on paper an entity set is a rectangle, an attribute an ellipse and a relationship a diamond. The superclass is joined to a small circle marked d or o, and the circle to each subclass with a subset symbol on the line; some notations draw a triangle labelled ISA instead. In the figure, entity sets are boxes, attributes are rounded shapes, and circles show the specialization and the relationship TEACHES.
7. Hierarchy and lattice: when every subclass has only one superclass, the result is a specialization hierarchy. If RESEARCH_SCHOLAR were a subclass of both STUDENT and TEACHING_STAFF, it would be a shared subclass inheriting from both (multiple inheritance), forming a lattice.
Conclusion: subclasses, inheritance, specialization and generalization show common and specific properties without repeating attributes.
Relational Model and Basic SQL
Syllabus: Introduction to the relational model; Domain, attribute, tuple and relation; Importance of null values; Domain, key and integrity constraints and their importance; Relational algebra; Relational calculus; A simple database schema and SQL data types; Table definitions: create and alter; DML operations: insert, delete and update
One-page revision summary
- The relational model, proposed by E. F. Codd, stores all data in relations (tables) and lets users reach data only through values, never through storage details.
- The relational model has a structural part (relations), an integrity part (keys and constraints) and a manipulative part (relational algebra and calculus).
- A relation schema R(A1, …, An) gives the relation's name and attributes, while the relation instance is the set of tuples present at one moment.
- A relation has no duplicate tuples, no meaningful order of tuples or attributes, and only atomic values in its cells.
- A null marks a value that is unknown, not applicable or not yet available; comparisons with null give UNKNOWN, so SQL uses IS NULL and IS NOT NULL.
- Domain constraints (data type, NOT NULL, CHECK) restrict each attribute's values, and key constraints (PRIMARY KEY, UNIQUE) forbid two tuples with the same key value.
- Entity integrity forbids nulls in a primary key, and referential integrity requires every foreign key value to match a referenced primary key value or be null.
- Constraints matter because the DBMS enforces them centrally on every INSERT, UPDATE and DELETE, so invalid or orphan data never enters the database.
- Relational algebra is procedural, and its six fundamental operations are selection, projection, union, set difference, Cartesian product and rename.
- Union, intersection and set difference need union-compatible relations: the same degree and matching domains for corresponding attributes.
- Relational calculus is declarative: TRC variables range over tuples, DRC variables range over domain values, and only safe expressions are allowed.
- Common SQL data types are CHAR, VARCHAR, INT, SMALLINT, DECIMAL(p, s), FLOAT, DATE, TIMESTAMP, CLOB and BLOB.
- CREATE TABLE declares columns, data types and constraints, and a referenced table must be created before the table whose foreign key refers to it.
- ALTER TABLE adds, modifies, renames or drops columns and adds constraints, while DROP TABLE removes a table with all its rows.
- INSERT adds rows, UPDATE changes values in the rows chosen by WHERE, and DELETE removes the rows chosen by WHERE; without WHERE they affect every row.
- DELETE without WHERE leaves an empty table, DROP TABLE removes the table itself, and inside a transaction ROLLBACK undoes DML changes that are not yet committed.
Learn these by heart
- Degree = number of attributes; cardinality = number of tuples.
- Candidate key = minimal superkey; primary key = the chosen candidate key, never null.
- R ∩ S = R − (R − S), and the theta join R ⋈θ S = σθ (R × S).
- |R × S| = |R| × |S|, and the degree of R × S is degree(R) + degree(S).
- TRC query: {t | P(t)}; DRC query: {<x1, …, xn> | P(x1, …, xn)}.
- Test for nulls with IS NULL, never with = NULL.
- Relational algebra and safe relational calculus have equal expressive power (relational completeness).
2-mark questions
1 Define domain, attribute, tuple and relation in the relational model. 2 marks
A domain is the set of atomic values an attribute may take, such as the integers 16 to 30 for age. An attribute is a named column whose values come from one domain. A tuple is one row, holding one value for each attribute. A relation is a named set of tuples over the same attributes, drawn as a table.
2 What is a null value? Why are null values important in a relation? 2 marks
A null is a special marker meaning a value is unknown, not applicable or not yet available, such as the phone number of a student who has none. It is not zero or a blank string. Nulls let a tuple be stored without inventing false values. Any comparison with null gives UNKNOWN, so SQL tests it with IS NULL.
3 Distinguish between a superkey, a candidate key and a primary key. 2 marks
A superkey is any set of attributes that identifies each tuple uniquely. A candidate key is a minimal superkey: no proper subset is a superkey. The primary key is the chosen candidate key and cannot be null. In STUDENT(roll_no, aadhaar_no, name), {roll_no, name} is a superkey, roll_no and aadhaar_no are candidate keys, and roll_no is the primary key.
4 Distinguish between the selection and projection operations of relational algebra. 2 marks
Selection, σ_P(R), keeps the tuples of R that satisfy the predicate P: it picks rows and keeps every attribute, so the degree is unchanged. Projection, π_A1,…,Ak(R), keeps only the listed attributes: it picks columns and removes any duplicate tuples that result, so the cardinality can fall but never rise.
5 Differentiate between tuple relational calculus and domain relational calculus. 2 marks
Both are non-procedural query languages based on predicate logic. In tuple relational calculus a variable ranges over the tuples of a relation, and a query has the form {t | P(t)}. In domain relational calculus each variable ranges over the values of an attribute's domain, and a query has the form {<x1, …, xn> | P(x1, …, xn)}.
6 Differentiate between the CHAR(n) and VARCHAR(n) data types in SQL. 2 marks
CHAR(n) is a fixed-length string: every value occupies n characters and a shorter value is padded with blanks, so it suits fixed-size codes such as 'CSE'. VARCHAR(n) is a variable-length string that stores only the characters given, up to n, so it saves space for names and addresses. Oracle's usual form is VARCHAR2(n).
10-mark questions
1 Explain the relational model. Define domain, attribute, tuple, relation, degree and cardinality with an example, and explain the importance of null values. 10 marks
The relational model, proposed by E. F. Codd, stores all data in relations, which are drawn as tables. Each row records one fact and each column is a named property. Users reach data only through values, without knowing how it is stored on disk. The model has three parts: a structural part (relations), an integrity part (keys and constraints) and a manipulative part (relational algebra and calculus, on which SQL is built).
The basic terms are explained with this relation:
STUDENT
roll name dept age
1 Ravi CSE 19
2 Sita ECE 20
3 Kiran CSE NULL
4 Anu NULL 191. Domain: a set of atomic (indivisible) values of one type, such as the integers 16 to 30 for age or the department codes for dept.
2. Attribute: a named column that takes its values from one domain. STUDENT has the attributes roll, name, dept and age.
3. Tuple: one row, holding one value for each attribute, such as (1, Ravi, CSE, 19).
4. Relation schema and relation: the schema STUDENT(roll, name, dept, age) gives the name and the attributes; the relation (relation instance) is the set of tuples present at a given moment. Formally, a relation is a subset of dom(roll) × dom(name) × dom(dept) × dom(age).
5. Degree and cardinality: the degree is the number of attributes (4 here) and the cardinality is the number of tuples (4 here). The degree is fixed by the schema; the cardinality changes with every insertion and deletion.
Properties of a relation: no two tuples are identical (a relation is a set); the order of tuples has no meaning; every value is atomic; and attributes have unique names and are used by name, so their order does not matter.
Importance of null values: a null marks a missing value. It may mean the value is unknown (Kiran's age), not applicable (a hostel room number for a day scholar) or not yet available (Anu's department is not yet allotted). Without nulls we would have to store false values such as age 0, which would spoil results like the average age. A null is not zero or a blank, and any comparison with null gives UNKNOWN:
SELECT name FROM student WHERE age > 18;
-- Ravi, Sita, Anu
SELECT name FROM student
WHERE NOT (age > 18);
-- no rows: Kiran is in neither result
SELECT name FROM student WHERE age IS NULL;
-- Kiran
SELECT AVG(age) FROM student;
-- 19.33 (58 / 3; the null is ignored)Primary key attributes can never be null. In short, the relational model treats data as sets of tuples over domains, and nulls let it record incomplete facts.
2 What are integrity constraints? Explain domain constraints, key constraints, entity integrity and referential integrity with SQL examples, and state their importance. 10 marks
Integrity constraints are rules that every legal state of a database must satisfy. They are declared once in the schema, and the DBMS checks them on every INSERT, UPDATE and DELETE, rejecting any change that would break them. The examples use this schema:
CREATE TABLE department (
dept_id CHAR(3) PRIMARY KEY,
dname VARCHAR(20) NOT NULL UNIQUE
);
CREATE TABLE student (
roll_no INT PRIMARY KEY,
name VARCHAR(30) NOT NULL,
age INT CHECK (age BETWEEN 16 AND 30),
dept_id CHAR(3)
REFERENCES department(dept_id)
);The starting data is two departments, ('CSE', 'Computer Science') and ('ECE', 'Electronics'), and one student, (101, 'Ravi', 19, 'CSE').
1. Domain constraints: every value must be atomic and belong to its attribute's domain, stated with the data type, NOT NULL and CHECK. Here age must be from 16 to 30 and name may not be null.
2. Key constraints: no two tuples may have the same value of a candidate key. PRIMARY KEY and UNIQUE declare them, so roll_no and dname must both be unique.
3. Entity integrity: no attribute of the primary key may be null, because the primary key is how each tuple is identified.
4. Referential integrity: a foreign key value must either match a primary key value in the referenced relation or be null. Here student.dept_id must name an existing department.
The first three are checked within one relation; referential integrity is checked between two relations.
Each statement below is run, in order, on the starting data:
INSERT INTO student
VALUES (102, 'Sita', 45, 'ECE');
-- rejected: CHECK fails (domain)
INSERT INTO student
VALUES (101, 'Kiran', 20, 'CSE');
-- rejected: duplicate primary key
INSERT INTO student
VALUES (NULL, 'Anu', 19, 'ECE');
-- rejected: entity integrity
INSERT INTO student
VALUES (103, 'Hari', 20, 'MEC');
-- rejected: no department MEC
INSERT INTO student
VALUES (104, 'Uma', 20, NULL);
-- accepted: a foreign key may be null
DELETE FROM department
WHERE dept_id = 'CSE';
-- rejected: student 101 refers to CSEThese are the results in Oracle and in standard SQL. SQLite checks foreign keys only after PRAGMA foreign_keys = ON, and it accepts the null roll_no unless the column is also declared NOT NULL. With ON DELETE CASCADE (referring rows are deleted too) or ON DELETE SET NULL (their foreign key becomes null), a referenced row can be deleted.
Importance of integrity constraints:
- They keep data accurate and consistent.
- They are enforced centrally by the DBMS, not rewritten in every application program.
- Keys let every tuple be identified and let relations be linked through joins.
- Referential integrity prevents orphan rows, such as a student of a non-existent department.
Thus constraints turn real-world rules into checks the DBMS applies automatically.
3 Explain the fundamental operations of relational algebra (selection, projection, union, set difference, Cartesian product and rename) with examples. 10 marks
Relational algebra is a procedural query language: a query is a sequence of operations, each taking one or two relations as input and producing a new relation. Because every result is again a relation, operations can be nested. The examples use these relations (CODING and MUSIC list the members of two clubs):
STUDENT
roll name dept age
1 Ravi CSE 19
2 Sita ECE 20
3 Kiran CSE 21
4 Anu EEE 19
CODING MUSIC EVENT
roll name roll name event
1 Ravi 2 Sita Quiz
3 Kiran 3 Kiran Hackathon1. Selection (σ): σ_P(R) keeps the tuples of R that satisfy the predicate P, built from comparisons (=, ≠, <, ≤, >, ≥) joined by ∧, ∨ and ¬. σ dept='CSE' (STUDENT) gives (1, Ravi, CSE, 19) and (3, Kiran, CSE, 21).
2. Projection (π): π_A1,…,Ak(R) keeps only the listed attributes and removes duplicate tuples. π dept (STUDENT) gives CSE, ECE and EEE: three tuples, not four, because CSE appears twice.
3. Union (∪): R ∪ S holds the tuples that are in R, in S or in both. R and S must be union-compatible: the same degree, with matching domains for corresponding attributes. CODING ∪ MUSIC gives (1, Ravi), (2, Sita) and (3, Kiran).
4. Set difference (−): R − S holds the tuples that are in R but not in S. CODING − MUSIC gives (1, Ravi), while MUSIC − CODING gives (2, Sita), so difference is not commutative.
5. Cartesian product (×): R × S pairs every tuple of R with every tuple of S, so the degrees add and the cardinalities multiply. π name (CODING) × EVENT has 2 × 2 = 4 tuples: (Ravi, Quiz), (Ravi, Hackathon), (Kiran, Quiz) and (Kiran, Hackathon).
6. Rename (ρ): ρ X (E) gives the result of the expression E the name X, and ρ X(A1, …, An) (E) renames its attributes as well. ρ CSE_STU (σ dept='CSE' (STUDENT)) names the CSE students' relation CSE_STU for later steps.
Operations combine into one expression. The names of CSE students aged 20 or more are found by selecting and then projecting; only one of the four STUDENT tuples passes the selection:
π name (σ dept='CSE' ∧ age ≥ 20 (STUDENT)) = {(Kiran)}
Other operations are derived from these six. Intersection is R ∩ S = R − (R − S), so CODING ∩ MUSIC gives (3, Kiran). A theta join is a selection on a product, R ⋈θ S = σθ (R × S), and division can be written with π, × and −.
Thus the six fundamental operations form a complete set, and a DBMS translates each SQL query into a relational algebra expression (a query tree) before evaluating it.
4 Explain tuple relational calculus and domain relational calculus with examples. How does relational calculus differ from relational algebra? 10 marks
Relational calculus is a non-procedural (declarative) query language based on first-order predicate logic. A query describes what the result must satisfy, not the steps that compute it. Its two forms are tuple (TRC) and domain (DRC) relational calculus. The examples use:
STUDENT
roll name dept age
1 Ravi CSE 19
2 Sita ECE 20
3 Kiran CSE 21
4 Anu EEE 19
ENROLL COURSE
roll course course
1 DBMS DBMS
1 OS OS
2 DBMS
3 OSTuple relational calculus: a query has the form {t | P(t)}, the set of all tuples t for which the formula P(t) is true. The atoms are t ∈ R, t.A op s.B and t.A op c, where op is a comparison and c is a constant. Formulas combine atoms with ∧, ∨, ¬ and →, and with the quantifiers ∃ (there exists) and ∀ (for all).
1. Students older than 19: {t | t ∈ STUDENT ∧ t.age > 19} gives (2, Sita, ECE, 20) and (3, Kiran, CSE, 21).
2. Names of students enrolled in DBMS, using ∃: {t.name | t ∈ STUDENT ∧ ∃e (e ∈ ENROLL ∧ e.roll = t.roll ∧ e.course = 'DBMS')} gives Ravi and Sita.
3. Names of students enrolled in every course, using ∀: {t.name | t ∈ STUDENT ∧ ∀c (c ∈ COURSE → ∃e (e ∈ ENROLL ∧ e.roll = t.roll ∧ e.course = c.course))} gives only Ravi, the one student enrolled in both DBMS and OS.
Domain relational calculus: each variable ranges over one attribute's domain. A query has the form {<x1, …, xn> | P(x1, …, xn)}, where the atom <x1, …, xn> ∈ R is true when those values form a tuple of R.
4. Names of CSE students: {<n> | ∃r ∃d ∃a (<r, n, d, a> ∈ STUDENT ∧ d = 'CSE')} gives Ravi and Kiran.
5. Name and age of students older than 19: {<n, a> | ∃r ∃d (<r, n, d, a> ∈ STUDENT ∧ a > 19)} gives (Sita, 20) and (Kiran, 21).
Safety: {t | ¬(t ∈ STUDENT)} describes infinitely many tuples, so it is unsafe; only safe expressions, whose results use only values from the database or the query, are allowed.
Relational calculus compared with relational algebra:
- Algebra is procedural and fixes the order of operations; calculus is declarative and states only the condition.
- Algebra uses operators (σ, π, ∪, −, ×, ρ); calculus uses variables, logical connectives and quantifiers.
- Algebra suits query evaluation plans; calculus underlies declarative languages: SQL resembles TRC, and QBE is based on DRC.
- Expressive power: relational algebra, safe TRC and safe DRC can express exactly the same queries (Codd's theorem). A language with this power is called relationally complete.
So calculus says what is wanted and algebra says how to get it, with equal power.
5 Design a simple database schema for a college. Explain the common SQL data types, write CREATE TABLE statements with constraints, and show how ALTER TABLE changes a table. 10 marks
A database schema is the description of a database: its tables, their attributes and data types, and the constraints on them. It is written with the DDL commands CREATE, ALTER and DROP and is kept in the data dictionary. A simple college schema (on paper, underline the primary keys):
DEPARTMENT(dept_id, dname)
STUDENT(roll_no, name, dob, cgpa, dept_id)
COURSE(course_id, title, credits)
ENROLL(roll_no, course_id, grade)In the figure each box shows a table with its primary key, and each arrow goes from a foreign key to the table it refers to. ENROLL has the composite primary key (roll_no, course_id), so a student can enrol in a course only once.
Common SQL data types:
- CHAR(n): a fixed-length string of n characters, padded with blanks.
- VARCHAR(n): a variable-length string of at most n characters (VARCHAR2 in Oracle).
- INT (INTEGER) and SMALLINT: whole numbers.
- DECIMAL(p, s) or NUMERIC(p, s): exact numbers of p digits, s of them after the decimal point; DECIMAL(4,2) holds -99.99 to 99.99 (NUMBER(p, s) in Oracle).
- FLOAT, REAL and DOUBLE PRECISION: approximate floating-point numbers.
- DATE, TIME and TIMESTAMP: a date, a time of day, and both together (Oracle's DATE also stores the time).
- CLOB and BLOB: large text and binary objects, such as documents and photos.
Table definitions; a referenced table is created before the table that refers to it:
CREATE TABLE department (
dept_id CHAR(3) PRIMARY KEY,
dname VARCHAR(30) NOT NULL UNIQUE
);
CREATE TABLE student (
roll_no INT PRIMARY KEY,
name VARCHAR(30) NOT NULL,
dob DATE,
cgpa DECIMAL(4,2)
CHECK (cgpa BETWEEN 0 AND 10),
dept_id CHAR(3)
REFERENCES department(dept_id)
);
CREATE TABLE course (
course_id CHAR(6) PRIMARY KEY,
title VARCHAR(40) NOT NULL,
credits SMALLINT
);
CREATE TABLE enroll (
roll_no INT REFERENCES student(roll_no),
course_id CHAR(6)
REFERENCES course(course_id),
grade CHAR(1),
PRIMARY KEY (roll_no, course_id)
);ALTER TABLE changes the structure of an existing table without re-creating it:
ALTER TABLE student ADD email VARCHAR(40);
ALTER TABLE enroll MODIFY grade CHAR(2);
ALTER TABLE student
RENAME COLUMN dob TO birth_date;
ALTER TABLE student DROP COLUMN email;
ALTER TABLE course ADD CONSTRAINT chk_cr
CHECK (credits BETWEEN 1 AND 4);- ADD appends a new column; the existing rows get NULL in it.
- MODIFY changes a column's type or size, here so that grades such as 'A+' fit. This is the Oracle and MySQL form; SQLite has no MODIFY.
- RENAME COLUMN renames a column, and DROP COLUMN removes a column with its values.
- ADD CONSTRAINT adds a named constraint; the DBMS refuses it if an existing row breaks it.
Finally, DROP TABLE enroll removes the table's rows and its definition. CREATE defines the schema, and ALTER lets it change as requirements grow.
6 Explain the DML commands INSERT, UPDATE and DELETE with their syntax and examples, showing the contents of the table after each step. 10 marks
Data Manipulation Language (DML) commands change the rows of a table, not its structure. The three basic ones are INSERT (add rows), UPDATE (change values in rows) and DELETE (remove rows). The DBMS checks every DML statement against the table's constraints. The examples use this table:
CREATE TABLE student (
roll_no INT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
dept CHAR(3),
marks INT
);1. INSERT. Syntax: INSERT INTO table [(column list)] VALUES (value list);
INSERT INTO student
VALUES (101, 'Ravi', 'CSE', 78);
INSERT INTO student
VALUES (102, 'Sita', 'ECE', 65);
INSERT INTO student
VALUES (103, 'Kiran', 'CSE', 58);
INSERT INTO student (roll_no, name, dept)
VALUES (104, 'Anu', 'EEE');Without a column list, a value must be given for every column in table order. With a column list, an omitted column gets NULL (or its DEFAULT value, if one is declared), so Anu's marks are NULL. Table after the inserts:
roll_no name dept marks
101 Ravi CSE 78
102 Sita ECE 65
103 Kiran CSE 58
104 Anu EEE NULLA further INSERT INTO student VALUES (101, 'Hari', 'MEC', 60); is rejected, because roll_no 101 already exists and roll_no is the primary key.
2. UPDATE. Syntax: UPDATE table SET column = expression [, column = expression] [WHERE condition];
UPDATE student SET marks = marks + 5
WHERE dept = 'CSE';
UPDATE student SET marks = 70
WHERE roll_no = 104;The first statement changes the two CSE rows: Ravi's 78 becomes 83 and Kiran's 58 becomes 63. Arithmetic with a null gives null (NULL + 5 is still NULL), so Anu's missing marks are set directly by the second statement. Without a WHERE clause, UPDATE changes every row. Table after the updates:
roll_no name dept marks
101 Ravi CSE 83
102 Sita ECE 65
103 Kiran CSE 63
104 Anu EEE 703. DELETE. Syntax: DELETE FROM table [WHERE condition];
DELETE FROM student WHERE marks < 65;Only Kiran (63) is removed; Sita's 65 is not less than 65. Final table:
roll_no name dept marks
101 Ravi CSE 83
102 Sita ECE 65
104 Anu EEE 70DELETE FROM student; with no WHERE clause removes every row but keeps the empty table, whereas DROP TABLE student removes the table itself. A DELETE is also refused while a foreign key in another table still refers to the row, unless that foreign key was declared with ON DELETE CASCADE or ON DELETE SET NULL.
Inside a transaction, COMMIT makes these changes permanent and ROLLBACK undoes them. So INSERT, UPDATE and DELETE, each limited by a WHERE condition and checked against the constraints, keep the stored data correct and current.
SQL Querying
Syllabus: Basic SQL querying (select and project) with the where clause; Arithmetic and logical operations; SQL functions: date and time, numeric and string conversion; Creating tables with relationships; Implementing key and integrity constraints; Nested queries and subqueries; Grouping, aggregation and ordering; Types of joins; Views: updatable and non-updatable; Relational set operations
One-page revision summary
- In SELECT column-list FROM table WHERE condition, the SELECT list performs projection, the WHERE clause performs selection, and DISTINCT removes duplicate rows from the result.
- BETWEEN includes both end values, IN tests membership in a list, and LIKE matches patterns in which % stands for any string and _ for one character.
- In arithmetic, * and / are applied before + and -, and any arithmetic involving NULL gives NULL.
- Single-row functions return one value per row: numeric (ROUND, TRUNC, MOD), string (UPPER, SUBSTR, LENGTH), date (ADD_MONTHS, LAST_DAY) and conversion (TO_CHAR, TO_DATE, TO_NUMBER).
- In Oracle, adding a number to a date adds that many days, and subtracting one date from another gives the number of days between them.
- A one-to-many relationship is built by placing the primary key of the parent table in the child table as a foreign key.
- A many-to-many relationship becomes a separate table whose composite primary key is made of two foreign keys.
- A table has one primary key, which is unique and NOT NULL, but may have several UNIQUE columns, which in Oracle and MySQL may hold NULLs.
- CHECK limits the values a column may take, and DEFAULT supplies a value when an INSERT leaves the column out.
- A non-correlated subquery runs once, while a correlated subquery refers to the outer row and is logically evaluated for each outer row.
- NOT IN returns no rows if its subquery produces a NULL, so NOT EXISTS is the safer way to test for absence.
- Aggregate functions ignore NULLs, except COUNT(*), which counts every row.
- Every column in the SELECT list that is not inside an aggregate function must appear in the GROUP BY clause.
- ORDER BY sorts in ascending order by default; DESC reverses it, and several sort keys can be listed.
- An outer join keeps the unmatched rows of one or both tables and fills the columns of the missing side with NULL.
- A natural join matches on all columns with the same name and shows each such column once, while an equi join names its condition explicitly.
- A view stores only its defining query, so its rows are computed from the base tables each time it is used.
- WITH CHECK OPTION rejects DML through a view that would create a row the view cannot show, and Oracle's WITH READ ONLY blocks all DML through a view.
- UNION, INTERSECT and EXCEPT remove duplicate rows while UNION ALL keeps them; Oracle writes EXCEPT as MINUS, and Oracle 21c and later also accept EXCEPT.
Learn these by heart
- Logical order of evaluation: FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY.
- WHERE filters rows before grouping and cannot use aggregates; HAVING filters groups after grouping and may use them.
- Three-valued logic: a comparison with NULL gives UNKNOWN, and WHERE keeps only rows whose condition is TRUE.
- A view on one table is updatable only if each view row maps to one base row and it has no DISTINCT, aggregate, GROUP BY, HAVING or set operator; a view over a join is updatable only under restrictions.
- Union compatibility: both queries return the same number of columns, with compatible data types, in the same order.
- A cross join of tables with m and n rows gives m × n rows; a left outer join returns every row of the left table at least once.
- Apart from duplicates, A INTERSECT B equals A WHERE x IN (B), and A EXCEPT B equals A WHERE x NOT IN (B) when B has no NULL.
2-mark questions
1 Distinguish between the WHERE clause and the HAVING clause in SQL. 2 marks
WHERE filters individual rows before grouping and cannot contain aggregate functions. HAVING filters whole groups after GROUP BY and usually tests an aggregate. For example, WHERE salary > 40000 first removes low-paid employees, and HAVING COUNT(*) >= 2 then removes departments left with fewer than two employees. One query can use both clauses.
2 How does SQL treat NULL in arithmetic expressions and in logical conditions? 2 marks
NULL means a missing or unknown value. Arithmetic with NULL gives NULL, so NULL + 5 is NULL. A comparison with NULL, even NULL = NULL, gives UNKNOWN, a third truth value; UNKNOWN OR TRUE is TRUE and UNKNOWN AND FALSE is FALSE. WHERE keeps only TRUE rows, so NULLs are tested with IS NULL.
3 What is referential integrity? How do ON DELETE CASCADE and ON DELETE SET NULL differ? 2 marks
Referential integrity requires every non-null foreign key value in a child table to match an existing primary key (or unique key) value in the parent table. When a parent row is deleted, ON DELETE CASCADE deletes its child rows too, while ON DELETE SET NULL keeps them with a NULL foreign key. Without either rule, the delete is rejected.
4 What is the difference between UNION and UNION ALL? Give an example. 2 marks
Both combine the rows of two union-compatible queries. UNION removes duplicate rows, while UNION ALL keeps every row and is faster because it skips the duplicate check. If R(a) holds 1, 2, 2 and S(a) holds 2, 3, then R UNION S gives 1, 2, 3 and R UNION ALL S gives 1, 2, 2, 2, 3.
5 What is a correlated subquery? How does it differ from an ordinary subquery? 2 marks
A correlated subquery uses a column of the outer query, as in WHERE e.sid = s.sid, so it is logically evaluated again for every row of the outer query. An ordinary (non-correlated) subquery does not depend on the outer query: it runs once and its result is reused. EXISTS and NOT EXISTS tests are usually correlated.
6 What are conversion functions in SQL? Give an example. 2 marks
Conversion functions change a value from one data type to another. In Oracle, TO_CHAR converts a date or number to text, TO_DATE converts text to a date and TO_NUMBER converts text to a number; CAST is the standard SQL form. For example, TO_CHAR(DATE '2025-08-15', 'DD-MON-YYYY') returns '15-AUG-2025'.
10-mark questions
1 Explain the basic form of an SQL query. Using a sample EMP table, write queries that select and project rows with a WHERE clause, and that group, aggregate and order the result with GROUP BY, HAVING and ORDER BY. Show the result of each query. 10 marks
An SQL query retrieves data with the SELECT statement. In its basic form, SELECT column-list FROM table WHERE condition, the WHERE clause performs selection (it keeps only the rows that satisfy the condition) and the SELECT list performs projection (it keeps only the named columns). Optional clauses group, filter and sort the result:
SELECT [DISTINCT] column-list
FROM table-list
[WHERE row-condition]
[GROUP BY column-list]
[HAVING group-condition]
[ORDER BY column [ASC | DESC]];Sample table EMP:
emp_no ename dept salary
101 Ravi CSE 50000
102 Sita ECE 42000
103 Kiran CSE 61000
104 Anil EEE 38000
105 Divya ECE 45000
106 Rahul CSE 540001. Selection and projection. Only two of the six rows satisfy both conditions, and only two of the four columns are kept:
SELECT ename, salary
FROM emp
WHERE dept = 'CSE' AND salary > 52000;
ename salary
Kiran 61000
Rahul 540002. Removing duplicates. SELECT DISTINCT dept FROM emp ORDER BY dept; returns CSE, ECE and EEE, each once.
3. Aggregation. COUNT, SUM, AVG, MAX and MIN turn many rows into one value. SELECT COUNT(*), SUM(salary), MAX(salary), MIN(salary) FROM emp; returns 6, 290000, 61000 and 38000.
4. Grouping, filtering groups and ordering:
SELECT dept, COUNT(*) AS cnt,
AVG(salary) AS avg_sal
FROM emp
WHERE salary > 40000
GROUP BY dept
HAVING COUNT(*) >= 2
ORDER BY avg_sal DESC;
dept cnt avg_sal
CSE 3 55000
ECE 2 43500- FROM emp supplies all 6 rows.
- WHERE removes Anil (38000), leaving 5 rows.
- GROUP BY forms 2 groups: CSE (50000, 61000, 54000) and ECE (42000, 45000).
- HAVING keeps both groups, since each has at least two rows.
- SELECT computes 165000 / 3 = 55000 and 87000 / 2 = 43500, giving 2 rows.
- ORDER BY avg_sal DESC puts the higher average first; ASC (ascending) is the default.
Every column in the SELECT list that is not inside an aggregate function must appear in GROUP BY.
5. Logical order of evaluation. Although SELECT is written first, the clauses are evaluated in this order:
In short, WHERE filters rows, GROUP BY forms groups, HAVING filters groups, SELECT projects columns and computes expressions, and ORDER BY sorts the final result.
2 Explain the arithmetic, comparison and logical operators of SQL, and its single-row functions for numbers, strings, dates and type conversion. Give examples with their results. 10 marks
SQL computes new values with operators and built-in functions. Operators combine values in the SELECT list or the WHERE clause; a single-row function returns one result for each row.
Sample table ITEM:
id name price qty
1 Pen 10 50
2 Book 120 10
3 Bag 450 NULL
4 Ink 25 81. Arithmetic operators: + (add), - (subtract), * (multiply) and / (divide). * and / are applied before + and -, and parentheses change the order. Any arithmetic with NULL gives NULL.
2. Comparison operators: =, <> (not equal), <, >, <= and >=, plus BETWEEN low AND high (both ends included), IN (list), LIKE (% matches any string, _ one character) and IS NULL.
3. Logical operators: AND (true when both conditions are true), OR (true when at least one is true) and NOT (reverses a condition).
SELECT name, price * qty AS amount
FROM item
WHERE price > 100 OR qty >= 50;
name amount
Pen 500
Book 1200
Bag NULLBag qualifies through price > 100, but 450 * NULL is NULL. Ink fails both conditions.
SELECT name FROM item
WHERE price BETWEEN 10 AND 120
AND NOT name LIKE 'B%';This returns Pen and Ink: Book is in the price range but is removed by NOT LIKE 'B%'. Similarly, WHERE qty IS NULL returns Bag, while WHERE qty = NULL returns no rows.
4. Single-row functions, in Oracle syntax, for example SELECT MOD(17, 5) FROM dual; (dual is Oracle's one-row dummy table). Below, d stands for DATE '2025-08-15', a Friday, and dates are shown as DD-MON-YYYY.
Numeric
ROUND(156.789, 1) 156.8
TRUNC(156.789, 1) 156.7
MOD(17, 5) 2
CEIL(4.2), FLOOR(4.8) 5, 4
POWER(2, 5), SQRT(81) 32, 9
String
UPPER('dbms') DBMS
INITCAP('data base') Data Base
LENGTH('Kakinada') 8
SUBSTR('KAKINADA', 1, 4) KAKI
INSTR('KAKINADA', 'A') 2
LPAD('42', 5, '0') 00042
'JNTU' || 'K' JNTUK
Date and time
SYSDATE current date-time
d + 10 25-AUG-2025
d - DATE '2025-08-01' 14 (days)
ADD_MONTHS(d, 1) 15-SEP-2025
MONTHS_BETWEEN(d,
DATE '2025-03-15') 5
LAST_DAY(d) 31-AUG-2025
NEXT_DAY(d, 'MONDAY') 18-AUG-2025
EXTRACT(YEAR FROM d) 2025
Conversion
TO_CHAR(d, 'DD/MM/YYYY') 15/08/2025
TO_DATE('15/08/2025',
'DD/MM/YYYY') 15-AUG-2025
TO_NUMBER('1250.50') + 10 1260.5If the day does not exist in the target month, or the input is the last day of its month, ADD_MONTHS returns the last day of the target month, so ADD_MONTHS(DATE '2025-01-31', 1) gives 28-FEB-2025. MySQL has most of the numeric and string functions too, but it writes TRUNCATE for TRUNC, has no INITCAP, joins strings with CONCAT (by default || means OR there) and has its own date functions such as CURDATE() and DATE_ADD.
Operators build conditions, and single-row functions transform individual values; both may appear wherever an expression is allowed.
3 Write SQL statements to create DEPT and EMP tables related one-to-many, using PRIMARY KEY, FOREIGN KEY, NOT NULL, UNIQUE and CHECK constraints and a DEFAULT value. Show which inserts and deletes the DBMS accepts or rejects, and why. 10 marks
Integrity constraints are rules declared with a table so that the DBMS itself rejects invalid data, whichever program sends it. They are of three kinds: domain constraints (data type, NOT NULL, CHECK), key constraints (PRIMARY KEY, UNIQUE) and referential integrity (FOREIGN KEY). A DEFAULT clause is not a rule; it supplies a value when an INSERT leaves the column out. A one-to-many relationship is created by placing the primary key of the 'one' table in the 'many' table as a foreign key.
1. Parent table (Oracle syntax):
CREATE TABLE dept (
dept_no NUMBER(2) PRIMARY KEY,
dname VARCHAR2(20) NOT NULL UNIQUE,
location VARCHAR2(20) DEFAULT 'Kakinada'
);2. Child table. Each employee belongs to one department, and mgr_no is a self-referencing foreign key that points to the employee's manager:
CREATE TABLE emp (
emp_no NUMBER(4) PRIMARY KEY,
ename VARCHAR2(20) NOT NULL,
salary NUMBER(8,2) CHECK (salary > 0),
dept_no NUMBER(2),
mgr_no NUMBER(4),
CONSTRAINT emp_dept_fk
FOREIGN KEY (dept_no)
REFERENCES dept (dept_no)
ON DELETE CASCADE,
CONSTRAINT emp_mgr_fk
FOREIGN KEY (mgr_no)
REFERENCES emp (emp_no)
);Constraints written beside a column are column-level; the two named FOREIGN KEY constraints are table-level. A composite key, such as PRIMARY KEY (emp_no, proj_no) in a works-on table, can only be written at table level. In the figure, PK marks a primary key and FK a foreign key.
3. Accepted rows. INSERT INTO dept (dept_no, dname) VALUES (10, 'CSE'); stores location 'Kakinada' through DEFAULT, and INSERT INTO dept VALUES (20, 'ECE', 'Vizag'); is also accepted. Then INSERT INTO emp VALUES (...) adds:
emp_no ename salary dept_no mgr_no
1 Ravi 50000 10 NULL
2 Sita 42000 10 1
3 Kiran 45000 20 14. Rejected inserts, each breaking one constraint:
Row inserted Rule broken
emp (1,'Anil',30000,10,NULL) PRIMARY KEY
emp (4,NULL,30000,10,1) NOT NULL
emp (4,'Anil',-5,10,1) CHECK
emp (4,'Anil',30000,99,1) FK: no dept 99
emp (4,'Anil',30000,10,77) FK: no emp 77
dept (30,'CSE','Guntur') UNIQUE dname5. Deletes. DELETE FROM dept WHERE dept_no = 20; is accepted, and ON DELETE CASCADE also deletes Kiran, the only employee of department 20. Next, DELETE FROM emp WHERE emp_no = 1; is rejected, because Sita's mgr_no still refers to Ravi and emp_mgr_fk has no ON DELETE rule. Declaring that key with ON DELETE SET NULL would instead keep Sita with a NULL mgr_no.
Because the rules live in the schema, every application gets the same checks, and no employee row can point to a department or manager that does not exist.
4 What is a view? Explain how views are created, queried and updated, distinguish updatable views from non-updatable views with examples, and explain WITH CHECK OPTION. 10 marks
A view is a named query that behaves like a virtual table. Only its definition is stored in the data dictionary; each time the view is used, the DBMS runs that query against the current base tables. Views hide rows and columns a user need not see, give a simple name to a complex query and keep programs working when base tables change.
Base table EMP:
emp_no ename salary dept_no
101 Ravi 50000 10
102 Sita 42000 20
103 Kiran 61000 10
104 Divya 45000 20
105 Anil 38000 301. Creating and querying a view (Oracle and MySQL syntax):
CREATE VIEW cse_emp AS
SELECT emp_no, ename, salary, dept_no
FROM emp
WHERE dept_no = 10
WITH CHECK OPTION;SELECT * FROM cse_emp; returns (101, Ravi, 50000, 10) and (103, Kiran, 61000, 10).
2. Updatable view. cse_emp is defined on one base table and each of its rows maps to exactly one EMP row, so the DBMS can translate DML on the view into DML on EMP:
UPDATE cse_emp SET salary = salary + 2000
WHERE emp_no = 101;This UPDATE through cse_emp reaches EMP: Ravi's salary there becomes 52000. In general, a view on a single table is updatable only if each view row maps to one base row and it has no DISTINCT, aggregate function, GROUP BY, HAVING or set operator (UNION, INTERSECT, MINUS). An INSERT through it also needs every NOT NULL column without a default to be in the view.
3. Non-updatable view:
CREATE VIEW dept_pay AS
SELECT dept_no, COUNT(*) AS cnt,
SUM(salary) AS total
FROM emp
GROUP BY dept_no;After the update above, dept_pay returns (10, 2, 113000), (20, 2, 87000) and (30, 1, 38000). Each of its rows is a summary of several EMP rows, so UPDATE dept_pay SET total = 100000 WHERE dept_no = 10; is rejected: the total 113000 comes from two salaries (52000 + 61000), and the DBMS cannot decide how to change them. For the same reason a column computed as salary * 12 cannot itself be updated, and a view over a join is updatable only under restrictions (Oracle and MySQL, for example, let one statement change only one of the joined tables).
4. WITH CHECK OPTION rejects any INSERT or UPDATE through the view that would create a row the view itself cannot show. UPDATE cse_emp SET dept_no = 20 WHERE emp_no = 103; is rejected, because Kiran's row would leave department 10. Without the option, the update would succeed and the row would silently disappear from the view.
CREATE OR REPLACE VIEW redefines a view, and DROP VIEW removes only its definition, never the rows in EMP.
5 Explain the types of joins in SQL: inner joins (equi, natural and theta), left, right and full outer joins, the cross join and the self join. Illustrate each with sample tables and show the results. 10 marks
A join combines rows of two tables into one result, usually by matching a column that they share. An inner join is logically a cross join (all pairs of rows) filtered by the join condition. The sample tables:
EMP DEPT
eno ename dno mgr dno dname
1 Ravi 10 NULL 10 CSE
2 Sita 20 1 20 ECE
3 Kiran NULL 1 30 EEE1. Inner join. Only pairs that satisfy the condition are returned:
SELECT e.ename, d.dname
FROM emp e INNER JOIN dept d
ON e.dno = d.dno;Result (2 rows): (Ravi, CSE) and (Sita, ECE). Kiran has no department and EEE has no employee, so both are left out.
- An equi join is an inner join whose condition uses =, as above.
- A natural join, emp NATURAL JOIN dept, matches automatically on every column with the same name (here dno) and shows that column only once. Here it returns the same two pairs.
- A theta (non-equi) join uses another comparison: ON e.dno < d.dno returns (Ravi, ECE), (Ravi, EEE) and (Sita, EEE).
2. Outer joins keep unmatched rows as well and fill the columns of the missing side with NULL. Replacing INNER JOIN in the query above gives:
Join Rows added to inner result
LEFT OUTER JOIN (Kiran, NULL)
RIGHT OUTER JOIN (NULL, EEE)
FULL OUTER JOIN (Kiran, NULL), (NULL, EEE)So the left join returns 3 rows, the right join 3 rows and the full join 4 rows. MySQL has no FULL OUTER JOIN; there it is written as the UNION of a left join and a right join, which gives the same 4 rows.
3. Cross join. FROM emp CROSS JOIN dept pairs every employee with every department: 3 × 3 = 9 rows. A cross join of tables with m and n rows always gives m × n rows.
4. Self join. A table is joined with itself under two aliases, here to list each employee with the manager:
SELECT e.ename, m.ename AS manager
FROM emp e JOIN emp m
ON e.mgr = m.eno;Result (2 rows): (Sita, Ravi) and (Kiran, Ravi). Ravi has no manager, so he does not appear; a LEFT OUTER self join would include him with a NULL manager.
An inner join is chosen when only matching rows matter, an outer join when unmatched rows must also be reported, and a self join when rows of one table are related to each other.
6 Explain nested queries in SQL, including subqueries with IN, EXISTS and comparison operators and correlated subqueries. Also explain the set operations UNION, UNION ALL, INTERSECT and EXCEPT, and show how INTERSECT and EXCEPT can be written as nested queries. Use sample tables and show the results. 10 marks
A nested query is a query written inside another SQL statement, in its WHERE, FROM, HAVING or SELECT clause. The inner query, called a subquery, supplies a value, a list of values or a table to the outer query. Set operations, in contrast, combine the results of two complete queries.
Sample tables:
STUDENT ENROLL
sid sname sid course
1 Asha 1 DBMS
2 Bala 1 OS
3 Chitra 2 DBMS
4 Dev 3 OS
3 CN1. Subquery with IN. The subquery does not depend on the outer query, so it runs once and gives the list (1, 2):
SELECT sname FROM student
WHERE sid IN (SELECT sid FROM enroll
WHERE course = 'DBMS');Result: Asha and Bala.
2. Correlated subquery with NOT EXISTS. The subquery refers to s.sid of the outer row, so it is evaluated once for every student. EXISTS is true when the subquery returns at least one row:
SELECT sname FROM student s
WHERE NOT EXISTS (SELECT * FROM enroll e
WHERE e.sid = s.sid);Result: Dev, the only student with no enrolment. NOT IN (SELECT sid FROM enroll) gives the same answer here, but NOT IN returns no rows at all if the subquery produces a NULL, so NOT EXISTS is safer.
3. Subquery with a comparison operator. A scalar subquery returns one value, which can be compared with =, <, > and so on:
SELECT sname FROM student s
WHERE (SELECT COUNT(*) FROM enroll e
WHERE e.sid = s.sid) >= 2;Result: Asha and Chitra. When a subquery returns a list, the comparison is combined with ANY (true if it holds for at least one value) or ALL (true if it holds for every value); = ANY means the same as IN.
4. Set operations need union-compatible operands: the same number of columns, with compatible types, in the same order. Let A be SELECT sid FROM enroll WHERE course = 'DBMS', which gives 1, 2, and B the same query for 'OS', which gives 1, 3.
A UNION B 1, 2, 3 (no duplicates)
A UNION ALL B 1, 2, 1, 3
A INTERSECT B 1
A EXCEPT B 2
B EXCEPT A 3Oracle writes EXCEPT as MINUS, and Oracle 21c and later also accept EXCEPT.
5. Set operations as nested queries. Apart from duplicate rows, which the set operators remove, A INTERSECT B equals A with AND sid IN (B) added to its WHERE clause, and A EXCEPT B equals A with AND sid NOT IN (B), provided B returns no NULL. On the sample data they return 1 and 2 respectively, as above.
Nested queries use one query's result inside another, while set operations merge whole results.
Schema Refinement (Normalization)
Syllabus: Purpose of normalization or schema refinement; Functional dependency; Normal forms based on functional dependency: 1NF, 2NF and 3NF; Lossless-join decomposition; Dependency-preserving decomposition; Surrogate key; Boyce-Codd normal form (BCNF); Multivalued dependency (MVD); Fourth normal form (4NF); Fifth normal form (5NF)
One-page revision summary
- Schema refinement uses functional dependencies to detect redundancy in a relation and removes it by decomposing the relation into smaller relations.
- Redundancy wastes storage and causes insertion, deletion and update anomalies, which make the data hard to keep consistent.
- Every decomposition must have a lossless join and should preserve dependencies; its cost is the extra joins that queries then need.
- Armstrong's axioms (reflexivity, augmentation and transitivity) are sound and complete, and they derive union, decomposition and pseudotransitivity.
- X is a superkey when the closure X+ contains every attribute of R, and a candidate key when no proper subset of X is also a superkey.
- A minimal cover of F is an equivalent set of FDs with single attributes on the right, no extraneous attribute on any left side and no redundant FD.
- 1NF needs atomic values, 2NF forbids partial dependencies of non-prime attributes, and 3NF also forbids transitive dependencies of non-prime attributes.
- When only FDs are given, a binary decomposition into R1 and R2 is lossless exactly when the common attributes R1 ∩ R2 form a superkey of R1 or of R2.
- A decomposition preserves dependencies when the FDs that hold inside the separate relations together imply all of F.
- A 3NF decomposition that is both lossless and dependency preserving always exists, while a BCNF decomposition is lossless but may lose an FD.
- A surrogate key is a system-generated key with no business meaning, such as an auto-increment number, used as the primary key instead of a long, composite or changeable natural key.
- Adding a surrogate key does not remove redundancy: the FDs among the real attributes must still be normalized, and the natural key should keep a UNIQUE constraint.
- BCNF requires every determinant of a non-trivial FD to be a superkey, and any relation with only two attributes is in BCNF.
- An MVD X →→ Y says the Y values for an X value are independent of the other attributes; every FD is an MVD, and X →→ Y implies X →→ R − X − Y.
- A relation is in 4NF when the left side of every non-trivial MVD is a superkey; every 4NF relation is in BCNF.
- The decomposition of R into XY and XZ, where Z = R − X − Y, is lossless exactly when X →→ Y holds.
- A join dependency says a relation equals the join of several of its projections, and 5NF requires every non-trivial join dependency to follow from the candidate keys.
- Each normal form is stricter than the one before it: every 5NF relation is in 4NF, every 4NF relation is in BCNF, and every BCNF relation is in 3NF.
Learn these by heart
- Closure X+: start with X; while some FD L → M has L inside the result, add M; stop when nothing changes.
- Lossless binary split (FDs only): R1 ∩ R2 → R1 or R1 ∩ R2 → R2 must be in F+.
- Dependency preserving: (F1 ∪ F2 ∪ … ∪ Fn)+ = F+, where Fi is the part of F+ on the attributes of Ri.
- 3NF: for every FD X → A, it is trivial, or X is a superkey, or A is a prime attribute.
- BCNF: for every non-trivial FD X → Y, X is a superkey.
- 4NF: for every non-trivial MVD X →→ Y, X is a superkey.
- Armstrong's axioms: reflexivity (Y ⊆ X gives X → Y), augmentation (X → Y gives XZ → YZ), transitivity (X → Y and Y → Z give X → Z).
2-mark questions
1 Define a functional dependency. When is a functional dependency trivial? 2 marks
In a relation R, a functional dependency X → Y holds when any two tuples that agree on the attributes X also agree on the attributes Y; we say X determines Y. Example: roll → sname in STUDENT. X → Y is trivial when Y ⊆ X, such as {roll, sname} → roll, because it holds in every relation.
2 What is a surrogate key? Give an example. 2 marks
A surrogate key is an artificial primary key with no business meaning, usually a system-generated integer from an auto-increment column or a sequence. Example: cust_id 1, 2, 3 in CUSTOMER instead of the natural key (name, phone). It is used when the natural key is long, composite or changeable; the natural key still gets a UNIQUE constraint.
3 Distinguish a partial dependency from a transitive dependency. 2 marks
A partial dependency is X → A, with A non-prime and X a proper part of a candidate key, as roll → sname when the key is {roll, cid}; 2NF forbids it. A transitive dependency is K → X → A, with K a key, X not a superkey and A non-prime, as roll → dept → hod; 3NF forbids it.
4 When is a relation in Boyce-Codd normal form (BCNF)? 2 marks
A relation R is in BCNF if, for every non-trivial functional dependency X → Y that holds on R, X is a superkey of R. BCNF is stricter than 3NF, which also allows X → A when A is a prime attribute. Every BCNF relation is in 3NF, but not every 3NF relation is in BCNF.
5 What is a multivalued dependency? When is it trivial? 2 marks
X →→ Y holds in R when the Y values for each X value are independent of the other attributes Z = R − X − Y: if (x, y1, z1) and (x, y2, z2) are in R, so are (x, y1, z2) and (x, y2, z1). It is trivial when Y ⊆ X or X ∪ Y = R.
6 What is a join dependency? When is a relation in fifth normal form (5NF)? 2 marks
A join dependency *(R1, R2, …, Rn) holds on R when every legal instance of R equals the natural join of its projections on R1, …, Rn; it is trivial when some Ri is R itself. R is in 5NF, also called project-join normal form, when every non-trivial join dependency on R is implied by the candidate keys of R.
10-mark questions
1 What is the purpose of schema refinement (normalization)? Explain insertion, deletion and update anomalies with an example relation, and show how decomposition removes them. 10 marks
Schema refinement is the step of database design that checks a relation schema for redundancy and, where it finds a problem, replaces the relation by smaller relations. Normalization does this in a systematic way, using functional dependencies (FDs) and a series of normal forms.
Purpose of normalization:
- Remove redundancy, so that each fact is stored once.
- Avoid insertion, deletion and update anomalies.
- Keep the data consistent without extra checking code.
- Do this without losing information (lossless join) and, where possible, without losing FDs (dependency preservation).
Example. EMP_DEPT(eid, ename, dno, dname, dmgr) with the FDs eid → ename, dno and dno → dname, dmgr. The only candidate key is eid.
eid ename dno dname dmgr
E1 Ravi 10 Sales Kiran
E2 Sita 10 Sales Kiran
E3 Anil 20 HR Meena
E4 Lata 10 Sales KiranThe department facts (10, Sales, Kiran) are repeated for every employee of department 10. This redundancy causes three anomalies.
1. Insertion anomaly: a new department 30 (Accounts) that has no employees yet cannot be stored, because its row would need a null value for the key eid. 2. Deletion anomaly: deleting E3, the only employee of department 20, also deletes the fact that department 20 is HR and is managed by Meena. 3. Update anomaly: if the manager of Sales changes, three rows must be changed; changing only some of them leaves the data inconsistent.
The cause is the FD dno → dname, dmgr, whose left side dno is not a key: dname and dmgr depend on eid only transitively, through dno, so EMP_DEPT is not in 3NF.
Decomposition. Split the relation on that FD into EMP(eid, ename, dno) and DEPT(dno, dname, dmgr), where dno in EMP is a foreign key that refers to DEPT.
EMP DEPT
eid ename dno dno dname dmgr
E1 Ravi 10 10 Sales Kiran
E2 Sita 10 20 HR Meena
E3 Anil 20
E4 Lata 10Now department 30 can be inserted into DEPT alone, deleting E3 keeps department 20, and the Sales manager is stored in one row. The join of EMP and DEPT on dno gives back exactly the four original rows, because dno is the key of DEPT, so the decomposition is lossless. Both FDs lie inside one relation each, so it is also dependency preserving.
Normalization has a cost: queries need joins to rebuild the full data, so designers sometimes keep a read-heavy table denormalized on purpose. In conclusion, schema refinement uses FDs to find redundancy and removes it by lossless decomposition.
2 Explain functional dependencies and Armstrong's axioms. For R(A, B, C, D, E) with F = {A → B, B → C, CD → E, E → A}, compute attribute closures and find all candidate keys of R. 10 marks
A functional dependency (FD) X → Y on a relation R means that any two tuples that agree on X also agree on Y, for example roll → sname.
Armstrong's axioms. Three rules derive F+, the set of all FDs implied by F; they are sound (only valid FDs) and complete (all of F+):
- Reflexivity: if Y ⊆ X, then X → Y.
- Augmentation: if X → Y, then XZ → YZ.
- Transitivity: if X → Y and Y → Z, then X → Z.
Derived rules: union (X → Y, X → Z give X → YZ), decomposition (X → YZ gives X → Y) and pseudotransitivity (X → Y, WY → Z give WX → Z). Example: CD → E and E → A give CD → A by transitivity; with A → B this gives CD → B.
Attribute closure. X+ is every attribute that X determines: start with X and keep adding the right side of any FD whose left side is inside the result. X is a superkey if X+ is all of R, and a candidate key if also no proper subset of X is a superkey.
Problem: R(A, B, C, D, E), F = {A → B, B → C, CD → E, E → A}. In the FD diagram, the box CD stands for the left side of CD → E.
Step 1: single attributes.
- A+ = ABC (A → B, then B → C)
- B+ = BC, C+ = C, D+ = D
- E+ = ABCE (E → A, A → B, B → C)
No single attribute is a key.
Step 2: D is on no right side, so nothing else can determine it and D must be in every key. Try D with each other attribute:
- AD+: A → B gives ABD, B → C gives ABCD, CD → E gives ABCDE.
- BD+: B → C gives BCD, CD → E gives BCDE, E → A gives ABCDE.
- CD+: CD → E gives CDE, E → A gives ACDE, A → B gives ABCDE.
- DE+: E → A gives ADE, A → B gives ABDE, B → C gives ABCDE.
Step 3: minimality. No single attribute is a key, so all four are minimal; any other superkey contains D plus one of A, B, C or E, so it contains one of them.
Result: the candidate keys are AD, BD, CD and DE. Every attribute is prime, so R is in 3NF; but in A → B the left side A is not a superkey, so R is not in BCNF.
In conclusion, attribute closure tests FDs and finds keys, and Armstrong's axioms justify each step.
3 Explain 1NF, 2NF and 3NF. Normalize ENROL(roll, sname, dept, hod, cid, ctitle, grade) up to 3NF, given roll → sname, dept; dept → hod; cid → ctitle; and roll, cid → grade. 10 marks
Normal forms are conditions on a relation that limit redundancy; each higher form includes the one below it.
- 1NF: every attribute value is atomic (single and indivisible); there are no repeating groups or multi-valued cells.
- 2NF: the relation is in 1NF and no non-prime attribute depends on a proper part of a candidate key (no partial dependency). A prime attribute is one that belongs to some candidate key.
- 3NF: the relation is in 2NF and no non-prime attribute depends transitively on a key. Equivalently, for every FD X → A, the FD is trivial, X is a superkey, or A is prime.
Step 1: 1NF. Suppose student data is first kept with a list of courses in one cell:
roll sname courses
21 Hari CS301, CS302This is not in 1NF. Storing one row per course gives ENROL(roll, sname, dept, hod, cid, ctitle, grade), in which every value is atomic.
Step 2: find the key. (roll, cid)+ contains all seven attributes, while roll+ = {roll, sname, dept, hod} and cid+ = {cid, ctitle}. So the only candidate key is (roll, cid), and the non-prime attributes are sname, dept, hod, ctitle and grade.
Step 3: 2NF. roll → sname, dept, hod and cid → ctitle are partial dependencies, because roll and cid are each only part of the key. Move each part of the key, with the attributes it determines, to its own relation:
- STUDENT(roll, sname, dept, hod), key roll
- COURSE(cid, ctitle), key cid
- ENROL(roll, cid, grade), key (roll, cid)
All three are now in 2NF.
Step 4: 3NF. In STUDENT, roll → dept and dept → hod, and dept is not a key, so hod depends transitively on roll; if a department's head changes, every student row of that department must change. Split STUDENT:
- STUDENT(roll, sname, dept), key roll
- DEPT(dept, hod), key dept
Final 3NF schema: STUDENT(roll, sname, dept), DEPT(dept, hod), COURSE(cid, ctitle) and ENROL(roll, cid, grade). In each of the four, every FD has a key on its left side, so all of them are in 3NF (in fact in BCNF). Each split was made on an FD whose left side became the key of one part, so every join is lossless, and each of the four given FDs lies inside one relation, so the dependencies are preserved.
In conclusion, 1NF removes multi-valued cells, 2NF removes partial dependencies and 3NF removes transitive dependencies.
4 Define BCNF and compare it with 3NF. Test R(student, subject, teacher) with {student, subject} → teacher and teacher → subject for 3NF and BCNF, decompose it into BCNF, and check whether the result is lossless and dependency preserving. 10 marks
Boyce-Codd normal form (BCNF). A relation R is in BCNF if, for every non-trivial FD X → Y that holds on R, X is a superkey of R. In words, every determinant must be a key.
Comparison with 3NF:
- 3NF allows X → A when X is not a superkey, provided A is a prime attribute; BCNF has no such exception.
- Every BCNF relation is in 3NF, but a 3NF relation can still have redundancy that BCNF removes.
- A lossless, dependency-preserving 3NF decomposition always exists; a lossless BCNF decomposition always exists, but it may not preserve every FD.
Example. R(student, subject, teacher): each teacher teaches one subject (teacher → subject), and for each subject a student has one teacher ({student, subject} → teacher).
Step 1: candidate keys.
- {student, subject}+ = {student, subject, teacher}, so it is a key.
- {student, teacher}+: teacher → subject adds subject, so it is also a key.
- No single attribute is a key: student+ = {student}, subject+ = {subject}, teacher+ = {teacher, subject}.
So all three attributes are prime.
Step 2: 3NF test. In teacher → subject, teacher is not a superkey, but subject is prime, so the FD is allowed; {student, subject} → teacher has a key on its left. R is in 3NF.
Step 3: BCNF test. teacher → subject has a left side that is not a superkey, so R is not in BCNF. The redundancy: the fact that a teacher teaches a subject is repeated for every student of that teacher.
Step 4: BCNF decomposition. For a violating FD X → Y, with X and Y disjoint, replace R by X ∪ Y and R − Y:
- R1(teacher, subject), key teacher
- R2(student, teacher), key {student, teacher}
Both are in BCNF.
Step 5: lossless join. R1 ∩ R2 = {teacher}, and teacher → subject makes teacher a key of R1, so the join is lossless.
Step 6: dependency preservation. teacher → subject lies in R1, but {student, subject} → teacher spans both relations and does not follow from the FDs of R1 and R2, so it is lost. These tables are each valid on their own:
R1 teacher subject R2 student teacher
Rao DBMS S1 Rao
Devi DBMS S1 DeviTheir join gives (S1, DBMS, Rao) and (S1, DBMS, Devi): student S1 now has two DBMS teachers, which breaks {student, subject} → teacher, and neither table alone can detect it.
In conclusion, R is in 3NF but not in BCNF; its BCNF decomposition is lossless but not dependency preserving, which is the usual trade-off between the two forms.
5 Explain lossless-join and dependency-preserving decomposition with their tests. For R(A, B, C, D) with F = {A → B, B → C, C → D}, check D1 = {AB, ACD}, D2 = {AB, BC, CD} and D3 = {AD, BCD}. 10 marks
A decomposition replaces R by smaller relations R1, …, Rn whose attributes together make up R. It should have two properties.
1. Lossless join. For every legal instance r of R, joining the projections gives back exactly r: πR1(r) ⋈ … ⋈ πRn(r) = r. The join always contains r; a lossy decomposition adds spurious tuples, so the true facts can no longer be told apart. Test for two relations: {R1, R2} is lossless if and only if R1 ∩ R2 → R1 or R1 ∩ R2 → R2 is in F+, that is, the common attributes form a superkey of one of the two.
2. Dependency preservation. Let Fi be the FDs of F+ that use only attributes of Ri. The decomposition preserves dependencies if (F1 ∪ … ∪ Fn)+ = F+, so every FD can be checked inside one relation without a join. Test for X → Y: set result = X, then for each Ri repeat result = result ∪ ((result ∩ Ri)+ ∩ Ri) until nothing changes; the FD is preserved if Y ⊆ result.
Example. R(A, B, C, D), F = {A → B, B → C, C → D}; the only key is A.
D1 = {AB, ACD}
- Lossless: AB ∩ ACD = A, and A+ = ABCD, so A is a key of AB. Lossless.
- Preservation: A → B lies in AB and C → D in ACD. For B → C, start with result = B: in AB, B+ ∩ AB = BCD ∩ AB = B, and ACD has no B, so the result stays B; B → C is not preserved.
D2 = {AB, BC, CD}
- Lossless: join AB and BC on B, a key of BC (B → C); then join ABC and CD on C, a key of CD (C → D). Both steps are lossless.
- Preservation: each FD lies inside one relation, so all are preserved.
D3 = {AD, BCD}
- Lossless: AD ∩ BCD = D, and D+ = D, a key of neither. Lossy.
- Preservation: B → C and C → D lie in BCD, but A → B is lost.
Spurious tuples in D3. This instance satisfies F:
A B C D
a1 b1 c1 d1
a2 b2 c2 d1πAD gives (a1, d1) and (a2, d1); πBCD gives (b1, c1, d1) and (b2, c2, d1). Their join on D has four tuples: the two originals plus the spurious (a1, b2, c2, d1) and (a2, b1, c1, d1). With D1, the join on A gives back exactly the two originals.
In conclusion, D2 is lossless and dependency preserving, D1 is lossless but loses B → C, and D3 is lossy. A lossless join is compulsory; dependency preservation is desirable.
6 Explain multivalued dependency and fourth normal form (4NF) with an example. Then explain join dependency and fifth normal form (5NF) with an example. 10 marks
Multivalued dependency (MVD). X →→ Y holds in R when each X value has a set of Y values that is independent of the remaining attributes Z = R − X − Y: if (x, y1, z1) and (x, y2, z2) are in r, then (x, y1, z2) and (x, y2, z1) are in r too. MVDs come in pairs (X →→ Y implies X →→ Z), and every FD is also an MVD.
Example. CTB(course, teacher, book): a course has several teachers and several books, and every teacher of a course uses every book of it.
course teacher book
DBMS Rao B1
DBMS Rao B2
DBMS Devi B1
DBMS Devi B2Here course →→ teacher and course →→ book hold, but course does not determine teacher or book and no other FD is given, so the only key is all three attributes and CTB is in BCNF. Still, adding a book B3 needs two new rows, one per teacher.
Fourth normal form (4NF). R is in 4NF if, for every non-trivial MVD X →→ Y, X is a superkey. CTB violates 4NF because course is not a superkey. Decompose on the MVD into CT(course, teacher) and CB(course, book). Their join on course gives back exactly the four rows, so the split is lossless; in general {XY, XZ} is lossless exactly when X →→ Y holds. Every 4NF relation is in BCNF.
Join dependency (JD). *(R1, …, Rn) holds when every legal instance of R equals the join of its projections on R1, …, Rn. An MVD is a JD with two parts.
Fifth normal form (5NF). R is in 5NF if every non-trivial JD on R is implied by its candidate keys.
Example. SUPPLY(agent, company, product), with the rule: if an agent works for a company, sells a product, and the company makes that product, then the agent sells that product for that company.
agent company product
Ravi Alpha Fan
Ravi Alpha TV
Ravi Beta TV
Uma Alpha TVWrite A, C and P for agent, company and product. No non-trivial MVD holds, so SUPPLY is in 4NF. Joining any two projections gives five rows, one spurious; for example AC ⋈ AP adds (Ravi, Beta, Fan). Joining all three gives back exactly the four rows, so the JD *(AC, AP, CP) holds. The only key is all three attributes, which does not imply this JD, so SUPPLY is not in 5NF; it is replaced by AC, AP and CP.
In conclusion, 4NF removes redundancy caused by independent MVDs, and 5NF removes redundancy that only a split into three or more parts can remove.
Transactions, Concurrency Control, Recovery and Indexing
Syllabus: Transaction concept and transaction states; ACID properties; Concurrent executions; Serializability and testing for serializability; Recoverability; Implementation of isolation; Lock-based concurrency protocols; Timestamp-based concurrency protocols; Optimistic (validation-based) concurrency protocols; Deadlocks; Failure classification and storage; Recovery and atomicity, and the recovery algorithm; B+ trees and operations on B+ trees; Hash-based indexing
One-page revision summary
- A transaction is a logical unit of work that passes through the states active, partially committed, committed, failed and aborted.
- Atomicity and durability come from the recovery system, isolation from concurrency control, and consistency from the programmer with integrity constraints.
- Concurrent execution raises throughput and resource utilisation and cuts waiting time, but it must be controlled to avoid lost updates and dirty reads.
- A schedule is conflict serializable exactly when its precedence graph has no cycle, and a topological sort of the graph gives an equivalent serial order.
- Every conflict-serializable schedule is view serializable, and a view-serializable schedule that is not conflict serializable always contains a blind write.
- A schedule is recoverable when each reader commits after the writer it read from, and cascadeless when every read sees only committed data.
- Isolation is implemented by locking, timestamps, validation or multiple versions, and SQL lets a transaction choose a weaker isolation level for more concurrency.
- Two-phase locking guarantees conflict serializability; strict two-phase locking also makes schedules cascadeless, but neither form prevents deadlock.
- Timestamp ordering never makes a transaction wait, so it is deadlock-free, and a rolled-back transaction restarts with a new timestamp.
- The validation-based protocol takes a transaction's validation time as its timestamp and works best when most transactions do not conflict.
- A deadlock exists exactly when the wait-for graph has a cycle; it is prevented by wait-die, wound-wait or timeouts, or detected and broken by rolling back a victim.
- Failures are transaction failures, system crashes and disk failures, and storage is volatile, non-volatile or stable.
- Under write-ahead logging, the log records for a block reach stable storage before the block itself is written to disk.
- A checkpoint limits how much of the log must be scanned after a crash, because recovery starts its redo phase at the last checkpoint.
- In a B+ tree all leaves are at the same level and linked in key order; a leaf split copies a key up, while an internal split moves a key up.
- Static hashing sends each key to a fixed bucket through a hash function and handles full buckets with chains of overflow buckets.
- Extendible hashing splits only the full bucket and doubles its directory only when that bucket's local depth equals the global depth.
- A hash index suits equality search, while a B+ tree supports both equality and range search.
Learn these by heart
- Two operations conflict when they belong to different transactions, access the same data item, and at least one of them is a write.
- Two-phase locking: a transaction may not obtain any lock after it has released a lock.
- Timestamp ordering: reject read(Q) by Ti if TS(Ti) < W-TS(Q); reject write(Q) if TS(Ti) < R-TS(Q) or TS(Ti) < W-TS(Q), and under the Thomas write rule ignore the write in the second case.
- Validation test for Tj: for every Ti with TS(Ti) < TS(Tj), either Finish(Ti) < Start(Tj), or Start(Tj) < Finish(Ti) < Validation(Tj) and the write set of Ti does not intersect the read set of Tj.
- Recovery: redo forward from the last checkpoint, repeating every update, then undo backward every transaction left in undo-list and write its abort record.
- Wait-die: older waits, younger dies. Wound-wait: older wounds the younger holder, younger waits.
- With n pointers per node, a non-root B+ tree leaf holds between ⌈(n−1)/2⌉ and n−1 keys, and a non-root internal node has between ⌈n/2⌉ and n children.
2-mark questions
1 What is a cascadeless schedule? Is every cascadeless schedule recoverable? 2 marks
A schedule is cascadeless if every transaction reads a data item only after the transaction that last wrote it has committed, so one abort never forces other transactions to roll back.
Yes. A reader sees only committed data, so the writer always commits before the reader commits, which is the condition for a recoverable schedule.
2 Name the SQL isolation levels and the ways a DBMS can implement isolation. 2 marks
SQL defines four levels, strongest first:
- Serializable: execution must be serializable.
- Repeatable read: only committed data, and repeated reads agree, but phantom rows may appear.
- Read committed: only committed data, but repeated reads may differ.
- Read uncommitted: uncommitted data may be read.
Isolation is implemented by locking, timestamps, or multiple versions (snapshot isolation).
3 What are the three phases of the validation-based (optimistic) concurrency protocol? 2 marks
- Read phase: the transaction reads data and writes only to local variables.
- Validation phase: when it finishes, the system tests whether applying its writes could break serializability.
- Write phase: if the test passes, the local values are written to the database; otherwise the transaction is rolled back.
Its timestamp is its validation time.
4 Distinguish the wait-die and wound-wait deadlock prevention schemes. 2 marks
Both compare start timestamps; the older transaction has the smaller timestamp.
- Wait-die (non-preemptive): an older requester waits for a younger holder; a younger requester dies (is rolled back).
- Wound-wait (preemptive): an older requester wounds (rolls back) the younger holder; a younger requester waits.
A rolled-back transaction restarts with its original timestamp, so it cannot starve.
5 What is stable storage, and how is it approximated in practice? 2 marks
Stable storage never loses its information, whatever failure occurs. It is approximated by keeping each block on two or more non-volatile disks, ideally at different sites, and writing the copies one after another: the second write starts only after the first finishes. A failure during a write then leaves at least one correct copy.
6 How does extendible hashing differ from static hashing? 2 marks
In static hashing a hash function maps each key to one of a fixed number of buckets; a growing file forms slow overflow chains.
Extendible hashing keeps a directory of 2^d bucket pointers indexed by d bits of the hash value (global depth d). Only a full bucket splits, and the directory doubles only when its local depth equals d.
10-mark questions
1 What is a transaction? Explain the states of a transaction with a state diagram, and explain the ACID properties using a funds-transfer example. 10 marks
A transaction is a unit of program execution that reads and possibly updates data items. It must behave as one logical unit of work: either all its operations take effect or none do.
Example: transaction T transfers 500 from account A to account B.
read(A)
A := A - 500
write(A)
read(B)
B := B + 500
write(B)Before T, A = 2000 and B = 1000, so A + B = 3000.
Transaction states: 1. Active: the initial state, while the statements execute. 2. Partially committed: after the final statement has executed, but before the changes are made permanent. 3. Failed: normal execution can no longer proceed, because of an error in the active state or a failure before the changes are made permanent. 4. Aborted: the transaction has been rolled back and the database restored to its state before T started. The system may then restart T (if the cause was not T's own logic) or kill it. 5. Committed: after successful completion, once its changes are permanent.
A transaction that has committed or aborted is terminated.
ACID properties: 1. Atomicity: all operations of T are reflected in the database, or none are. If the system fails after write(A) but before write(B), the database shows A = 1500 and B = 1000, and 500 has vanished. The recovery system uses the log to undo write(A). 2. Consistency: T run alone on a consistent database leaves it consistent. Here A + B must stay 3000; after T, A = 1500 and B = 1500. This is the programmer's job, helped by integrity constraints. 3. Isolation: concurrent transactions must each behave as if they ran alone. A transaction that adds A + B between write(A) and write(B) would see 2500. The concurrency-control system prevents this. 4. Durability: once T commits, A = 1500 and B = 1500 survive any later crash. The recovery system ensures this by writing the updates, or log records describing them, to stable storage before commit completes.
Conclusion: the states describe the life of a transaction, and ACID lists the guarantees the DBMS gives; atomicity and durability come from the recovery system and isolation from concurrency control.
2 Classify the failures and the types of storage in a database system. Explain the log-based recovery algorithm and apply it to the log below after a system crash. 10 marks
The recovery system keeps transactions atomic and durable in spite of failures, using a log kept on stable storage.
Failure classification:
- Transaction failure: a logical error (bad input, overflow) or a system error such as deadlock forces one transaction to abort.
- System crash: a hardware fault or software bug halts the system; volatile storage is lost, non-volatile storage survives.
- Disk failure: disk blocks are destroyed; recovery uses copies on other disks or archival backups.
Storage types: volatile (main memory, lost in a crash), non-volatile (disk, survives a crash) and stable (never loses data, approximated by copies on several non-volatile disks).
Log records are <Ti start>, <Ti, X, old value, new value>, <Ti commit>, <Ti abort> and <checkpoint L>, where L lists the transactions active at the checkpoint. A log record reaches stable storage before the block it describes is written to disk (write-ahead logging), and a checkpoint writes all modified blocks to disk.
Recovery algorithm, when the system restarts: 1. Redo phase: find the last checkpoint record and set undo-list = L. Scan forward, redoing every update (write the new value). On <Ti start>, add Ti to undo-list; on <Ti commit> or <Ti abort>, remove Ti. 2. Undo phase: scan backward from the end. For each update by a transaction in undo-list, restore the old value and write a redo-only record <Ti, X, old value>. On reaching <Ti start> of such a transaction, write <Ti abort> and remove Ti. Stop when undo-list is empty; normal processing resumes.
Example log:
1 <T1 start>
2 <T1, X, 500, 450>
3 <T1 commit>
4 <T2 start>
5 <T2, Y, 300, 360>
6 <checkpoint {T2}>
7 <T3 start>
8 <T3, Z, 40, 70>
9 <T2, X, 450, 420>
10 <T2 commit>
11 <T3, Y, 360, 330>
--- system crash ---Redo phase from record 6: undo-list = {T2}. Record 7 adds T3; redo Z = 70 and X = 420; record 10 removes T2; redo Y = 330. Undo-list = {T3}.
Undo phase: record 11 sets Y = 360 and writes <T3, Y, 360>; record 8 sets Z = 40 and writes <T3, Z, 40>; record 7 writes <T3 abort> and empties the list.
Result: X = 420, Y = 360, Z = 40. T1 finished before the checkpoint and needs nothing, committed T2 is redone, and incomplete T3 is undone.
Conclusion: redo restores committed work (durability) and undo removes incomplete work (atomicity).
3 Why are concurrent executions allowed? For the schedule S below, draw the precedence graph, decide whether S is conflict serializable, and check whether it is recoverable and cascadeless. 10 marks
In a concurrent execution the operations of several transactions are interleaved. It is allowed because it raises throughput and resource utilisation (one transaction uses the CPU while another waits for the disk) and cuts average waiting time, since short transactions need not queue behind long ones. Uncontrolled interleaving can cause lost updates and dirty reads, so only serializable schedules are allowed.
Two operations conflict if they belong to different transactions, use the same item, and at least one is a write. S is conflict serializable if it is conflict equivalent to a serial schedule.
Step T1 T2 T3
1 r(A)
2 r(B)
3 w(B)
4 commit
5 r(B)
6 w(A)
7 r(A)
8 w(A)
9 r(B)
10 commit
11 commitTesting with a precedence graph: 1. Draw a node for each transaction: T1, T2, T3. 2. For each conflicting pair, draw an edge from the transaction whose operation comes first:
- w2(B) at step 3 before r1(B) at step 5: T2 → T1 on B
- w2(B) at step 3 before r3(B) at step 9: T2 → T3 on B
- r1(A) at step 1 before w3(A) at step 8: T1 → T3 on A
- w1(A) at step 6 before r3(A) and w3(A) at steps 7 and 8: T1 → T3 on A
3. Look for a cycle. The edges T2 → T1, T1 → T3 and T2 → T3 form no cycle.
So S is conflict serializable, and a topological sort gives its only equivalent serial order: T2, T1, T3.
Recoverability: S is recoverable if, whenever Tj reads an item written by Ti, Ti commits before Tj commits.
- T1 reads B from T2 at step 5; T2 committed at step 4, so this is fine.
- T3 reads A from T1 at step 7 and commits at step 10, but T1 commits only at step 11. If T1 failed after step 10, the committed T3 could not be undone. So S is not recoverable.
Cascadeless: every read must see committed data. T3 reads A at step 7 before T1 commits, so S is not cascadeless either.
Repairs: moving T3's commit after T1's commit makes S recoverable but still not cascadeless; moving T1's commit to just before step 7 makes it cascadeless, and hence recoverable. In both cases the serial order stays T2, T1, T3.
Conclusion: serializability and recoverability are separate tests, and a correct schedule must pass both.
4 Explain the two-phase locking protocol and its strict and rigorous forms. Trace the lock requests below, draw the wait-for graph, and explain how the deadlock is detected or prevented. 10 marks
In a lock-based protocol a transaction must lock a data item before using it. A shared lock, lock-S(Q), allows reading; an exclusive lock, lock-X(Q), allows reading and writing. The lock manager grants a request only if it is compatible with the locks held by other transactions:
Held \ Requested S X
S yes no
X no noTwo-phase locking (2PL): 1. Growing phase: the transaction may obtain locks but not release any. 2. Shrinking phase: once it releases a lock, it may not obtain a new one. The moment it gets its last lock is its lock point. Every 2PL schedule is conflict serializable, in the order of the lock points. An S lock may be upgraded to X only in the growing phase.
Basic 2PL still allows cascading rollback and deadlock.
- Strict 2PL holds every exclusive lock until commit or abort, so no one reads uncommitted data and schedules are cascadeless.
- Rigorous 2PL holds all locks until commit or abort; transactions are then serializable in commit order.
Trace (T1 is the oldest, T3 the youngest):
Step Request Result
1 T1 lock-X(A) granted
2 T2 lock-X(B) granted
3 T3 lock-S(C) granted
4 T1 lock-X(B) waits, T2 holds B
5 T2 lock-X(C) waits, T3 holds C
6 T3 lock-S(A) waits, T1 holds AAll three are in their growing phase, and each waits for the next.
Deadlock detection: the wait-for graph has an edge Ti → Tj when Ti waits for a lock that Tj holds. Here T1 waits for B held by T2, T2 waits for C held by T3, and T3 waits for A held by T1: the cycle T1 → T2 → T3 → T1 means a deadlock.
The system picks a victim, say T3, the youngest, and rolls it back. Its lock on C is released, T2 gets lock-X(C), finishes and releases B, and then T1 gets lock-X(B). The number of past rollbacks is counted when choosing a victim, so that the same transaction does not starve.
Deadlock prevention with timestamps:
- Wait-die: at step 4 the older T1 waits for T2; at step 5 T2 waits for T3; at step 6 the younger T3 requests a lock held by the older T1 and dies, so no cycle forms.
- Wound-wait: at step 4 the older T1 wounds T2, which is rolled back and releases B.
A lock timeout is a simpler alternative.
Conclusion: 2PL gives conflict serializability, strict 2PL adds cascadelessness, and deadlocks are detected with a wait-for graph or prevented by timestamp schemes.
5 Explain the timestamp-ordering protocol. Apply it, with and without the Thomas write rule, to the schedule S: r1(A), r2(B), w2(A), w1(A), r1(B), w2(B), where TS(T1) = 10 and TS(T2) = 20. Compare it briefly with the validation-based protocol. 10 marks
In timestamp ordering (TO) each transaction Ti gets a unique timestamp TS(Ti) when it starts; an older transaction has a smaller timestamp. Conflicting operations must run in timestamp order, so every accepted schedule is equivalent to the serial schedule in that order. For each item Q the system keeps W-TS(Q) and R-TS(Q), the largest timestamps of transactions that wrote and read Q successfully.
Rules: 1. Ti issues read(Q): if TS(Ti) < W-TS(Q), a younger transaction has already overwritten Q, so the read is rejected and Ti is rolled back. Otherwise the read runs and R-TS(Q) = max(R-TS(Q), TS(Ti)). 2. Ti issues write(Q): if TS(Ti) < R-TS(Q), a younger transaction has already read Q, so Ti is rolled back. If TS(Ti) < W-TS(Q), the value is obsolete and Ti is rolled back. Otherwise the write runs and W-TS(Q) = TS(Ti). A rolled-back transaction restarts with a new timestamp.
Thomas write rule: in the second case of rule 2, the obsolete write is ignored and Ti continues.
Trace (all R-TS and W-TS start at 0; step 5 runs only under the Thomas rule):
Step Op Test Result
1 r1(A) 10 ≥ W-TS(A)=0 R-TS(A)=10
2 r2(B) 20 ≥ W-TS(B)=0 R-TS(B)=20
3 w2(A) 20 ≥ R-TS(A)=10 W-TS(A)=20
20 ≥ W-TS(A)=0
4 w1(A) 10 ≥ R-TS(A)=10 see below
10 < W-TS(A)=20
5 r1(B) 10 ≥ W-TS(B)=0 R-TS(B)=20
6 w2(B) 20 ≥ R-TS(B)=20 W-TS(B)=20
20 ≥ W-TS(B)=0Basic TO: at step 4, TS(T1) = 10 < W-TS(A) = 20, so T1 is rolled back and step 5 never runs. T2 completes step 6, and T1 later restarts with a new timestamp.
With the Thomas write rule: step 4 passes the read test (10 ≥ 10) and is ignored; steps 5 and 6 run (R-TS(B) stays 20, the larger value), and both transactions finish.
Why ignoring is safe: S has the conflicts r1(A) before w2(A) and r1(B) before w2(B), giving T1 → T2, and w2(A) before w1(A), giving T2 → T1. This cycle means S is not conflict serializable. With the ignored write removed only T1 → T2 remains, so the result is equivalent to the serial order T1, T2, in which T2's value of A would overwrite T1's anyway.
TO is free from deadlock because no transaction waits, but long transactions may starve, and schedules may not be recoverable unless writes are held back until commit.
Validation-based protocol: a transaction runs a read phase on local copies, then a validation phase, and writes to the database only if validation succeeds. Its timestamp is its validation time. It suits workloads with few conflicts, whereas TO checks every operation as it happens.
Conclusion: TO enforces serializability by timestamps, and the Thomas rule accepts more schedules by discarding obsolete writes.
6 Construct a B+ tree by inserting the keys 8, 14, 2, 20, 11, 5, 17, 25, 29 in that order, where each node holds at most 3 keys. Explain how a search works, and then delete 17 and 5. 10 marks
A B+ tree is a balanced multi-level index. All leaves are at the same depth and hold every search-key value with record pointers, and each leaf points to the next leaf for range queries. Internal nodes hold only separator keys.
Convention: a node holds at most 3 keys (4 child pointers); a non-root leaf keeps at least 2 keys and a non-root internal node at least 2 children. Between keys k1 and k2 of a node lies the subtree for keys k with k1 ≤ k < k2.
Insertion: 1. Find the correct leaf and insert the key in sorted order. 2. If the leaf now has 4 keys, split it: the left leaf keeps the first 2, the right leaf gets the last 2, and the first key of the right leaf is copied up into the parent. 3. If the parent overflows, it splits too, but the key sent up is moved, not kept below. A root split creates a new root, the only way the tree grows taller.
8, 14, 2: one leaf [2 8 14]
20: [2 8 14 20] splits into
[2 8] and [14 20]; 14 copied up
root [14]
11: leaf [2 8 11]
5: [2 5 8 11] splits into
[2 5] and [8 11]; 8 copied up
root [8 14]
17: leaf [14 17 20]
25: [14 17 20 25] splits into
[14 17] and [20 25]; 20 copied up
root [8 14 20]
29: leaf [20 25 29]Final tree: root [8 14 20] with leaves [2 5], [8 11], [14 17] and [20 25 29].
Search: for 17, at the root 14 ≤ 17 < 20, so follow the third pointer to leaf [14 17], where 17 is found. A search for 26 reaches leaf [20 25 29] and fails. One node is read per level.
Deletion: a leaf that falls below the minimum first borrows a key from an adjacent sibling that can spare one, and merges with a sibling only when none can lend. 1. Delete 17: leaf [14 17] becomes [14], below the minimum of 2. The left sibling [8 11] cannot lend, but the right sibling [20 25 29] has 3 keys, so 20 is borrowed: leaves [14 20] and [25 29], and the root separator 20 becomes 25. Root [8 14 25]. 2. Delete 5: leaf [2 5] becomes [2]. Its only sibling [8 11] has just 2 keys, so they merge into [2 8 11] and separator 8 leaves the root: root [14 25] with leaves [2 8 11], [14 20] and [25 29].
An internal node left with too few children borrows or merges the same way, and a root left with one child is removed.
Conclusion: splits and merges keep the tree balanced, so every operation costs time proportional to its height.
Public sources that settled doubtful points
Only the points the second AI pass doubted were looked up. These are the pages that confirmed or contradicted them; nothing here is copied from them.
37 pages
- MySQL 8.4 Reference Manual: Updatable and Insertable Views
- Oracle Database 21c Administrator's Guide: Managing Views, Sequences, and Synonyms
- Oracle Database 21c SQL Language Reference: The set operators
- Multivalued dependency - Wikipedia
- B+ tree (Wikipedia)
- ANSI-SPARC Architecture (Wikipedia)
- Database Concepts and Architecture, CS 435 lecture notes, Montana State University
- Three-Schema Architecture and Data Independence, CE384 Database Design lecture slides, Sharif University of Technology
- Overall System Structure, CMSC 461 lecture notes, UMBC
- Enhanced Entity-Relationship Modeling, CS 448 lecture slides, Purdue University
- ER modeling: weak entity sets, CS 4750 Database Systems slides, University of Virginia
- Data Modeling Using the Entity-Relationship Model, lecture slides, Marquette University
- Codd's theorem (Wikipedia)
- Tuple relational calculus (Wikipedia)
- Domain relational calculus (Wikipedia)
- Null (SQL) (Wikipedia)
- Relational algebra (Wikipedia)
- Oracle Database SQL Language Reference 12.1: Data Types
- MySQL 8.0 Reference Manual: ALTER TABLE Statement
- Oracle Database SQL Language Reference: ADD_MONTHS
- Oracle Database SQL Language Reference: NEXT_DAY
- Oracle Database SQL Language Reference: MONTHS_BETWEEN
- MySQL 8.4 Reference Manual: Mathematical Functions
- MySQL 8.4 Reference Manual: Server SQL Modes
- MySQL 8.0 Reference Manual: JOIN Clause
- MySQL 8.4 Reference Manual: The View WITH CHECK OPTION Clause
- Fifth normal form - Wikipedia
- Boyce-Codd normal form - Wikipedia
- Third normal form - Wikipedia
- CSCI 4380 Database Systems, lecture 7 notes (Rensselaer Polytechnic Institute)
- Surrogate key - Wikipedia
- Armstrong's axioms - Wikipedia
- Thomas write rule (Wikipedia)
- Timestamp-based concurrency control (Wikipedia)
- Extendible hashing (Wikipedia)
- Two-phase locking (Wikipedia)
- PostgreSQL documentation: Transaction Isolation
Further reading
Titles only, for your own study. Nothing on this page is copied from them. The units follow the official JNTUK R23 CSE syllabus (PDF) ↗.
- Database Management Systems · Raghu Ramakrishnan and Johannes Gehrke
- Database System Concepts · Abraham Silberschatz, Henry F. Korth and S. Sudarshan
- An Introduction to Database Systems · C. J. Date
- Fundamentals of Database Systems · Ramez Elmasri and Shamkant B. Navathe
- Database Systems: Design, Implementation and Management · Carlos Coronel, Steven Morris and Peter Rob