Part 1 — Database Fundamentals, Architecture and Data Modeling (Q1–Q50)
Q1. What is a database?
Solution: A database is an organized collection of related data stored so that it can be accessed, managed, updated, and retrieved efficiently. Example: a university database containing students, courses, faculty, and grades.
Q2. What is a DBMS, and why is it needed?
Solution: A Database Management System is software that manages databases. It supports data definition, querying, updates, access control, integrity, concurrency, and recovery. It reduces the problems associated with isolated files.
Q3. Differentiate between DBMS and RDBMS.
Solution:
Q4. Differentiate between a file system and a DBMS.
Solution:
Q5. What are the major types of databases?
Solution: Common categories include relational, document, key-value, wide-column, graph, hierarchical, network, object-oriented, and time-series databases. Databases may also be centralized, distributed, cloud-hosted, or in-memory.
Q6. What is metadata? Give an example.
Solution: Metadata is data describing other data. For example, a table definition specifying that StudentID is an integer primary key and Name is a string contains metadata.
Q7. What is the difference between a database schema and a database instance?
Solution: A schema defines the database's structure; an instance is the actual data at a particular time. Adding a column changes the schema, while inserting a student changes the instance.
Q8. Explain logical and physical data independence.
Solution:
Logical data independence is generally harder to achieve.
Q9. What are the principal functions of a DBMS?
Solution: Data storage and retrieval, query processing, transaction management, concurrency control, integrity enforcement, authorization, backup, recovery, and catalog management.
Q10. What is data redundancy, and why can it be harmful?
Solution: Data redundancy means storing the same fact in multiple places. It can waste space and cause update, insertion, and deletion anomalies. Normalization can reduce unnecessary redundancy.
Q11. Explain the three-schema architecture of a DBMS.
Solution:
Mappings between levels help provide data independence.
Q12. A university changes the physical organization of a student table without changing applications. Which concept applies?
Solution: Physical data independence. For example, replacing a heap file with an indexed organization should not require changes to the logical table interface.
Q13. A university adds a department attribute to its conceptual schema. Which type of data independence is relevant?
Solution: Logical data independence. Existing views and applications can remain unaffected if the change is properly isolated and compatibility is maintained.
Q14. What is the difference between two-tier and three-tier database architecture?
Solution:
Three-tier architecture usually provides better separation of concerns, centralized business logic, and scalability.
Q15. What are DDL, DML, DCL, and TCL?
Solution:
Exact command classifications can vary by DBMS.
Q16. Differentiate between procedural and nonprocedural query languages.
Solution: A procedural language specifies both the desired result and the operations used to obtain it. A nonprocedural language specifies the desired result, leaving the execution strategy to the system. Relational algebra is procedural; relational calculus is declarative.
Q17. What are the ACID properties?
Solution:
Q18. A bank transfer deducts ₹1,000 from account A but crashes before crediting account B. Which ACID property is violated if the partial transfer remains committed?
Solution: Atomicity. The transfer must be treated as one logical unit. Recovery should undo incomplete effects or otherwise restore a consistent committed outcome.
Q19. Why is a DBMS catalog important?
Solution: The catalog stores metadata about tables, columns, constraints, indexes, users, and other database objects. The query optimizer and database administration tools use this information.
Q20. What is the difference between a database administrator and a database designer?
Solution: A database designer determines data structures, relationships, constraints, and schemas. A DBA manages security, performance, availability, backups, recovery, storage, and operational maintenance.
Q21. What is a data model? Name four types.
Solution: A data model describes how data, relationships, and constraints are represented. Examples include the relational, hierarchical, network, and entity-relationship models. Document and graph models are also widely used.
Q22. Differentiate between a conceptual, logical, and physical data model.
Solution:
Q23. What is an entity in an ER model?
Solution: An entity is a distinguishable real-world object or concept, such as a student, course, or department. An entity set is a collection of entities of the same type.
Q24. Differentiate between an entity, entity set, and attribute.
Solution: A particular student is an entity; all students form an entity set; StudentID and Name are attributes describing students.
Q25. What are simple, composite, single-valued, multivalued, and derived attributes?
Solution:
Q26. What is a weak entity? Give an example.
Solution: A weak entity cannot be uniquely identified using only its own attributes and depends on an owner entity. For example, a Dependent might be identified by (EmployeeID, DependentName).
Q27. Differentiate between strong and weak entities.
Solution: A strong entity has its own key. A weak entity depends on an owner entity for identification and generally has a partial key plus the owner's key.
Q28. What are the common notations used in an ER diagram?
Solution: In traditional Chen notation, rectangles represent entity sets, diamonds represent relationships, ovals represent attributes, underlined attributes indicate keys, and double rectangles represent weak entities. Other notations, such as crow's-foot notation, use different symbols.
Q29. What is a relationship in an ER model?
Solution: A relationship represents an association among entities. For example, Student ENROLLS_IN Course associates students with courses.
Q30. Explain unary, binary, and ternary relationships.
Solution:
Q31. What is cardinality in ER modeling?
Solution: Cardinality describes how many entities may participate in a relationship, commonly expressed as one-to-one, one-to-many, or many-to-many.
Q32. A department can employ many employees, but each employee belongs to at most one department. Identify the relationship.
Solution: One-to-many from Department to Employee. The employee's department reference can be represented using a foreign key.
Q33. Differentiate between cardinality ratio and participation constraint.
Solution: Cardinality ratio describes the maximum number of related entities, such as one-to-many. Participation describes whether participation is mandatory or optional; total participation means every entity must participate in the relationship.
Q34. What is specialization in an ER model?
Solution: Specialization is a top-down process that divides a superclass into subclasses based on distinguishing properties. For example, Employee may be specialized into Faculty and Administrator.
Q35. What is generalization?
Solution: Generalization is a bottom-up process that combines similar entity types into a common superclass. For example, Car and Truck can be generalized into Vehicle.
Q36. Differentiate between specialization and generalization.
Solution: Specialization moves from a general entity type to more specific subtypes; generalization moves from specific types to a shared supertype. Both support abstraction and inheritance.
Q37. What are disjoint and overlapping specialization constraints?
Solution: In disjoint specialization, an entity can belong to at most one subclass in the specialization. In overlapping specialization, it may belong to multiple subclasses.
Q38. What are total and partial specialization?
Solution: Total specialization requires every superclass entity to belong to at least one subclass. Partial specialization allows superclass entities that belong to none of the specified subclasses.
Q39. What is aggregation in ER modeling?
Solution: Aggregation treats a relationship and its participating entities as a higher-level unit so that it can participate in another relationship. It is useful when modeling a relationship about another relationship.
Q40. When is a ternary relationship preferable to three binary relationships?
Solution: Use a ternary relationship when the fact depends on the simultaneous combination of three entities. For example, the quantity supplied may depend on a particular supplier, part, and project. Replacing it with three binary relationships may lose this association.
Q41. Define superkey, candidate key, primary key, and alternate key.
Solution:
Q42. A relation has attributes (A, B, C) and functional dependencies A → B and B → C. Find a candidate key, assuming no other dependencies.
Solution: The closure of A is {A,B,C}, so A is a candidate key. Neither B nor C determines A, and neither alone determines all attributes.
Q43. What is a foreign key?
Solution: A foreign key is an attribute set whose values reference a candidate key, usually the primary key, of the same or another relation. It enforces referential integrity according to the defined constraints.
Q44. What are entity integrity and referential integrity?
Solution: Entity integrity requires primary key values to be unique and non-null. Referential integrity requires each non-null foreign key value to match a referenced key value, subject to the database's declared rules.
Q45. How is a one-to-many relationship converted into relational tables?
Solution: Put the primary key of the one-side relation as a foreign key in the many-side relation. For example, Employee(EmpID, DeptID) references Department(DeptID).
Q46. How is a many-to-many relationship converted into tables?
Solution: Create a junction relation containing the keys of both participating relations as foreign keys. For example, Enrollment(StudentID, CourseID, Grade), with (StudentID, CourseID) as a possible primary key.
Q47. How is a multivalued attribute mapped into a relational schema?
Solution: Create a separate relation containing the owner's key and the multivalued attribute. For example, StudentPhone(StudentID, PhoneNumber), with a suitable composite key.
Q48. How can a weak entity be mapped into relations?
Solution: Include the owner's primary key in the weak entity relation. Combine it with the weak entity's partial key to form the primary key. For example, Dependent(EmpID, DependentName, DOB).
Q49. How should a one-to-one relationship be mapped into relations?
Solution: Place a foreign key in one of the two relations, preferably where participation is total or where doing so reduces nulls. Add a uniqueness constraint to enforce one-to-one cardinality. A non-null foreign key can enforce mandatory participation on the referencing side.
Q50. What is a higher-degree relationship, and how is it mapped?
Solution: A higher-degree relationship involves three or more entity sets. It is generally mapped to a separate relation containing foreign keys for the participating entity sets and any relationship attributes. The key and uniqueness constraints depend on the relationship's semantics.
Part 2 — Relational Model, Algebra, Calculus and SQL Concepts (Q51–Q100)
Q51. What is a relation in the relational model?
Solution: A relation is a set of tuples defined over attributes. In the classical relational model, duplicate tuples are not permitted, and tuple order is irrelevant.
Q52. Differentiate between a relation, tuple, attribute, and domain.
Solution: A relation is a table-like set of tuples; a tuple is one row; an attribute is a named column; a domain is the permitted set of values for an attribute.
Q53. What is the degree and cardinality of a relation?
Solution: Degree is the number of attributes. Cardinality is the number of tuples. A relation with five columns and 200 rows has degree 5 and cardinality 200.
Q54. Why are duplicate tuples disallowed in the classical relational model?
Solution: A relation represents a set, and sets contain no duplicate elements. SQL tables can contain duplicate rows unless constraints or query semantics prevent them.
Q55. What is a NULL value? Is NULL equal to zero?
Solution: NULL indicates missing, unknown, or inapplicable information, depending on the context. It is not equal to zero or an empty string. SQL comparisons involving NULL generally evaluate to UNKNOWN.
Q56. What is a domain constraint?
Solution: A domain constraint restricts an attribute to valid values and types. For example, Age INT CHECK (Age >= 0) restricts age to nonnegative integers.
Q57. Explain the difference between selection and projection in relational algebra.
Solution: Selection filters rows according to a predicate. Projection selects attributes (columns). For example, σDeptID=10(Employee) filters employees, while πName(Employee) returns their names.
Q58. Given Employee(EmpID, Name, Salary), express the operation that finds employees earning more than ₹50,000.
Solution: σSalary>50000(Employee).
Q59. Given Student(StudentID, Name, City), express a query returning only student names and cities.
Solution: πName, City(Student).
Q60. What is the Cartesian product?
Solution: R×S combines each tuple of relation R with each tuple of relation S. If R has 4 tuples and S has 7 tuples, the product has 28 tuples.
Q61. What is the union operation?
Solution: R∪S returns tuples present in either relation. The relations must be union-compatible: they must have corresponding attributes with compatible domains.
Q62. If relation R contains 10 tuples, S contains 8 tuples, and their intersection contains 3 tuples, how many tuples are in their union?
Solution: ∣R∪S∣=∣R∣+∣S∣−∣R∩S∣=10+8−3=15.
Q63. What is set difference in relational algebra?
Solution: R−S returns tuples that occur in R but not in S. The two relations must be union-compatible.
Q64. What is the division operation used for?
Solution: Division is useful for queries involving “for all.” If Takes(StudentID, CourseID) is divided by Required(CourseID), the result contains students who have taken every required course, assuming the attributes are aligned appropriately.
Q65. Explain the theta join.
Solution: A theta join combines tuples from two relations when a specified comparison predicate is true. It can use conditions such as R.A=S.B, R.A<S.B, or a conjunction of predicates.
Q66. Differentiate between equijoin and natural join.
Solution: An equijoin uses equality comparisons and may retain both join columns. A natural join automatically matches all same-named compatible attributes and typically retains one copy of each common attribute.
Q67. What is a left outer join?
Solution: A left outer join returns all rows from the left relation and matching rows from the right relation. If there is no match, right-side attributes are filled with NULL.
Q68. Relations R and S have 5 and 6 tuples, respectively. What are the minimum and maximum possible sizes of their Cartesian product?
Solution: The size is fixed at 5×6=30 tuples, assuming ordinary finite relations. The minimum and maximum are both 30.
Q69. What is the difference between a semijoin and a natural join?
Solution: A semijoin returns only the attributes of one relation for tuples that match the other relation. A natural join combines the attributes of both relations while matching common attributes.
Q70. What is the rename operator in relational algebra?
Solution: The rename operator, commonly written ρ, renames a relation or its attributes. It is useful for self-joins and resolving naming conflicts.
Q71. What is relational calculus?
Solution: Relational calculus is a declarative query formalism based on predicate logic. It specifies what data is desired rather than the sequence of operations used to obtain it.
Q72. Differentiate between tuple relational calculus and domain relational calculus.
Solution: Tuple relational calculus uses tuple variables. Domain relational calculus uses variables representing individual attribute values.
Q73. What does it mean for a relational calculus expression to be safe?
Solution: A safe expression produces a finite result determined by the values in the database rather than an unbounded set of values from the entire underlying domain.
Q74. Are relational algebra and relational calculus equivalent in expressive power?
Solution: Classical relational algebra and safe relational calculus have equivalent expressive power for relational queries under the usual relational assumptions.
Q75. Express the idea of finding students enrolled in every course in a required-course relation.
Solution: Conceptually, return each student for whom there does not exist a required course that the student has not taken. This is a double-negation or “for all” formulation and corresponds naturally to relational division.
Q76. Write an SQL query to find employees with salaries above the average salary.
Solution:
sql
SELECT *
FROM Employee
WHERE Salary > (
SELECT AVG(Salary)
FROM Employee
);
Q77. Write an SQL query to find the second-highest distinct salary.
Solution:
sql
SELECT MAX(Salary) AS SecondHighest
FROM Employee
WHERE Salary < (
SELECT MAX(Salary)
FROM Employee
);
This returns NULL if there is no second distinct salary.
Q78. Write an SQL query to count employees in each department.
Solution:
sql
SELECT DeptID, COUNT(*) AS EmployeeCount
FROM Employee
GROUP BY DeptID;
Q79. Explain the difference between WHERE and HAVING.
Solution: WHERE filters rows before grouping. HAVING filters groups after grouping and is commonly used with aggregate functions.
Q80. Why can COUNT(*) differ from COUNT(column_name)?
Solution: COUNT(*) counts rows. COUNT(column_name) counts only rows where that column is non-NULL.
Q81. What is the difference between UNION and UNION ALL?
Solution: UNION eliminates duplicate result rows; UNION ALL retains them. Consequently, UNION ALL can be more efficient when duplicate removal is unnecessary.
Q82. Explain a correlated subquery.
Solution: A correlated subquery references a column from an outer query. It is logically evaluated in the context of outer rows, though the optimizer may transform its execution plan.
Q83. What is a view?
Solution: A view is a named query presented as a virtual table. A normal view stores its definition rather than independently storing the query result, although materialized views can store results.
Q84. What is a materialized view?
Solution: A materialized view stores the result of a query. It can accelerate repeated reads but requires a refresh strategy to keep its contents sufficiently current.
Q85. Explain primary key versus unique constraint.
Solution: A primary key uniquely identifies rows and cannot contain NULL. A unique constraint prevents duplicate key values; its treatment of NULL varies by DBMS. A table can have only one primary key constraint but multiple unique constraints.
Q86. What is a CHECK constraint?
Solution: A CHECK constraint enforces a specified condition on inserted or updated data. For example:
sql
CHECK (Salary >= 0)
The precise handling of UNKNOWN conditions and NULLs follows SQL constraint semantics.
Q87. What is a trigger?
Solution: A trigger is a database-defined action that executes in response to events such as inserts, updates, or deletes. It can enforce complex rules or maintain derived information, but excessive trigger logic can make systems harder to reason about.
Q88. Differentiate between a stored procedure and a function.
Solution: Both encapsulate database logic. A function typically returns a value or table and is subject to rules governing where it can be called. A stored procedure is invoked as a procedure and may support output parameters and transaction-related operations, depending on the DBMS.
Q89. What is a database assertion?
Solution: An assertion is a declarative constraint that may involve multiple tables. Standard SQL defines assertions, but support is limited in many popular database systems; triggers or other mechanisms may be needed instead.
Q90. What is the difference between a candidate key and a minimal superkey?
Solution: They mean the same thing: a candidate key is a superkey from which no attribute can be removed without losing the uniqueness property.
Q91. What are the three common types of integrity constraints?
Solution: Domain constraints, key/entity integrity constraints, and referential integrity constraints. Business rules may add further restrictions.
Q92. Why is a foreign key not necessarily unique?
Solution: Multiple child rows may reference the same parent row. For example, many employees can belong to one department. A uniqueness constraint is required if the relationship must be one-to-one.
Q93. What is query optimization?
Solution: Query optimization selects an efficient execution plan among equivalent or semantically valid alternatives, considering such factors as indexes, join order, cardinality estimates, and I/O costs.
Q94. Why can pushing a selection before a join improve performance?
Solution: Filtering rows early may reduce the number of tuples processed by later operations. This is valid when the transformation preserves the query's semantics.
Q95. Under what condition can a Cartesian product followed by a selection be replaced by a join?
Solution: When the selection predicate specifies the join condition between the relations, the combination can be represented as a theta join. This equivalence is useful for query rewriting.
Q96. What is a lossless relational decomposition?
Solution: A decomposition is lossless if joining its projections reconstructs exactly the original relation, without introducing spurious tuples or losing information.
Q97. What is dependency preservation?
Solution: A decomposition is dependency-preserving if the original functional dependencies can be enforced on the decomposed relations without needing to join them to check those dependencies.
Q98. Can a decomposition be lossless but not dependency-preserving?
Solution: Yes. Losslessness concerns reconstruction of the original relation; dependency preservation concerns checking constraints locally on the decomposed relations. They are distinct properties.
Q99. Why are indexes not always beneficial?
Solution: Indexes consume storage and add maintenance costs to inserts, updates, and deletes. A full table scan may be faster for small tables or queries retrieving a large proportion of rows.
Q100. A query returns too many rows after joining Employee and Department. What is a likely cause?
Solution: The join condition may be missing, incomplete, or based on a nonunique attribute. Verify that the join uses the intended foreign-key/primary-key relationship and that the expected cardinality is valid.
Part 3 — Functional Dependencies and Normalization (Q101–Q150)
Q101. What is a functional dependency?
Solution: In a relation, X→Y means that any two tuples agreeing on attributes X must also agree on attributes Y.
Q102. Given R(A,B,C) and dependencies A→B, B→C, find A+.
Solution: Start with A+={A}. Using A→B, add B; using B→C, add C. Therefore, A+={A,B,C}.
Q103. Find the candidate key of R(A,B,C,D) given A→B, B→C, and C→D.
Solution: A+={A,B,C,D}, so A is a candidate key. Since A is not derivable from other attributes and is the only determinant needed to obtain all attributes, it is minimal.
Q104. Given AB→C and C→D, find (AB)+.
Solution: (AB)+={A,B,C,D}. Thus AB is a superkey if these are all the relation's attributes, and it is a candidate key if neither A nor B can be removed while preserving the closure.
Q105. What is a trivial functional dependency?
Solution: A dependency X→Y is trivial if Y⊆X. For example, AB→A.
Q106. What is a nontrivial functional dependency?
Solution: It is a dependency in which Y is not a subset of X. For example, A→B when A and B are distinct attributes.
Q107. State Armstrong's axioms.
Solution:
These rules are sound and complete for reasoning about functional dependencies.
Q108. If A→B and A→C, derive a combined dependency.
Solution: By the union rule, which follows from Armstrong's axioms, A→BC.
Q109. If A→B, can we infer AC→B?
Solution: Yes. By augmentation, AC→BC; by decomposition, AC→B.
Q110. If AB→C and C→D, can we derive AB→D?
Solution: Yes. By transitivity, AB→D.
Q111. What is a canonical cover?
Solution: A canonical cover is a simplified set of functional dependencies equivalent to the original set, typically with singleton right-hand sides, no extraneous attributes, and no redundant dependencies.
Q112. What is an extraneous attribute in a functional dependency?
Solution: An attribute is extraneous if removing it from the left- or right-hand side, as applicable, preserves equivalence with the original dependency set.
Q113. Given F={A→BC, B→C, A→B}, find a minimal equivalent cover.
Solution: Split A→BC into A→B and A→C. Since A→B and B→C imply A→C, that dependency is redundant. The cover is {A→B, B→C}.
Q114. How can we test whether X is a superkey?
Solution: Compute X+ using the functional dependencies. If X+ contains every attribute of the relation, X is a superkey.
Q115. How can we test whether a superkey is a candidate key?
Solution: Check that it is minimal: removing any individual attribute must make it cease to be a superkey.
Q116. What is normalization?
Solution: Normalization organizes relations to reduce undesirable redundancy and insertion, update, and deletion anomalies while preserving necessary information and constraints.
Q117. What is First Normal Form (1NF)?
Solution: A relation is in 1NF when its attributes hold single values from their respective domains, rather than repeating groups or nested collections under the classical relational model.
Q118. A table contains columns Phone1, Phone2, and Phone3. What is a better normalized design?
Solution: Use Student(StudentID, Name) and StudentPhone(StudentID, PhoneNumber). Each phone number becomes a separate row, allowing an arbitrary number of phones.
Q119. What is Second Normal Form (2NF)?
Solution: A relation is in 2NF if it is in 1NF and every non-prime attribute is fully functionally dependent on every candidate key. Partial dependencies on a proper subset of a candidate key are disallowed.
Q120. Why is a relation with a single-attribute candidate key automatically in 2NF if it is in 1NF?
Solution: A single-attribute key has no nonempty proper subset that could determine a non-prime attribute, so partial dependency on part of the key cannot occur.
Q121. Consider R(StudentID,CourseID,StudentName,Grade), with key (StudentID,CourseID) and StudentID→StudentName. Is it in 2NF?
Solution: No. StudentName depends on only part of the composite key. Decompose into Student(StudentID, StudentName) and Enrollment(StudentID, CourseID, Grade).
Q122. What is Third Normal Form (3NF)?
Solution: For every nontrivial dependency X→A, either X is a superkey or A is a prime attribute. A prime attribute belongs to at least one candidate key.
Q123. What is Boyce–Codd Normal Form (BCNF)?
Solution: A relation is in BCNF if, for every nontrivial functional dependency X→Y, X is a superkey.
Q124. What is the main difference between 3NF and BCNF?
Solution: 3NF permits a non-superkey determinant in certain cases where the dependent attribute is prime. BCNF does not permit such an exception.
Q125. Give a relation that is in 3NF but not BCNF.
Solution: Let R(Student,Course,Instructor) have dependencies Student,Course→Instructor and Instructor→Course, with candidate keys (Student, Course) and (Student, Instructor). The dependency Instructor → Course violates BCNF because Instructor is not a superkey, but Course is prime, so the relation satisfies 3NF.
Q126. What is Fourth Normal Form (4NF)?
Solution: A relation is in 4NF if every nontrivial multivalued dependency X↠Y has X as a superkey.
Q127. What is Fifth Normal Form (5NF)?
Solution: A relation is in 5NF if every nontrivial join dependency is implied by its candidate keys. It prevents redundancy caused by certain join dependencies that are not adequately addressed by 4NF.
Q128. What is a multivalued dependency?
Solution: X↠Y states that, for each X value, the set of Y values is independent of the remaining attributes Z=R−(X∪Y), under the formal MVD definition.
Q129. Give a practical example of a multivalued dependency.
Solution: A relation Person(PersonID, Skill, Language) may independently record a person's skills and spoken languages. If skills and languages vary independently, PersonID ↠ Skill and PersonID ↠ Language may hold, producing redundant combinations.
Q130. How can a 4NF violation be decomposed?
Solution: For a nontrivial MVD X↠Y, decompose R into R1=X∪Y and R2=X∪(R−Y). Under the stated MVD, this decomposition is lossless.
Q131. What is relational decomposition?
Solution: It divides a relation into smaller relations to improve design, reduce redundancy, or satisfy normal forms.
Q132. What are the two major properties of a good decomposition?
Solution: Lossless join and dependency preservation. A decomposition ideally provides both, though a BCNF decomposition may sacrifice dependency preservation.
Q133. For a binary decomposition of R into R1 and R2, what is the lossless-join test using functional dependencies?
Solution: The decomposition is lossless if the common attributes R1∩R2 functionally determine all attributes of R1 or all attributes of R2 under the projected dependency closure.
Q134. Consider R(A,B,C), with A→B. Is decomposition into R1(A,B) and R2(A,C) lossless?
Solution: Yes. The intersection is A, and A→AB determines all of R1, satisfying the lossless-join test.
Q135. Consider R(A,B,C), with no nontrivial dependencies. Is decomposition into R1(A,B) and R2(B,C) necessarily lossless?
Solution: No. The common attribute B does not determine either relation under the assumed dependencies. The natural join can produce spurious combinations.
Q136. What is a spurious tuple?
Solution: A spurious tuple is an incorrect tuple introduced when decomposed relations are joined, even though that tuple did not belong to the original relation.
Q137. What is join dependency?
Solution: A join dependency specifies that a relation can be reconstructed exactly by joining its projections onto specified attribute subsets. It generalizes the lossless decomposition concept to multiple projections.
Q138. What is inclusion dependency?
Solution: An inclusion dependency R[X]⊆S[Y] requires each value tuple appearing in R's attributes X to appear in S's attributes Y. A foreign-key constraint is a common example.
Q139. What is the difference between a functional dependency and an inclusion dependency?
Solution: A functional dependency constrains how attributes within a relation determine each other. An inclusion dependency constrains values in one relation to be included among values in another relation or attribute set.
Q140. Why might BCNF decomposition fail to preserve all dependencies?
Solution: The decomposition may split attributes in a way that prevents some original dependencies from being checked within any one resulting relation. Enforcing them may require a join.
Q141. Find candidate keys for R(A,B,C,D) with F={A→B, C→D, B→C}.
Solution: A+={A,B,C,D}, so A is a candidate key. Since A never appears on a right-hand side, any key must include A. Thus the only candidate key is A.
Q142. Find the candidate key of R(A,B,C) given AB→C, C→B, and no other nontrivial dependencies.
Solution: AB+=ABC, and AC+=ABC because C→B. Neither A, B, or C alone determines all attributes. The candidate keys are AB and AC.
Q143. Is R(A,B,C) with A→B and B→C in 3NF?
Solution: A is the candidate key. B and C are non-prime attributes, and B→C has a determinant that is not a superkey. Therefore, the relation is not in 3NF.
Q144. Decompose the relation in Q143 into 3NF.
Solution: One valid decomposition is R1(A,B) and R2(B,C). Both relations are in BCNF for the specified dependencies, the decomposition is lossless, and the original dependencies are preserved.
Q145. Given R(A,B,C,D) with AB→C and C→D, is AB a candidate key?
Solution: Yes. AB+={A,B,C,D}. Neither A nor B alone can derive all attributes under the stated dependencies, so AB is minimal.
Q146. For the relation in Q145, identify a 3NF decomposition.
Solution: The dependencies imply a canonical cover with AB→C and C→D. A synthesis decomposition is R1(A,B,C) and R2(C,D). It preserves the dependencies and is lossless because R1 contains the candidate key AB.
Q147. What is the difference between 2NF and 3NF violations?
Solution: A 2NF violation involves a non-prime attribute depending on only part of a candidate key. A 3NF violation involves a dependency whose determinant is not a superkey and whose dependent attribute is non-prime.
Q148. Can a relation be in BCNF but fail to preserve dependencies after decomposition?
Solution: Yes. BCNF is a property of the resulting relations, whereas dependency preservation concerns whether all original dependencies can be enforced without joins.
Q149. What is the role of prime attributes in 3NF?
Solution: A prime attribute belongs to at least one candidate key. It provides the exception that allows some dependencies with non-superkey determinants in 3NF.
Q150. Why is normalization not always the final step in physical database design?
Solution: Highly normalized designs can require additional joins. For performance or reporting, designers may selectively denormalize or materialize aggregates after measuring workload requirements, while maintaining consistency.
Part 4 — Transactions, Schedules and Serializability (Q151–Q200)
Q151. What is a transaction?
Solution: A transaction is a logical unit of database work consisting of one or more operations. For example, transferring money requires debiting one account and crediting another.
Q152. What are the major transaction states?
Solution: Active, partially committed, committed, failed, aborted, and terminated. A transaction may become failed after an error and then be aborted; a successfully committed transaction reaches its committed state before termination.
Q153. What is the difference between COMMIT and ROLLBACK?
Solution: COMMIT makes a transaction's changes permanent according to the DBMS's durability guarantees. ROLLBACK undoes uncommitted changes within the applicable transaction scope.
Q154. What is a transaction schedule?
Solution: A schedule is an ordering of operations from one or more transactions that preserves each transaction's internal operation order.
Q155. Differentiate between serial and nonserial schedules.
Solution: A serial schedule completes one transaction before beginning the next. A nonserial schedule interleaves operations from multiple transactions.
Q156. What is serializability?
Solution: Serializability is the property that a concurrent schedule is equivalent, under a specified equivalence criterion, to some serial schedule.
Q157. What is a conflict between two operations?
Solution: Two operations conflict if they belong to different transactions, access the same data item, and at least one operation is a write. Thus, read-write, write-read, and write-write pairs conflict; read-read pairs do not.
Q158. What is conflict serializability?
Solution: A schedule is conflict-serializable if it can be transformed into a serial schedule by swapping adjacent nonconflicting operations.
Q159. How is conflict serializability tested?
Solution: Build a precedence graph. Each transaction is a vertex, and an edge Ti→Tj exists if an operation of Ti conflicts with and precedes an operation of Tj. The schedule is conflict-serializable exactly when the graph is acyclic.
Q160. A precedence graph has edges T1→T2, T2→T3, and T1→T3. Is the schedule conflict-serializable?
Solution: Yes. The graph is acyclic, and the serial order is T1,T2,T3.
Q161. A precedence graph has edges T1→T2 and T2→T1. What does this indicate?
Solution: The graph contains a cycle, so the schedule is not conflict-serializable.
Q162. Given the schedule W1(X),R2(X),W2(Y),R1(Y), test conflict serializability.
Solution: The conflict on X creates T1→T2. The conflict on Y creates T2→T1. The cycle means the schedule is not conflict-serializable.
Q163. Given R1(X),W1(X),R2(X),W2(X), find the serial order.
Solution: The conflicting operations create only T1→T2, so the schedule is conflict-serializable in the order T1,T2.
Q164. What is view serializability?
Solution: A schedule is view-serializable if it is view-equivalent to a serial schedule. View equivalence preserves initial reads, the transaction responsible for each read value, and the final write on each item.
Q165. How does view serializability differ from conflict serializability?
Solution: Every conflict-serializable schedule is view-serializable, but the converse is not always true. View serializability can accept certain schedules involving blind writes that conflict serializability rejects.
Q166. What is a blind write?
Solution: A blind write updates a data item without first reading its current value within that transaction.
Q167. Give a schedule that is view-serializable but not conflict-serializable.
Solution: Consider W1(X),W2(X),W1(X). All operations are blind writes. The final write is by T1, so the schedule is view-equivalent to the serial order T2,T1. Its conflicting writes produce edges in both directions, so it is not conflict-serializable.
Q168. What is a recoverable schedule?
Solution: A schedule is recoverable if a transaction that reads data written by another transaction commits only after the writer commits.
Q169. What is a cascading rollback?
Solution: A cascading rollback occurs when aborting one transaction forces other transactions to abort because they read its uncommitted data.
Q170. What is a cascadeless schedule?
Solution: A schedule is cascadeless if transactions read only committed values written by other transactions. This prevents cascading rollbacks due to dirty reads.
Q171. What is a strict schedule?
Solution: A strict schedule prevents any transaction from reading or writing an item written by another transaction until the writer commits or aborts. Strict schedules simplify recovery.
Q172. Explain the relationship among strict, cascadeless, and recoverable schedules.
Solution: Strict schedules are cascadeless, and cascadeless schedules are recoverable. The reverse implications do not generally hold.
Q173. Consider W1(X),R2(X),C1,C2. Is this schedule recoverable?
Solution: Yes. T2 reads the value written by T1, and T1 commits before T2 commits. However, it is not cascadeless because T2 reads X before T1 commits.
Q174. Consider W1(X),R2(X),C2,A1. Is this schedule recoverable?
Solution: No. T2 commits after reading an uncommitted value from T1, even though T1 subsequently aborts.
Q175. Can a recoverable schedule still require cascading rollback?
Solution: Yes. Recoverability constrains commit order, not whether transactions may read uncommitted values. A dependent transaction can be forced to abort before it commits.
Q176. What is a dirty read?
Solution: A dirty read occurs when a transaction reads a value written by another transaction that has not yet committed.
Q177. What is a lost update?
Solution: A lost update occurs when concurrent transactions overwrite each other's changes so that one update is effectively discarded.
Q178. Explain an inconsistent retrieval problem.
Solution: A transaction reads related data while another transaction is updating it, observing a mixture of old and new values. The result may violate an application's consistency expectations.
Q179. What is a nonrepeatable read?
Solution: A transaction reads a row twice and obtains different values because another transaction committed an update between the reads.
Q180. What is a phantom read?
Solution: A transaction repeats a predicate-based query and finds additional or missing rows because another transaction inserted, deleted, or modified rows so that they enter or leave the predicate's result.
Q181. What is concurrency control?
Solution: Concurrency control coordinates simultaneous transactions to maintain isolation and protect database consistency while allowing useful parallelism.
Q182. What is a serial schedule's main disadvantage?
Solution: It can reduce throughput and resource utilization because transactions cannot overlap, even when their operations access independent data.
Q183. What is a schedule's precedence graph used for?
Solution: It identifies conflicts and tests conflict serializability. A directed cycle proves that no conflict-equivalent serial order exists.
Q184. How many topological orders does a precedence graph with two independent vertices have?
Solution: Two: T1,T2 and T2,T1. Both are valid serial orders when no edges constrain their ordering.
Q185. A graph contains T1→T2 and T1→T3, with no other edges. Give all valid serial orders.
Solution: T1,T2,T3 and T1,T3,T2. Transaction T1 must precede both others, but T2 and T3 can be ordered either way.
Q186. Why is a precedence graph with a cycle not conflict-serializable?
Solution: Every edge imposes an ordering constraint on a serial equivalent. A cycle would require a transaction to precede itself indirectly, making the ordering constraints impossible to satisfy.
Q187. Does conflict serializability guarantee that a schedule is recoverable?
Solution: No. Serializability and recoverability are separate properties. A conflict-serializable schedule can allow a transaction to read an uncommitted value and commit before the writer.
Q188. What is the purpose of transaction isolation levels?
Solution: Isolation levels define which anomalies concurrent transactions may observe and the guarantees provided by the DBMS. Stronger isolation generally restricts more concurrency or requires more sophisticated control.
Q189. What is snapshot isolation?
Solution: Snapshot isolation lets a transaction read a consistent snapshot of committed data, often using multiversion concurrency control. It can prevent many read anomalies but does not, by itself, guarantee full serializability in every implementation.
Q190. Why can snapshot isolation permit write skew?
Solution: Two transactions may read the same valid snapshot, update different rows, and each commit because their writes do not conflict. Together, their changes may violate a cross-row business rule.
Q191. Given R1(X),W1(X),R2(X),W2(X),R1(Y),W1(Y), construct the precedence graph.
Solution: The conflicts on X produce T1→T2. There is no conflict involving Y and T2. The graph is acyclic, so the schedule is conflict-serializable in order T1,T2.
Q192. Given R1(X),W2(X),R2(Y),W1(Y), is the schedule conflict-serializable?
Solution: The X conflict gives T1→T2; the Y conflict gives T2→T1. The cycle makes the schedule non-conflict-serializable.
Q193. Consider W1(X),W2(X),W3(X). Is the schedule conflict-serializable?
Solution: Yes. The graph has edges T1→T2, T1→T3, and T2→T3. The serial order is T1,T2,T3.
Q194. Consider R1(X),W2(X),W1(X). Is the schedule conflict-serializable?
Solution: No. R1(X) before W2(X) gives T1→T2; W2(X) before W1(X) gives T2→T1. The graph has a cycle.
Q195. Can two read operations on the same item create an edge in the precedence graph?
Solution: No. Read-read operations do not conflict, so they do not create a precedence edge by themselves.
Q196. A transaction reads X from T1, but T1 aborts. What must happen to a dependent transaction in a recoverable schedule?
Solution: The dependent transaction must not have committed before T1. It may need to abort as well, especially if it used the dirty value.
Q197. What is a commit dependency?
Solution: If T2 reads a value produced by T1, recoverability requires T2's commit to follow T1's commit. Thus, T2's commit depends on T1's successful commit.
Q198. What is a serial execution order, and how is it obtained from an acyclic graph?
Solution: It is a total order of transactions consistent with all precedence edges. Obtain one by topologically sorting the graph.
Q199. If a schedule is strict, can it contain a dirty read?
Solution: No. Strictness prohibits reading a value written by an uncommitted transaction, so dirty reads are excluded.
Q200. Why is conflict serializability easier to test than general view serializability?
Solution: Conflict serializability reduces to cycle detection in a precedence graph, which can be done efficiently. General view-serializability testing is computationally more difficult.
Part 5 — Concurrency Control, Locking, Deadlocks and Recovery (Q201–Q250)
Q201. What is a lock in DBMS?
Solution: A lock controls access to a data item to prevent incompatible concurrent operations.
Q202. Differentiate between shared and exclusive locks.
Solution: A shared (S) lock permits reading and is compatible with other shared locks. An exclusive (X) lock permits writing and is incompatible with other shared or exclusive locks on the same item.
Q203. Can two transactions hold shared locks on the same item simultaneously?
Solution: Yes, provided neither holds an incompatible lock. Both transactions can read the item concurrently.
Q204. Can a transaction acquire an exclusive lock while another transaction holds a shared lock on the item?
Solution: Not immediately. It must wait until the conflicting shared lock is released, unless the lock manager resolves the situation by aborting or otherwise handling a transaction.
Q205. What is two-phase locking (2PL)?
Solution: Under 2PL, a transaction has a growing phase in which it acquires locks and a shrinking phase in which it releases locks. It cannot acquire new locks after releasing its first lock.
Q206. Does basic 2PL guarantee conflict serializability?
Solution: Yes. Every schedule generated by basic 2PL is conflict-serializable, although deadlocks may occur.
Q207. What is strict 2PL?
Solution: Strict 2PL retains exclusive locks until commit or abort. Some systems use the term for protocols that retain all locks until transaction completion, so the exact convention should be stated.
Q208. Differentiate between basic, strict, and rigorous 2PL.
Solution: Basic 2PL imposes growing and shrinking phases. Strict 2PL holds exclusive locks until completion. Rigorous 2PL holds both shared and exclusive locks until completion.
Q209. What is lock conversion?
Solution: Lock conversion changes a lock's mode. Upgrading changes S to X, while downgrading changes X to S. An upgrade must satisfy the lock compatibility rules.
Q210. What is a lock compatibility matrix used for?
Solution: It determines whether a requested lock can be granted while another transaction holds a lock on the same item.
|
Requested/held |
S |
X |
|
S |
Yes |
No |
|
X |
No |
No |
Q211. Can 2PL cause deadlocks?
Solution: Yes. Two transactions may each hold a lock needed by the other while waiting for additional locks.
Q212. What is a deadlock?
Solution: A deadlock is a situation in which a set of transactions waits indefinitely for resources held by one another, preventing progress.
Q213. What is a wait-for graph?
Solution: It is a directed graph in which each vertex represents a transaction and an edge Ti→Tj indicates that Ti is waiting for a resource held by Tj. A cycle indicates deadlock in the usual single-instance locking model.
Q214. Transactions T1 and T2 each hold one lock and wait for the other's lock. What is the result?
Solution: There is a cycle T1→T2→T1, so the transactions are deadlocked.
Q215. Name four methods for handling deadlocks.
Solution: Deadlock prevention, deadlock avoidance, deadlock detection and recovery, and timeout-based handling.
Q216. What is the wait-die scheme?
Solution: It is a timestamp-based prevention scheme. An older transaction may wait for a younger one; a younger transaction requesting a resource held by an older one is aborted.
Q217. What is the wound-wait scheme?
Solution: An older transaction requesting a resource held by a younger one aborts the younger transaction. A younger transaction requesting a resource held by an older one waits.
Q218. How can a DBMS select a deadlock victim?
Solution: It may consider transaction age, work completed, locks held, rollback cost, and the effect on other transactions. The selected victim is aborted to break the cycle.
Q219. What is starvation in lock management?
Solution: Starvation occurs when a transaction repeatedly waits or is repeatedly aborted and therefore makes no progress. Fair queues, aging, and careful victim selection can reduce it.
Q220. What is multiple-granularity locking?
Solution: It allows locks at different hierarchy levels, such as database, table, page, and row, balancing concurrency against locking overhead.
Q221. What is a timestamp-ordering protocol?
Solution: It assigns each transaction a timestamp and enforces a serial order consistent with those timestamps through read and write validation rules.
Q222. What are read_TS(X) and write_TS(X)?
Solution: read_TS(X) records the largest timestamp of a transaction that successfully read X. write_TS(X) records the largest timestamp of a transaction whose write to X was accepted.
Q223. Under basic timestamp ordering, when is a read Ri(X) rejected?
Solution: If TS(Ti)<write_TS(X), the read is rejected because a newer transaction has already written X. The transaction is normally rolled back and restarted.
Q224. Under basic timestamp ordering, when is a write Wi(X) rejected?
Solution: If TS(Ti)<read_TS(X), the write would violate the timestamp order and is rejected. Under basic timestamp ordering, it is also rejected if TS(Ti)<write_TS(X).
Q225. What is Thomas's Write Rule?
Solution: If a transaction attempts a write whose timestamp is older than write_TS(X), the obsolete write may be ignored rather than aborting the transaction. This can permit schedules that basic timestamp ordering would reject.
Q226. What is optimistic or validation-based concurrency control?
Solution: It allows transactions to execute without acquiring conventional read/write locks during their read phase, then validates their read/write sets before accepting their writes.
Q227. What are the three phases of optimistic concurrency control?
Solution: Read phase, validation phase, and write phase.
Q228. When is optimistic concurrency control most suitable?
Solution: It is often suitable when conflicts are rare and the overhead of locking would outweigh the cost of occasional transaction restarts.
Q229. Compare lock-based and timestamp-based protocols.
Solution: Lock-based protocols delay conflicting operations and can deadlock. Basic timestamp ordering typically aborts operations that violate timestamp order and avoids lock-based deadlocks, but may incur restarts.
Q230. Can timestamp ordering prevent deadlocks caused by waiting for locks?
Solution: Basic timestamp ordering does not wait for conflicting locks; it aborts violating operations instead. Therefore, it avoids deadlocks of the ordinary lock-wait type, though other system-level waits may still occur.
Q231. What is database recovery?
Solution: Recovery restores the database to a correct state after transaction errors, system crashes, or storage failures.
Q232. What are the major classes of database failures?
Solution: Transaction failures, system crashes, and media failures. Communication or distributed-system failures can also affect distributed transactions.
Q233. What is a transaction failure?
Solution: A transaction failure occurs when an individual transaction cannot complete because of an error, constraint violation, explicit abort, or deadlock victim selection.
Q234. What is a system crash?
Solution: A system crash interrupts database processing, possibly losing volatile memory contents while persistent storage remains available.
Q235. What is a media failure?
Solution: A media failure damages or makes persistent storage unavailable, requiring restoration from backups and application of retained logs or other recovery data.
Q236. What is log-based recovery?
Solution: The DBMS records transaction actions and recovery information in a log so that it can undo incomplete changes and redo necessary committed changes after failure.
Q237. What is Write-Ahead Logging (WAL)?
Solution: WAL requires relevant log records to reach stable storage before the corresponding modified data page is written. Commit records must also be made durable before a commit is acknowledged under the applicable durability guarantee.
Q238. What is the difference between UNDO and REDO?
Solution: UNDO reverses changes from transactions whose effects must not remain. REDO reapplies changes that must persist but may not have reached the database pages before failure.
Q239. Why can a recovery algorithm need both UNDO and REDO?
Solution: A database may have flushed some uncommitted updates to disk and may not have flushed some committed updates. UNDO removes the former; REDO restores the latter.
Q240. What is a checkpoint?
Solution: A checkpoint records recovery-relevant information and can reduce how far back the recovery process must examine the log. It does not necessarily flush every page or eliminate the need for recovery.
Q241. Does a checkpoint mean all transactions have committed?
Solution: No. Transactions may remain active at a checkpoint. Recovery still needs information about transactions and dirty pages that span the checkpoint.
Q242. What is a deferred database modification scheme?
Solution: Database updates are deferred until a transaction commits, so uncommitted changes need not be undone in the database. Depending on the scheme, REDO may still be necessary.
Q243. What is an immediate database modification scheme?
Solution: Updates may reach database pages before transaction commit. Recovery therefore needs enough log information to undo uncommitted updates and redo committed updates when required.
Q244. What is shadow paging?
Solution: Shadow paging preserves an unchanged page-table version while modifications are made to new pages. Commit switches the database to the new page table, allowing recovery without conventional undo/redo logging for those page changes, though practical implementations have other costs.
Q245. What is a fuzzy checkpoint?
Solution: A fuzzy checkpoint allows normal transaction processing to continue while checkpoint information is recorded, rather than requiring all activity to stop. Recovery uses checkpoint metadata and the log to identify relevant work.
Q246. What is ARIES?
Solution: ARIES is a widely studied recovery algorithm based on Write-Ahead Logging. Its main recovery phases are analysis, redo, and undo.
Q247. What is a compensation log record (CLR)?
Solution: A CLR records an action performed while undoing a previous update. It supports correct recovery if another crash occurs during recovery itself.
Q248. Why must recovery be repeatable after a second crash?
Solution: Recovery actions may be interrupted by another failure. Logging recovery actions and maintaining suitable log ordering allows the DBMS to resume recovery without corrupting the database or repeating undo incorrectly.
Q249. What is a backup, and how does it differ from a transaction log?
Solution: A backup is a saved database copy or recovery baseline. A transaction log records changes and transaction events. Combining a backup with suitable logs can restore a database to a later recovery point.
Q250. A crash occurs after a transaction's commit record is durable but before its updated page reaches disk. What should recovery do?
Solution: Recovery should REDO the committed transaction's update if necessary. The durable commit record establishes that the transaction committed, even if its data page had not yet been flushed.
Part 6 — File Organization, Indexing and B+ Trees (Q251–Q300)
Q251. What is file organization in DBMS?
Solution: File organization determines how records are physically arranged in storage. It affects search performance, insertion, deletion, range queries, and sequential access.
Q252. What is heap file organization?
Solution: Records are stored without maintaining a particular search-key order. Inserts are often inexpensive, but finding a particular record may require a scan unless an index exists.
Q253. What is sequential file organization?
Solution: Records are stored in a specified key order. It supports ordered scans and range access but can make insertions and deletions more expensive if physical order must be maintained.
Q254. What is hashed file organization?
Solution: A hash function maps a search key to a bucket. It is effective for equality searches when the hash function and collision handling are well designed.
Q255. Which file organization is generally suitable for range queries: heap, hashing, or ordered sequential storage?
Solution: Ordered sequential storage is generally more suitable because records are organized by key. Hashing does not preserve key order, and heap storage normally requires a scan unless an appropriate index exists.
Q256. What is clustered file organization?
Solution: Related records are physically stored close together according to a clustering key or related organization. This can improve access to groups of associated records, though updates and overflow handling can be more complicated.
Q257. What is ISAM?
Solution: Indexed Sequential Access Method is an ordered file organization with a static index structure and overflow areas for records that do not fit in their primary storage locations. Excessive overflow can degrade performance.
Q258. Differentiate between ISAM and a B+ tree.
Solution: ISAM generally has a static index structure with overflow chains, whereas a B+ tree dynamically splits and merges nodes as the data changes. B+ trees tend to adapt better to changing workloads.
Q259. What is an index in DBMS?
Solution: An index is an auxiliary structure that helps locate records efficiently. It reduces search work for suitable queries at the cost of storage and update overhead.
Q260. Differentiate between primary and secondary indexes.
Solution: In common textbook terminology, a primary index is built on the ordering key of a physically ordered file, while a secondary index is built on a nonordering attribute. Terminology varies across systems and textbooks.
Q261. What is a dense index?
Solution: A dense index has an index entry for every search-key value or every record, depending on the implementation. It typically offers direct access at the cost of more index entries.
Q262. What is a sparse index?
Solution: A sparse index stores entries for only some search-key values, commonly one per data block in an ordered file. It needs the data file to be suitably ordered and may require a scan within the selected block.
Q263. Why can a sparse index be smaller than a dense index?
Solution: It stores fewer index entries, often one per block rather than one per record. This reduces index size and can reduce index maintenance work.
Q264. What is a multilevel index?
Solution: A multilevel index indexes an existing index, creating a hierarchy. Searching descends through levels until the relevant data block or record is located.
Q265. What is a clustered index?
Solution: A clustered index determines or closely corresponds to the physical ordering of records. Because physical order is limited, a system generally cannot maintain multiple independent physical orderings of the same table simultaneously.
Q266. What is a nonclustered index?
Solution: A nonclustered index stores search keys and references to records separately from the table's primary physical organization. Multiple nonclustered indexes may exist on one table.
Q267. What is a composite index?
Solution: A composite index uses more than one attribute, such as (DepartmentID, Salary). Its usefulness depends on the index order and query predicates.
Q268. Why does column order matter in a composite B-tree index?
Solution: A B-tree index on (A, B) is naturally suited to searches on A and on A together with B. It may not efficiently support searches on B alone because entries are ordered first by A.
Q269. What is a covering index?
Solution: A covering index contains all columns required by a particular query, enabling the DBMS to answer that query without retrieving the full table rows in suitable circumstances.
Q270. Why might a full table scan outperform an index scan?
Solution: If a query retrieves a large fraction of the table, random index lookups and row fetches may cost more than scanning data pages sequentially.
Q271. What is a B-tree?
Solution: A B-tree is a balanced search tree in which keys and, depending on the variant, record references can appear in internal and leaf nodes. It is designed to reduce storage I/O by using nodes with many children.
Q272. What is a B+ tree?
Solution: A B+ tree stores search keys and record pointers in internal nodes for navigation, while data entries or record references reside at the leaves. Leaf nodes are commonly linked for efficient ordered traversal.
Q273. Differentiate between B-tree and B+ tree.
Solution: In a typical B-tree, data entries may appear in internal nodes and leaves. In a B+ tree, all data entries are at the leaves, and internal nodes guide searches. B+ trees support efficient range scans through linked leaves.
Q274. Why are B+ trees widely used for database indexes?
Solution: They have high fan-out, low height, balanced search paths, and efficient sequential leaf traversal. These properties reduce page I/O for point and range queries.
Q275. What is the fan-out of a B+ tree?
Solution: Fan-out is the number of child pointers an internal node can contain. Larger fan-out generally means fewer levels for a given number of indexed keys.
Q276. A B+ tree has fan-out 100 and three internal-to-leaf levels of descent. Roughly how many leaf regions can the root hierarchy address if the root has 100 children and each of the next two internal levels has 100 children?
Solution: Up to 1003=1,000,000 leaf regions under the idealized full-tree assumption. Actual capacity depends on occupancy, root structure, and the precise meaning of the stated levels.
Q277. What is the root split operation in a B+ tree?
Solution: When the root overflows, it is split and a new root is created above the resulting nodes. The tree height increases by one.
Q278. What happens when a leaf node overflows during insertion?
Solution: The leaf is split, its entries are divided between the resulting leaves, and a separator key is inserted into the parent. A parent overflow may trigger further splitting.
Q279. What happens when a B+ tree node becomes underfull after deletion?
Solution: The implementation may redistribute entries from a sibling or merge nodes. Parent separators and pointers are adjusted, and underflow can propagate upward.
Q280. Why are B+ tree leaf nodes often linked?
Solution: Leaf links make range queries and ordered scans efficient because the DBMS can move sequentially between neighboring leaves after finding the first qualifying key.
Q281. A B+ tree internal node can have at most 8 children. What is the maximum number of separator keys in that node?
Solution: At most 8−1=7 separator keys, assuming the usual structure in which an internal node with m children has m−1 separator keys.
Q282. If a B+ tree has an internal-node fan-out of 5, what is the maximum number of leaf nodes at depth 3 below the root in a full tree?
Solution: Under the assumption that the root is at depth 0 and each internal node has five children, depth 3 can contain 53=125 leaves.
Q283. An index has 1,000,000 records and a B+ tree fan-out of 100. Approximately how many levels are needed in an ideally full tree to cover the leaf regions?
Solution: Since 1003=1,000,000, about three branching steps from the root can address one million leaf regions under the idealized assumption. The actual height also depends on leaf capacity and occupancy.
Q284. A leaf can hold 100 data entries. Approximately how many leaves are needed for 50,000 entries if all leaves are full?
Solution: 50,000/100=500 leaves. Real trees may require more because nodes are not necessarily full.
Q285. If a B+ tree has 500 leaf nodes and each internal node can have 10 children, how many internal nodes are needed at the level directly above the leaves in the idealized full case?
Solution: ⌈500/10⌉=50 internal nodes, assuming every node can have ten children and ignoring minimum-occupancy and root special cases.
Q286. What is the approximate I/O cost of a B+ tree point lookup?
Solution: Approximately one page access per tree level, plus any necessary data-page access if the leaf does not contain the record itself. Buffer caching can reduce physical I/O.
Q287. Why can B+ tree range queries be more efficient than repeated independent lookups?
Solution: After reaching the first qualifying leaf, the DBMS can follow linked leaves sequentially rather than repeatedly descending from the root for every key.
Q288. A B+ tree leaf split leaves 60 entries in one leaf and 40 in the other. Is this necessarily invalid?
Solution: No. Validity depends on the tree's maximum capacity, minimum occupancy, and split policy. The split must respect the implementation's occupancy constraints.
Q289. What is separator-key propagation?
Solution: When a node splits, a key representing the boundary between the resulting nodes is inserted or propagated into the parent so searches can choose the correct child.
Q290. Does a B+ tree always have the same number of entries in every leaf?
Solution: No. Leaves can have different occupancy. The balance property requires all leaves to be at the same depth, not that every leaf contains the same number of entries.
Q291. What is a bitmap index?
Solution: A bitmap index uses bit vectors to represent the presence of attribute values. It can be effective for low-cardinality columns and analytical workloads.
Q292. Why may bitmap indexes perform poorly for heavily updated transactional columns?
Solution: Frequent updates can cause substantial index-maintenance overhead, particularly when many rows and bitmap segments are affected.
Q293. What is a hash index?
Solution: A hash index uses a hash function to map keys to index buckets. It is generally optimized for equality lookups rather than ordered range scans.
Q294. Can a hash index directly support Salary BETWEEN 40000 AND 60000 efficiently?
Solution: Generally not through hash order alone, because hashing destroys key ordering. A B-tree index is usually more appropriate for range predicates.
Q295. What is index selectivity?
Solution: Selectivity describes how strongly a predicate filters the data. A highly selective predicate returns a small fraction of rows and is often a good candidate for index access.
Q296. What is a unique index?
Solution: A unique index prevents duplicate indexed key combinations, subject to the DBMS's NULL-handling rules. It can enforce a unique constraint and accelerate qualifying searches.
Q297. What is a function-based index?
Solution: It indexes the result of an expression, such as LOWER(Email). It can accelerate searches that use the matching expression, depending on the DBMS.
Q298. Why can a function on an indexed column prevent ordinary index use?
Solution: A predicate such as LOWER(Name) = 'ravi' may not match a conventional index on Name. An expression index or a suitable query rewrite may be required.
Q299. What is index fragmentation?
Solution: Index fragmentation refers to less efficient physical organization, such as poorly filled pages or scattered page placement. Its impact depends on the index type, workload, storage system, and DBMS.
Q300. How would you choose between a B+ tree and a hash index for a frequently queried column?
Solution: Prefer a B+ tree if the workload includes equality and range queries, ordering, or prefix access on composite keys. Consider a hash index when equality lookups dominate and the DBMS's hash implementation is suitable.
Part 7 — Hashing, Static Hashing and Dynamic Hashing (Q301–Q350)
Q301. What is hashing in DBMS?
Solution: Hashing uses a function to map a search key to a bucket containing or locating records. It is commonly used for equality searches.
Q302. What is a hash function?
Solution: A hash function h(k) maps a key k to a bucket address or bucket number. A good function distributes expected keys reasonably evenly.
Q303. What is a collision in hashing?
Solution: A collision occurs when different keys map to the same bucket.
Q304. What is a hash bucket?
Solution: A bucket is a storage unit or logical grouping to which a hash function directs records. A bucket may contain several records and may require overflow handling.
Q305. What is static hashing?
Solution: Static hashing uses a fixed number of primary buckets. As data grows, overflow chains or additional overflow areas may be needed.
Q306. What is dynamic hashing?
Solution: Dynamic hashing adapts its bucket structure as data grows or shrinks, reducing the performance problems associated with a fixed bucket count.
Q307. Differentiate between static and dynamic hashing.
Solution: Static hashing has a fixed primary bucket structure, while dynamic hashing expands or contracts its organization as needed. Dynamic schemes can reduce long overflow chains but introduce splitting, directory, or restructuring overhead.
Q308. What is overflow handling?
Solution: Overflow handling determines where records go when their target bucket is full. Common techniques include overflow chains, open addressing in related hash structures, and bucket splitting.
Q309. What is separate chaining?
Solution: Separate chaining handles collisions by storing colliding records in a linked list or other secondary structure associated with a bucket.
Q310. What is linear probing?
Solution: Linear probing searches successive positions when a collision occurs, commonly using h(k,i)=(h(k)+i) mod m. It can suffer from primary clustering.
Q311. A hash table has 10 buckets and uses h(k)=k mod 10. Find the bucket for key 437.
Solution: 437 mod 10=7. The key maps to bucket 7.
Q312. Using h(k)=k mod 7, insert keys 10, 17, 24, and 31. Which bucket do they map to?
Solution: Each key has remainder 3 when divided by 7. All four map to bucket 3, creating a collision sequence.
Q313. A table has 100 buckets and 700 records. What is its load factor?
Solution: The load factor is 700/100=7 records per bucket on average, assuming one record per unit of bucket capacity is the baseline. If buckets can store multiple records, the occupancy ratio should instead use the actual capacity.
Q314. A hash table has 1,000 slots, of which 750 are occupied. Find the load factor.
Solution: α=750/1000=0.75, or 75%.
Q315. Why can a poor hash function cause performance degradation?
Solution: It concentrates keys in a small number of buckets, causing long collision chains or repeated probes and increasing search and insertion costs.
Q316. What is primary clustering in linear probing?
Solution: Primary clustering occurs when contiguous occupied regions grow and cause more keys to collide with those regions, increasing probe lengths.
Q317. What is quadratic probing?
Solution: Quadratic probing uses a quadratic sequence of offsets, such as h(k,i)=(h(k)+c1i+c2i2) mod m, to reduce primary clustering. Its ability to visit all slots depends on the parameters and table size.
Q318. What is double hashing?
Solution: Double hashing uses a second hash function to determine the probe step, for example h(k,i)=(h1(k)+i h2(k)) mod m. Suitable choices reduce clustering and help cover the table.
Q319. What is the difference between separate chaining and open addressing?
Solution: Separate chaining stores collided entries outside the original bucket slot structure, such as in chains. Open addressing stores all entries in the table itself and searches for an available slot using a probe sequence.
Q320. Why can deleting a key be difficult in open addressing?
Solution: Simply clearing a slot can break the probe sequence and make later keys unreachable. Implementations often use tombstones or perform a reorganization.
Q321. What is extendible hashing?
Solution: Extendible hashing is a dynamic hashing scheme that uses a directory indexed by hash-prefix bits and allows buckets to split as they overflow.
Q322. What is global depth in extendible hashing?
Solution: Global depth is the number of hash bits used to index the directory. A directory with global depth d has 2d entries.
Q323. What is local depth?
Solution: Local depth is the number of hash-prefix bits that identify a particular bucket. It is less than or equal to the global depth.
Q324. An extendible hash directory has global depth 4. How many directory entries does it contain?
Solution: 24=16 directory entries.
Q325. If global depth is 3 and a bucket has local depth 2, how many directory entries point to that bucket?
Solution: 23−2=2 directory entries, assuming the standard extendible-hashing structure.
Q326. What happens when a bucket overflows and its local depth is smaller than the global depth?
Solution: The bucket can split without doubling the entire directory. Its local depth increases, and the appropriate directory pointers are redirected.
Q327. What happens when a bucket overflows and its local depth equals global depth?
Solution: The directory must be doubled, increasing global depth by one, and the overflowing bucket is split.
Q328. An extendible hash has global depth 2 and directory size 4. A bucket with local depth 2 overflows. What is the new directory size after doubling?
Solution: The global depth becomes 3, so the directory contains 23=8 entries.
Q329. Why can several directory entries point to the same bucket?
Solution: When a bucket's local depth is smaller than the global depth, multiple bit patterns share the same prefix and therefore map to that bucket.
Q330. What is the main advantage of extendible hashing?
Solution: It expands by splitting buckets and adjusting directory entries, helping maintain efficient access as the data set grows without requiring a complete reorganization of all records.
Q331. What is linear hashing?
Solution: Linear hashing is a dynamic hashing method that expands incrementally, typically splitting buckets according to a split pointer rather than doubling an entire directory at once.
Q332. Differentiate between linear and extendible hashing.
Solution: Extendible hashing uses a directory indexed by hash-prefix bits and may double it. Linear hashing usually expands buckets incrementally with a split pointer and can operate without a large directory.
Q333. What is a split pointer in linear hashing?
Solution: It identifies the next bucket scheduled to split as the hash structure grows. It advances through the bucket sequence and eventually completes a round of splits.
Q334. Why does linear hashing avoid sudden full-directory doubling?
Solution: It spreads growth across incremental bucket splits. This can smooth expansion costs, although individual splits still require redistribution of records.
Q335. What is the purpose of using two hash functions or hash levels in linear hashing?
Solution: A new hash level helps redistribute records as the table expands. The active hash function depends on the current expansion round and whether a bucket has already been split.
Q336. A bucket can hold 4 records. If 17 records map to the same bucket, how many overflow records are required beyond the primary bucket capacity?
Solution: 17−4=13 records exceed the primary bucket's capacity. The exact number of overflow pages depends on the overflow-page capacity.
Q337. A hash function distributes 10,000 records uniformly across 1,000 buckets. What is the expected average number of records per bucket?
Solution: 10,000/1,000=10 records per bucket.
Q338. If the number of records doubles but a static hash table's bucket count remains unchanged, what generally happens to average bucket occupancy?
Solution: The average occupancy doubles. Unless the original table had substantial spare capacity, collision and overflow costs are likely to increase.
Q339. Why is hashing usually unsuitable for ordered range scans?
Solution: Hashing maps nearby key values to unrelated bucket addresses, so bucket order does not correspond to key order.
Q340. What is the expected search cost of a well-designed hash table?
Solution: It is often described as expected O(1) under suitable assumptions about the hash function, load factor, collision handling, and workload. Worst-case search can be O(n).
Q341. Can hashing guarantee constant-time lookup in the worst case?
Solution: Not with ordinary hash tables under arbitrary collisions. Worst-case lookup can degrade to linear time unless stronger assumptions or specialized schemes are used.
Q342. How does a DBMS handle a hash collision when a bucket has available space?
Solution: It stores the colliding record in the same bucket, provided the bucket format supports multiple records. A collision does not necessarily require an overflow page.
Q343. Why might dynamic hashing still perform poorly?
Solution: Poor hash distribution, skewed keys, high load, expensive directory access, and repeated bucket splits can all degrade performance.
Q344. What is hash skew?
Solution: Hash skew occurs when records are distributed unevenly across buckets, often because of nonuniform data or a poor hash function.
Q345. Why should the hash function be deterministic for a persistent database index?
Solution: A stored key must map consistently to the bucket where its record is located. If the function changes unexpectedly, lookups may search the wrong bucket unless the index is rebuilt or the mapping is versioned.
Q346. What is a static hash overflow chain?
Solution: It is a linked sequence of additional storage pages associated with a bucket when the primary bucket cannot hold all its records.
Q347. Compare hash indexing with B+ tree indexing for equality queries.
Solution: Both can support equality lookups. Hash indexing may be efficient for equality searches, while B+ trees also support ordered retrieval, range queries, and traversal of neighboring keys.
Q348. What is the role of rehashing?
Solution: Rehashing redistributes records, often after the hash-table size or hash function changes, to reduce excessive collisions and restore suitable performance.
Q349. Why can resizing a hash table be expensive?
Solution: Many or all keys may need to be redistributed, causing substantial I/O and computation. Dynamic hashing schemes seek to reduce or distribute this cost.
Q350. A system needs frequent exact-match lookups and frequent salary-range reports. Which index design is a sensible starting point?
Solution: A B+ tree on salary is a strong starting point because it supports both equality and range queries. A separate hash index may help if exact-match lookups dominate and measurements justify the extra storage and maintenance cost.
Part 8 — Advanced Transactions, Recovery and Distributed DBMS (Q351–Q400)
Q351. What is a cascading abort, and how can strict 2PL prevent it?
Solution: A cascading abort forces dependent transactions to abort after a transaction they read from aborts. Strict 2PL prevents dirty reads by retaining write locks until transaction completion.
Q352. Can a transaction release a lock and later acquire another lock under basic 2PL?
Solution: No. Once it enters the shrinking phase by releasing a lock, it cannot acquire any new locks.
Q353. What is the lock point of a transaction?
Solution: The lock point is the instant when the transaction obtains its final lock. Under 2PL, serializable transactions can be ordered by their lock points.
Q354. Two transactions request locks in opposite orders: T1 requests A then B, while T2 requests B then A. What problem can arise?
Solution: Deadlock. Each transaction may hold one lock and wait for the other. A global lock-ordering rule can prevent this particular circular-wait pattern.
Q355. How does lock ordering prevent deadlocks?
Solution: Require every transaction to acquire locks according to a consistent global order. This prevents cycles caused by transactions acquiring the same resources in contradictory orders.
Q356. What is conservative 2PL?
Solution: Conservative 2PL requires a transaction to obtain all locks it will need before it begins. It prevents deadlocks caused by lock acquisition but may reduce concurrency and require advance knowledge of the lock set.
Q357. What is the main difference between conservative and strict 2PL?
Solution: Conservative 2PL avoids deadlocks by acquiring all required locks before execution. Strict 2PL retains exclusive locks until completion to simplify recovery; strict 2PL alone does not prevent deadlocks.
Q358. How does a timestamp-based deadlock prevention scheme differ from a timeout?
Solution: Timestamp schemes use transaction ages to decide which transactions wait or abort. A timeout aborts a transaction after waiting too long, which is simpler but may abort transactions even when no deadlock exists.
Q359. What is lock escalation?
Solution: Lock escalation replaces many fine-grained locks with a coarser lock, such as replacing numerous row locks with a table lock. It reduces lock-management overhead but can reduce concurrency.
Q360. Why is intention locking necessary in multiple-granularity locking?
Solution: Intention locks signal that a transaction holds or plans to acquire locks at lower levels. They allow the DBMS to coordinate table-level and row-level locking safely.
Q361. What is multiversion concurrency control (MVCC)?
Solution: MVCC maintains multiple versions of data so that readers can access an appropriate version without necessarily blocking concurrent writers.
Q362. How can MVCC reduce read-write blocking?
Solution: A reader can access a committed historical version while a writer modifies a newer version. The precise behavior depends on the DBMS's snapshot and isolation implementation.
Q363. Does MVCC eliminate all concurrency anomalies?
Solution: No. Its guarantees depend on the isolation level and implementation. Write skew and other anomalies can remain under some snapshot-isolation schemes.
Q364. What is a serialization anomaly?
Solution: It is an outcome of concurrent transactions that cannot be explained by any serial execution of those transactions.
Q365. How does serializable snapshot isolation differ from ordinary snapshot isolation?
Solution: Serializable snapshot isolation adds mechanisms to detect or prevent dangerous dependency patterns so that committed transactions meet serializability requirements.
Q366. What is a dirty write?
Solution: A dirty write occurs when a transaction overwrites data written by another transaction that has not yet committed or aborted. Strict concurrency control generally prevents this.
Q367. What is a write-write conflict?
Solution: It occurs when two transactions attempt incompatible writes to the same logical data item. Locking or validation mechanisms must coordinate the writes.
Q368. Why can a read-only transaction still experience a consistency anomaly?
Solution: Its multiple reads may observe incompatible states or depend on concurrent transactions whose combined effects are not serializable. Snapshot mechanisms can prevent some such anomalies, depending on the isolation guarantee.
Q369. What is a predicate lock?
Solution: A predicate lock protects a set of rows defined by a condition rather than just existing individual rows. It can prevent phantoms by coordinating inserts and updates that would satisfy the predicate.
Q370. How can range locking prevent phantom reads?
Solution: By locking the relevant key range or predicate, the DBMS prevents concurrent transactions from inserting or modifying rows that would change the protected query result, according to the protocol's guarantees.
Q371. A transaction updates X and Y, then aborts. What information is needed for undo recovery?
Solution: The recovery system needs sufficient before-image or equivalent log information to restore the original values of X and Y and to determine which updates belong to the aborted transaction.
Q372. Why must log records be durable before dirty pages are flushed under WAL?
Solution: If a crash occurs after a data page is written, the durable log must contain the information needed to undo or redo that update. Otherwise, recovery may lack the information required to restore correctness.
Q373. A committed transaction has no updated data page on disk when a crash occurs. Is the transaction lost?
Solution: Not necessarily. If its commit is durable and the log contains the required update information, recovery can redo the transaction.
Q374. A transaction has written uncommitted data to disk. What recovery action is necessary after a crash?
Solution: The recovery process must undo the transaction's uncommitted effects, unless the particular storage design guarantees that those effects cannot become visible or persist.
Q375. What is a dirty page in recovery terminology?
Solution: A dirty page is a buffer-pool page modified in memory but not yet written to the database's persistent data files.
Q376. What is a transaction table used for during recovery?
Solution: It tracks transactions relevant to recovery, often including their status and last log sequence number.
Q377. What is a dirty page table?
Solution: It records pages that may have unflushed changes, often with the earliest log sequence number associated with their outstanding changes. Recovery uses it to identify relevant redo work.
Q378. What is the purpose of the analysis phase in ARIES?
Solution: Analysis reconstructs the transaction table and dirty page table from the log and identifies transactions and pages relevant to recovery.
Q379. What is the purpose of the redo phase in ARIES?
Solution: Redo repeats logged actions as needed to restore the database to the state it had at the time of failure, including effects of transactions that were not committed by then.
Q380. What is the purpose of the undo phase in ARIES?
Solution: Undo reverses the effects of transactions that were incomplete at the time of failure, recording compensation log records as appropriate.
Q381. What is a distributed database?
Solution: A distributed database stores logically related data across multiple networked locations while providing coordinated access and management.
Q382. What is data fragmentation?
Solution: Fragmentation divides a relation into smaller parts for distribution. It may be horizontal (rows), vertical (columns), or a combination of both.
Q383. What is replication in distributed databases?
Solution: Replication stores copies of data at multiple sites to improve availability or read performance. It introduces consistency and update-coordination requirements.
Q384. Differentiate between horizontal and vertical fragmentation.
Solution: Horizontal fragmentation partitions rows based on predicates. Vertical fragmentation partitions columns, generally retaining a key or identifier to reconstruct the original relation.
Q385. What is distributed query processing?
Solution: It executes queries over data distributed across multiple sites, choosing where to move data and perform operations to minimize communication and computation costs.
Q386. Why is communication cost important in distributed query optimization?
Solution: Moving large relations over a network may be much more expensive than processing them locally. The optimizer may choose a plan that sends only filtered or projected data.
Q387. What is distributed transaction processing?
Solution: It coordinates a transaction that accesses or modifies data at multiple sites, aiming to maintain the required atomicity and consistency across those sites.
Q388. What is two-phase commit (2PC)?
Solution: Two-phase commit is a distributed commit protocol with a prepare/voting phase followed by a commit-or-abort decision phase. It coordinates participants so that they agree on the transaction's outcome.
Q389. Why can two-phase commit block?
Solution: A participant may have prepared to commit but be unable to learn the final decision if the coordinator fails and required information is unavailable. It may need to wait for recovery or communication.
Q390. What is the role of a coordinator in 2PC?
Solution: The coordinator requests votes from participants, collects their responses, determines the global outcome according to the protocol, and communicates the decision.
Q391. What is the difference between synchronous and asynchronous replication?
Solution: Synchronous replication waits for acknowledgments from specified replicas before confirming a write. Asynchronous replication allows acknowledgment before all replicas have applied the update, potentially leaving replicas temporarily behind.
Q392. What is replica lag?
Solution: Replica lag is the delay between a change being accepted or applied at one site and becoming visible at another replica.
Q393. What is eventual consistency?
Solution: Eventual consistency means replicas converge if updates stop and communication and processing eventually succeed. It does not necessarily guarantee that every read immediately returns the latest global value.
Q394. What is a distributed deadlock?
Solution: A distributed deadlock involves transactions at different sites waiting on one another in a cycle. Detecting it can require collecting or coordinating wait information across sites.
Q395. What is the CAP theorem's core trade-off?
Solution: During a network partition, a distributed system cannot guarantee both linearizable consistency and availability for every request. Systems must define which behavior they prioritize under partition conditions.
Q396. What is a distributed database's global schema?
Solution: It describes the overall logical structure of data across sites, presenting a unified view despite physical distribution and fragmentation.
Q397. Why is distributed database recovery harder than single-site recovery?
Solution: Failures can occur independently at different sites, messages may be delayed or lost, and transaction outcomes may need coordination across multiple logs and participants.
Q398. What is a distributed commit log used for?
Solution: It records decisions and transaction events needed to recover the global outcome after failures. Its exact format and role depend on the distributed transaction protocol.
Q399. Why might a distributed database duplicate data?
Solution: Replication can improve read availability, reduce access latency, and tolerate some site failures. These benefits come with the cost of maintaining consistent copies.
Q400. When should an organization consider a distributed database rather than a centralized database?
Solution: It may be appropriate when data is geographically dispersed, workload demands horizontal scaling, local availability is important, or data ownership requires multiple sites. Distribution also increases operational and consistency complexity.
Part 9 — Integrated DBMS Problems and Advanced Applications (Q401–Q450)
Q401. A university has students, courses, and instructors. Each course may have multiple students and each instructor may teach several courses. Design the main relations.
Solution:
Course.InstructorID references Instructor, and the composite key of Enrollment is (StudentID, CourseID) if each student can enroll in a course only once.
Q402. A company assigns employees to projects. An employee can work on multiple projects, and the hours depend on the employee-project pair. How should this be modeled?
Solution: Use Employee(EmpID, Name), Project(ProjectID, Name), and WorksOn(EmpID, ProjectID, Hours). The hours attribute belongs to the many-to-many relationship, and (EmpID, ProjectID) is the natural key if each pair has one assignment record.
Q403. A student may have several email addresses. Why is storing them as Email1, Email2, and Email3 undesirable?
Solution: It creates repeating groups, limits the number of addresses, and complicates queries and updates. Use a separate relation such as StudentEmail(StudentID, Email).
Q404. An order contains several products, and the same product can occur in many orders. Where should Quantity be stored?
Solution: Store it in OrderLine(OrderID, ProductID, Quantity, UnitPrice), because quantity depends on the particular order-product combination.
Q405. When mapping a specialization to tables, what is one approach for representing subclasses?
Solution: Create a superclass table and separate subclass tables. Each subclass table uses the superclass primary key as both its own primary key and a foreign key to the superclass.
Q406. What is a key constraint in an ER relationship?
Solution: It limits how many related entities may participate. For example, a key constraint on the employee side of a department-employment relationship can indicate that each employee belongs to at most one department.
Q407. A ternary relationship connects Supplier, Part, and Project. Why might three separate binary relationships be insufficient?
Solution: They may lose the information that a particular supplier supplies a particular part to a particular project. The ternary association must be retained when the fact depends on all three entities together.
Q408. What is a participation constraint? Give an example.
Solution: It specifies whether participation in a relationship is mandatory. If every order must belong to a customer, Order has total participation in the relationship with Customer.
Q409. Can a foreign key reference a nonunique column?
Solution: Under standard relational integrity rules, the referenced columns must form an eligible unique key. A foreign key cannot normally reference an arbitrary nonunique column.
Q410. What is a surrogate key, and when is it useful?
Solution: A surrogate key is an artificial identifier, such as an auto-generated integer. It can simplify references when natural identifiers are long, mutable, or unsuitable as primary keys. Natural-key uniqueness may still need enforcement.
Q411. Find the candidate keys of R(A,B,C,D,E) with F={A→BC, CD→E, B→D, E→A}.
Solution: Since A and E each determine A, B, C, D, and E through the dependencies, both A and E are candidate keys. Also, BC→D, and therefore CD→E can be applied when C and D are known. The set BC does not determine A unless E is obtained, so it is not a candidate key. The candidate keys are A and E.
Q412. Given F={A→B, B→C, A→C}, find a minimal cover.
Solution: Remove A→C, since it follows from A→B and B→C. A minimal cover is {A→B, B→C}.
Q413. For R(A,B,C,D), with F={A→B, B→A, A→C, C→D}, find all candidate keys.
Solution: A+=ABCD, so A is a candidate key. Since B→A, B+=ABCD, so B is also a candidate key. No other minimal key is required. The candidate keys are A and B.
Q414. Explain why attribute closure is useful in normalization.
Solution: Attribute closure identifies superkeys, candidate keys, and dependencies implied by a set of functional dependencies. It is also useful for testing whether a dependency follows from a given dependency set.
Q415. Given R(A,B,C), F={A→B, B→A}, find the candidate keys.
Solution: Both AC and BC determine all attributes: A determines B, and B determines A. Neither A nor B alone determines C. Thus the candidate keys are AC and BC.
Q416. In Q415, is the relation in BCNF?
Solution: Yes. The nontrivial dependencies have determinants A and B, neither of which is a superkey for the full relation. Therefore, under the stated dependencies, the relation is actually not in BCNF. The relation illustrates that mutual determination of A and B does not make either one a superkey when C is independent.
Q417. What is a partial functional dependency?
Solution: It occurs when a non-prime attribute depends on a proper subset of a candidate key. For example, (StudentID, CourseID) → StudentName is a partial dependency if StudentID → StudentName.
Q418. What is a transitive dependency in the normalization context?
Solution: It occurs when a key determines an attribute through another non-key determinant. For example, EmployeeID → DeptID and DeptID → DeptName imply EmployeeID → DeptName.
Q419. Why is a 3NF decomposition often preferred when dependency preservation is important?
Solution: The standard 3NF synthesis algorithm can produce a lossless, dependency-preserving decomposition, whereas BCNF decomposition does not always preserve every dependency.
Q420. What is the main limitation of decomposition based only on eliminating redundancy?
Solution: A decomposition must also preserve information and important constraints. A design that reduces redundancy but introduces spurious tuples or loses enforceable dependencies may be unsuitable.
Q421. Write an SQL query to find departments whose average employee salary exceeds ₹60,000.
Solution:
sql
SELECT DeptID
FROM Employee
GROUP BY DeptID
HAVING AVG(Salary) > 60000;
Q422. Write an SQL query to find employees who earn more than their department's average salary.
Solution:
sql
SELECT e.*
FROM Employee e
WHERE e.Salary > (
SELECT AVG(e2.Salary)
FROM Employee e2
WHERE e2.DeptID = e.DeptID
);
Q423. How can you find duplicate email addresses in a table?
Solution:
sql
SELECT Email, COUNT(*) AS Occurrences
FROM Users
GROUP BY Email
HAVING COUNT(*) > 1;
Q424. How can you find rows in one table that have no matching rows in another?
Solution: Use NOT EXISTS or an appropriate anti-join. For example:
sql
SELECT s.*
FROM Student s
WHERE NOT EXISTS (
SELECT 1
FROM Enrollment e
WHERE e.StudentID = s.StudentID
);
Q425. What is the difference between EXISTS and IN?
Solution: EXISTS tests whether a subquery returns at least one row. IN tests membership in a set of values. NULLs can make NOT IN behave unexpectedly, so NOT EXISTS is often safer for anti-join logic.
Q426. Why can an index on a low-cardinality column be ineffective?
Solution: If the column has only a few distinct values, each value may match a large proportion of the table. A scan may cost less than index access, depending on data distribution and clustering.
Q427. What is a query execution plan?
Solution: It is the DBMS's chosen sequence of operations, such as scans, index lookups, joins, sorts, and aggregations, used to execute a query.
Q428. Why can join order affect query performance?
Solution: Different join orders produce different intermediate result sizes. Joining highly selective relations first can reduce the amount of data processed by subsequent operations.
Q429. What is the difference between nested-loop join and hash join?
Solution: A nested-loop join compares rows from one relation against rows from another, potentially using an index. A hash join builds a hash structure on one input and probes it with the other, making it suitable for many equality joins.
Q430. When might a sort-merge join be preferable?
Solution: It can be attractive when inputs are already sorted on the join keys or when sorted output is useful. Otherwise, the sorting cost may outweigh its advantages.
Q431. Explain the lost-update anomaly with two transactions.
Solution: Suppose X initially equals 100. T1 reads 100 and plans to add 20; T2 reads 100 and plans to subtract 10. If T1 writes 120 and T2 then writes 90, T1's update is lost. Locking or suitable isolation can prevent this.
Q432. A transaction transfers ₹500 from A to B. What consistency condition should hold if no other activity occurs?
Solution: The total A+B must remain unchanged. Atomicity ensures both changes occur together, while consistency requires the transfer to preserve the declared balance rules.
Q433. What is a write skew anomaly?
Solution: Two transactions read a shared condition and update different rows based on that condition. Both changes can commit even though their combined result violates the intended constraint.
Q434. Why does a precedence graph use transactions as vertices rather than individual operations?
Solution: Conflict serializability asks whether entire transactions can be ordered serially. Conflicting operations impose ordering constraints between the transactions that contain them.
Q435. A schedule is conflict-serializable. Does that guarantee the same final result as every serial schedule?
Solution: No. It guarantees equivalence to at least one conflict-equivalent serial schedule, not every possible serial order.
Q436. What is a recoverable schedule's commit-order requirement?
Solution: If Tj reads a value written by Ti, then Ti must commit before Tj commits.
Q437. What is the advantage of a cascadeless schedule over a merely recoverable schedule?
Solution: Cascadeless schedules prevent dirty reads, so aborting one transaction does not force other transactions to roll back because they consumed its uncommitted data.
Q438. Why is strictness useful in recovery?
Solution: It prevents transactions from reading or overwriting data written by an uncommitted transaction. This simplifies undo and reduces the risk of cascading aborts.
Q439. How does a DBMS ensure that a committed transaction survives a power failure?
Solution: It uses durable logging and storage mechanisms, often including WAL, commit-record persistence, and recovery procedures. The guarantee also depends on storage hardware and configuration honoring durability requirements.
Q440. What is the difference between a checkpoint and a backup?
Solution: A checkpoint helps the DBMS recover efficiently from a recent log position. A backup is a saved copy used to restore data after more extensive loss or corruption.
Q441. A disk page is 8 KB, and each index entry occupies 80 bytes. Ignoring page headers, approximately how many entries fit in one page?
Solution: 8×1024/80=8192/80=102.4. Therefore, at most 102 full entries fit if entries cannot be split across pages.
Q442. A data file has 1,000,000 records and 100 records per page. How many data pages are needed if all pages are full?
Solution: 1,000,000/100=10,000 pages.
Q443. If a binary search operates on 10,000 sorted pages, roughly how many page probes are needed to locate a page?
Solution: ⌈log2(10,000)⌉=14, since 213=8192 and 214=16384. This idealized estimate ignores caching and storage-specific effects.
Q444. A B+ tree index has four page accesses from root to leaf. If retrieving the record requires one additional data-page access, what is the approximate I/O cost of a cold point lookup?
Solution: Approximately 5 page I/Os, assuming each page access causes physical I/O and no page is cached.
Q445. Why can a clustered index reduce the cost of retrieving many matching rows?
Solution: Matching rows are stored near one another, reducing random page accesses. A nonclustered index may require fetching many scattered data pages.
Q446. A hash table has 256 buckets. How many bits are needed to identify a bucket using a direct binary directory?
Solution: log2(256)=8 bits.
Q447. A B+ tree has fan-out 50. Under an idealized full-tree assumption, how many leaf regions can be reached through three branching levels?
Solution: 503=125,000 leaf regions.
Q448. Why does high B+ tree fan-out reduce tree height?
Solution: Each internal node directs searches to many children. A higher branching factor therefore covers more leaves at each additional level.
Q449. What is the trade-off between a very wide B+ tree node and a narrow node?
Solution: Wider nodes may reduce tree height but require more space per node and can change cache behavior and update costs. Actual page-sized node designs balance fan-out, key size, pointer size, and occupancy.
Q450. A system performs frequent range scans and frequent inserts. Which index property should be considered beyond lookup speed?
Solution: Consider range traversal efficiency, page splits, occupancy, write amplification, concurrency behavior, and index maintenance cost. B+ trees are a common choice because they support ordered scans and dynamic updates.
Part 10 — Final Advanced DBMS Questions (Q451–Q500)
Q451. What is the difference between a centralized database and a distributed database?
Solution: A centralized database is managed at one central site, whereas a distributed database stores data across multiple sites. Distribution can improve locality and scalability but introduces network and coordination challenges.
Q452. What is a data warehouse?
Solution: A data warehouse is a system designed for integrated historical analysis and reporting, usually with workloads that differ from transaction-processing systems.
Q453. Differentiate between OLTP and OLAP.
Solution: OLTP emphasizes frequent, relatively short operational transactions. OLAP emphasizes analytical queries over large amounts of data, often involving scans, aggregations, and historical comparisons.
Q454. What is a star schema?
Solution: A star schema organizes analytical data around a central fact table connected to dimension tables. It is commonly used in data warehousing.
Q455. What is a fact table?
Solution: A fact table stores measurable business events or quantities, together with foreign keys referencing dimensions. Examples include sales amounts and quantities sold.
Q456. What is a dimension table?
Solution: A dimension table stores descriptive attributes used to analyze facts, such as customer, product, location, or date information.
Q457. Why might a data warehouse use denormalized dimension tables?
Solution: Denormalization can simplify analytical queries and reduce joins. This can improve usability and sometimes performance, though it introduces redundancy and requires maintenance.
Q458. What is a slowly changing dimension?
Solution: It is a dimension whose descriptive attributes change over time. Warehouse designs use strategies such as overwriting old values or preserving historical versions, depending on reporting requirements.
Q459. What is a surrogate key in a data warehouse dimension?
Solution: It is an artificial identifier assigned to a dimension row, allowing historical versions of the same business entity to be distinguished.
Q460. What is database schema evolution?
Solution: Schema evolution is the process of changing a database's structure over time while managing compatibility with existing data, applications, and integrations.
Q461. What is a semantic integrity constraint?
Solution: It is a business rule that restricts valid database states, such as preventing an employee's commission from exceeding a specified percentage of salary.
Q462. Why are constraints preferable to relying entirely on application code?
Solution: Database constraints protect data regardless of which application or user performs an update. Application validation remains useful, but database enforcement helps prevent inconsistent writes from bypassing business rules.
Q463. What is a multivalued dependency's trivial case?
Solution: An MVD X↠Y is trivial if Y⊆X or X∪Y contains every attribute of the relation.
Q464. What does the multivalued dependency X↠Y imply about the remaining attributes?
Solution: Given a fixed X value, the Y values vary independently of the remaining attributes. This independence allows a relation to be reconstructed from projections onto X∪Y and the complementary attribute set.
Q465. How does 4NF differ from BCNF?
Solution: BCNF addresses functional dependencies, while 4NF addresses nontrivial multivalued dependencies. A relation can satisfy BCNF but violate 4NF because of an MVD that is not implied by an ordinary functional dependency.
Q466. What is the relationship between 5NF and join dependencies?
Solution: 5NF requires that every nontrivial join dependency be implied by the candidate keys. It addresses redundancy that can arise when a relation must be decomposed into three or more projections.
Q467. What is a lossless join in the context of normalization?
Solution: It means that joining the decomposed relations reconstructs exactly the original relation for every valid instance, without adding spurious tuples.
Q468. Can a relation satisfy 3NF while having redundant data?
Solution: Yes. 3NF reduces redundancy caused by certain functional dependencies but does not eliminate all redundancy arising from multivalued dependencies or more complex join dependencies.
Q469. What is the purpose of a canonical cover in 3NF synthesis?
Solution: It provides a simplified equivalent dependency set from which relations can be constructed while preserving dependencies and, under the standard algorithm, obtaining a lossless decomposition.
Q470. Why is candidate-key identification essential before normalizing a relation?
Solution: Normal forms depend on keys, prime attributes, and dependencies. Without identifying candidate keys, a designer cannot reliably test 2NF, 3NF, or BCNF.
Q471. Can two transactions execute concurrently while the overall schedule remains serializable?
Solution: Yes. Independent operations can interleave, and conflicting operations can be ordered so that the schedule remains equivalent to a serial execution.
Q472. What is the difference between serializability and strictness?
Solution: Serializability concerns equivalence to a serial transaction order. Strictness concerns access to data written by uncommitted transactions. A schedule can satisfy one property without satisfying the other.
Q473. What does a cycle in a wait-for graph indicate?
Solution: In the standard single-instance lock model, a cycle indicates deadlock. With more complex resource models, the exact deadlock test depends on the resource-allocation structure.
Q474. Why is deadlock detection sometimes preferable to prevention?
Solution: Prevention can reduce concurrency or cause unnecessary aborts. Detection allows transactions to proceed normally and intervenes only when a deadlock is identified, at the cost of detection overhead and recovery.
Q475. What is the difference between deadlock and starvation?
Solution: Deadlock is a circular waiting condition with no progress among the affected transactions. Starvation is indefinite postponement of a transaction, even when the system as a whole continues making progress.
Q476. Why is the recovery log usually append-oriented?
Solution: Appending records supports ordered logging, efficient persistence, and recovery analysis. Implementations may use log segments, truncation, archival, and compaction mechanisms as part of log management.
Q477. What is the difference between undo logging and redo logging?
Solution: Undo logging stores information needed to restore previous values. Redo logging stores information needed to reapply updates. Many production recovery systems use both undo and redo information.
Q478. What is a transaction's commit point?
Solution: It is the point at which the transaction is considered committed by the database protocol. In a WAL-based system, the durable commit record is central to this determination.
Q479. Why can a committed transaction's effects be absent from the data files immediately after commit?
Solution: The DBMS can acknowledge commit after the necessary log information is durable, allowing data pages to be written later. Recovery replays the log when needed.
Q480. Why must a recovery algorithm be idempotent or otherwise safely resumable?
Solution: Recovery may be interrupted by another crash. Reapplying recovery actions must not corrupt data or undo work incorrectly. Logging, page-state checks, and recovery markers help make repeated or resumed recovery safe.
Q481. Why is a heap file often appropriate for a table with frequent inserts and few search queries?
Solution: New records can often be placed in available space without maintaining a key order. This makes inserts relatively inexpensive, although searches may require scans unless indexes are added.
Q482. What is the main disadvantage of maintaining many indexes on one table?
Solution: Each index consumes storage and must be maintained during inserts, deletes, and updates to indexed columns. This can substantially increase write costs.
Q483. Why is a B+ tree suitable for database storage on secondary memory?
Solution: Its large branching factor minimizes height, and its balanced structure keeps search depth predictable. Page-oriented nodes reduce the number of storage accesses needed for lookups.
Q484. What is the difference between an index entry and a data record?
Solution: An index entry stores search-key information and a pointer or reference to the relevant data. A data record stores the actual row attributes.
Q485. What is the difference between a primary index and a primary key?
Solution: A primary key is a logical uniqueness constraint identifying rows. A primary index is a physical access structure associated with an ordering key in common textbook terminology. A primary key does not necessarily imply a specific physical file organization.
Q486. What is a composite search key in a B+ tree?
Solution: It is a key made from multiple attributes, ordered lexicographically or according to the DBMS's index ordering rules. The key order affects which queries can use the index efficiently.
Q487. What is a covering index, and what is its main benefit?
Solution: A covering index contains all the columns needed by a query, allowing the DBMS to return the result from the index without fetching the base table rows in suitable circumstances.
Q488. Why is a hash index unsuitable for ORDER BY Salary?
Solution: Hash bucket placement does not preserve salary order. An ordered index such as a B+ tree can support ordered retrieval more naturally.
Q489. Why might a dynamic hash structure split a bucket?
Solution: A bucket split redistributes keys to reduce overflow and maintain access performance as the data set grows.
Q490. What is the main difference between extendible hashing and a conventional static hash file?
Solution: Extendible hashing expands its directory and splits buckets as needed. Static hashing retains a fixed primary bucket structure and often relies on overflow storage as records accumulate.
Q491. A relation R(A,B,C,D) has F={A→B, B→C, C→D}. Find the candidate key and highest normal form.
Solution: A is the only candidate key because A+=ABCD, and A cannot be derived from the other attributes. The relation is in 3NF only if every nontrivial dependency has a superkey determinant or a prime right-hand attribute. Here, B → C and C → D violate 3NF, so the highest normal form is 2NF, assuming atomic attributes.
Q492. For the relation in Q491, give a lossless, dependency-preserving decomposition into BCNF relations.
Solution: Decompose into R1(A,B), R2(B,C), and R3(C,D). Each dependency is preserved, each resulting relation is in BCNF under the stated dependencies, and the decomposition is lossless because the successive intersections determine the corresponding relations.
Q493. A schedule has precedence edges T1→T2, T2→T3, and T3→T1. Can it be conflict-serializable?
Solution: No. The graph contains a directed cycle, so no serial ordering can satisfy all the conflict constraints.
Q494. A transaction writes X, commits, and crashes before the modified page is written. Which recovery action is needed?
Solution: REDO the update if the page does not contain it. The durable commit record and log provide the information needed to preserve the committed transaction.
Q495. A table contains 1,000,000 rows. A query returns 5 rows using a selective indexed predicate. Why might an index be faster than a scan?
Solution: The index can identify the five qualifying rows without reading every data page. The advantage depends on index availability, selectivity, caching, and the cost of fetching the rows.
Q496. A transaction reads a value written by an uncommitted transaction. Which anomaly has occurred, and which schedule property is violated?
Solution: A dirty read has occurred. The schedule is not cascadeless and is not strict. Whether it is recoverable depends on the commit order of the dependent transactions.
Q497. Two concurrent transactions update different rows after reading a common snapshot, and the combined updates violate a business rule. What is this anomaly, and how can it be prevented?
Solution: This is write skew. Possible remedies include serializable isolation, explicit locking of the shared invariant or relevant predicate, or restructuring the transaction so that conflicting updates are detected.
Q498. A database uses an index on (DepartmentID, Salary). Which of these queries is best supported by the index: searching by DepartmentID, searching by DepartmentID and Salary, or searching by Salary alone?
Solution: The index naturally supports searches by DepartmentID and by both DepartmentID and Salary. A search by Salary alone generally cannot use the leading index order as efficiently, though DBMS-specific optimizations may help.