৪৯তম বিসিএস ⎯ তথ্য ও যোগাযোগ প্রযুক্তি [২৮১]

A Database Management System (DBMS) is a software system used to manage databases. It provides an interface for users and applications to interact with the data, allowing operations such as creating, reading, updating, and deleting data. The DBMS ensures data integrity, security, and efficient retrieval.

Example:
MySQL, PostgreSQL, and Oracle are examples of DBMS that store, manage, and provide access to databases.

Others option:
A collection of interrelated data: 
​This defines a database, not the DBMS itself.

​A set of programs to manage data: 
​The DBMS is a set of programs designed for managing databases.

​A table where data is stored: 
​This is an aspect of a database, not the DBMS.

​A method to backup data:
​ A backup is one operation supported by a DBMS but not the main purpose of a DBMS.
​
​Source: "Database System Concepts" by Abraham Silberschatz

In the context of a relational database, a relation refers to a table, which is a collection of tuples (rows) that represent individual records. A relation is defined by its schema (structure), which consists of attributes (columns) and the set of tuples (rows).

Example:

Consider a table named Students:
​
​Each row (tuple) in this table represents a student record.

Others option:

A set of tables: 
​ A relation refers to a single table, not a collection of tables.

A collection of attributes:
​ Attributes are the columns of a relation, but a relation is a collection of tuples.

A set of tuples: 
​ A relation is made up of tuples (rows) in a table.

A collection of SQL queries: 
​ SQL queries are used to interact with the database but are not relations themselves.

Source: Database Management Systems by Raghu Ramakrishnan

OUTER JOIN is a category of joins, not a standalone type. It includes LEFT OUTER JOIN, RIGHT OUTER JOIN, and FULL OUTER JOIN. These types of joins return records that do not have matching rows in the other table, along with the matching rows.

Example:
​
SELECT * FROM Employees
LEFT OUTER JOIN Departments ON Employees.DepartmentID = Departments.DepartmentID;

This query retrieves all employees, including those who don’t belong to a department.

Option Breakdown:

INNER JOIN: 
​INNER JOIN returns only matching records from both tables.

LEFT JOIN: 
​ LEFT JOIN (or LEFT OUTER JOIN) returns all records from the left table and matching records from the right table.

RIGHT JOIN: 
​ RIGHT JOIN (or RIGHT OUTER JOIN) returns all records from the right table and matching records from the left table.

OUTER JOIN: 
​ OUTER JOIN is a category of joins, not a specific type. It includes LEFT OUTER JOIN, RIGHT OUTER JOIN, and FULL OUTER JOIN.

​
Source: SQL for Smarties by Joe Celko

In the Entity-Relationship (ER) model, relationships define how entities (tables) are related to each other. The common types of relationships are:
One-to-One (1:1): 
​• One entity is associated with exactly one other entity.
​• This is a valid relationship type in the ER model.

One-to-Many (1:M): 
​• One entity is associated with multiple instances of another entity.
​• This is a valid relationship type in the ER model.

Many-to-Many (M:N): 
• ​Many entities are associated with many other entities.
• This is a valid relationship type in the ER model.​

One-to-Single (1:S): 
​• This is not a valid relationship type in the ER model.
​• There is no One-to-Single (1:S) relationship in the ER model.

Source: "Database System Concepts" by Abraham Silberschatz

One-to-One (1:1):
​A one-to-one mapping is always unique because each element in the first set is related to exactly one element in the second set, and vice versa. No element in either set can map to more than one element in the other set. For example, in a system where each student has a unique ID number, a one-to-one mapping would ensure that each student is paired with exactly one ID number, and each ID number corresponds to one student only.

Example:
• Set A (Students): {John, Jane, Alice}
• Set B (Student ID): {S001, S002, S003}
• Mapping: John → S001, Jane → S002, Alice → S003

In this case, each student has a unique ID, and no ID is repeated. Hence, it’s a one-to-one relationship.
​
​Option Analysis:
​One-to-Many (1:M):
​In a one-to-many mapping, one element in the first set can be related to multiple elements in the second set. 
​Example: 
​• Set A (Department): {Math, English}
​• Set B (Teachers): {Mr. Smith, Ms. Davis, Mr. Brown}
• Mapping: Math → Mr. Smith, English → Mr. Davis, English → Mr. Brown
​
​Many-to-One (M:1): 
​A many-to-one mapping allows multiple elements in the first set to be related to a single element in the second set.
​Example:
• Set A (Students): {John, Jane, Alice}
• Set B (School): {School A}
• Mapping: John → School A, Jane → School A, Alice → School A
​
​Many-to-Many (M:N): 
​In a many-to-many mapping, multiple elements in the first set can be related to multiple elements in the second set. 
Example:
Set A (Students): {John, Jane, Alice}
Set B (Subjects): {Math, Science, History}
Mapping: John → Math, John → Science, Jane → Math, Alice → History
​
​Source: Introduction to Mathematical Logic by Elliott Mendelson

The relational model is the most widely used data model in databases. It represents data in the form of tables (also known as relations), where each table consists of rows (records) and columns (attributes). Each table has a primary key that uniquely identifies each row, and foreign keys are used to establish relationships between tables.

Example:
In a relational database, data might be stored in tables like Customers, Orders, and Products, where relationships are established using foreign keys.

Option Analysis:

Hierarchical model: 
​The hierarchical model organizes data in a tree-like structure, but it is not as widely used as the relational model.
Network model:
​The network model organizes data in a graph structure but is less commonly used than the relational model.
Relational model: 
​The relational model is the foundation of most modern database systems like MySQL, PostgreSQL, and Oracle.
Object-oriented model: 
​While the object-oriented model is used in some databases, it is not as common as the relational model.

Source: Database System Concepts by Abraham Silberschatz

The ACID properties are a set of properties that ensure reliable processing of database transactions:

​Atomicity: Ensures that a transaction is treated as a single unit, which either fully completes or fully fails.
Consistency: Ensures that a transaction brings the database from one valid state to another.
Isolation: Ensures that concurrent transactions do not affect each other.
Durability: Ensures that once a transaction is committed, its changes are permanent.

Example:
In a bank transaction, transferring money from one account to another must ensure that either both debit and credit operations are completed or none at all (atomicity), and the database remains consistent after the transaction.

Option Analysis:

Atomicity:  
​Atomicity is one of the ACID properties.

Consistency:  
​Consistency is one of the ACID properties.

Isolation:  
​Isolation is one of the ACID properties.

Density:  
​Density is not an ACID property of transactions.

Source: Database Management Systems by Raghu Ramakrishnan

The DISTINCT keyword in SQL is used to return only unique values, removing any duplicates from the result set. It can be applied to one or more columns in a query to ensure that duplicate records are excluded.

Example


This query retrieves only unique department names from the Employees table, eliminating duplicates.

Option Analysis:

DISTINCT:  
​The DISTINCT clause removes duplicate records from the result set.

GROUP BY:  
​GROUP BY is used to group rows that have the same values into summary rows.

HAVING:  
​HAVING is used to filter records after grouping them, typically used with aggregate functions.

ORDER BY:  
​ORDER BY is used to sort the result set but does not remove duplicates.

Source: SQL For Smarties by Joe Celko

SELECT command retrieves data from the database but does not modify or alter the data in any way. It is used for querying the database and retrieving specific information based on the provided conditions.

Examples:

​This retrieves the names of students from the CSE department without altering the table data.

Other options:

INSERT: 
​This command is used to insert new records into a table, which modifies the data.

UPDATE: 
​This command is used to modify existing records in a table.

DELETE: 
​This command is used to delete records from a table, which also modifies the data.
​
Sources:
Data Communications and Networking, 4th Edition by Behrouz A. Forouzan 

The HAVING clause is used to filter groups after the GROUP BY operation in SQL. While the WHERE clause filters rows before the grouping operation, the HAVING clause filters the groups formed by GROUP BY after the aggregation.

HAVING is specifically designed to filter aggregated results. It is typically used when performing operations like COUNT, SUM, AVG, MAX, or MIN, and you want to filter based on the results of these aggregate functions.

Examples of HAVING Clause:

•Basic Example with GROUP BY and HAVING:

​This query retrieves the number of employees in each department, but only for departments with more than 10 employees.

•Example with Aggregate Functions:

​This query retrieves the average salary for each city, but only for cities where the average salary is greater than 50,000.
​
​Sources: SQL For Dummies by Allen G. Taylor.

In the Hierarchical model, data is represented in a tree-like structure, where each record has a single parent and can have multiple children. The root of the tree represents the highest-level record, and each child record can point to its parent record.

Example:
A company organization might be represented with the CEO at the top of the hierarchy, followed by departments as children of the CEO, and employees as children of each department.

Others option:

Data is organized into tables with rows and columns: 
​This is the structure of the relational model, not the hierarchical model.

Data is stored in a tree-like structure:
​The Hierarchical model uses a tree structure to represent data.

Data is represented as objects: 
​This is characteristic of the object-oriented model, not the hierarchical model.

Data is stored in graphs with nodes and edges: 
​This is characteristic of the graph model, not the hierarchical model.

Source: Database Management Systems by Raghu Ramakrishnan

In the Object-Oriented Database (OOD) model, data is stored as objects similar to how objects are used in object-oriented programming (OOP). These objects can have both attributes (data) and methods (functions). This model allows for greater flexibility when representing complex data and behaviors. ​In the object-oriented model, data is stored as objects, which are analogous to objects in programming languages like Java or C++.

Example:

Consider an Employee object in an OOD, which might have attributes like Name and Salary, and methods like 'calculateBonus()'. Relationships between objects (such as an Employee object having an association with a Department object) are also represented directly.

Others option:

Data is stored in tables:
​This is characteristic of the relational model, not the object-oriented model.

Data is represented using graphs and nodes: 
​This describes the graph model, not the object-oriented model.

Data is organized in a tree structure: 
​This is the characteristic of the hierarchical model, not the object-oriented model.

Source: Object-Oriented Database Systems by David Maier

The B+ Tree has a logarithmic time complexity (O(log n)) for search, insertion, and deletion operations. This is because the tree is balanced, and the height of the tree is kept small due to the branching factor (degree of nodes). This ensures that search and update operations remain efficient, even for large datasets.

Example:
In a B+ Tree with a branching factor of 3:
            • To search for a value, the search begins from the root node and follows the appropriate path, and the time complexity is O(log n) due to the tree's height being logarithmic in relation to the number of elements.

Options:
O(n log n): 
​ B+ Tree operations are more efficient, with a time complexity of O(log n), not O(n log n).
​
O(n): 
​ A B+ Tree provides logarithmic time complexity for search and updates, not linear.

 O(1): 
​ O(1) is constant time, but B+ Tree operations are logarithmic, not constant.


​O(log n): 
​ All operations (search, insert, and delete) take logarithmic time due to the balanced structure of the B+ Tree.

Source: "Database Management Systems" by Raghu Ramakrishnan

A secondary index requires additional storage because it is a separate data structure that maintains a list of values from the indexed column(s) along with pointers to the corresponding rows in the table. This increases the overall storage requirements, especially when there are multiple secondary indexes on large tables.

Example:
In a table with multiple secondary indexes (e.g., on Name, Department, and Salary), each index consumes additional storage space.

Option:

It requires a larger amount of storage: 
​ Secondary indexes consume additional storage because they store the indexed column values and pointers.

It improves the performance of all database queries: 
​ Secondary indexes improve performance for specific queries, not all queries.

It is slower than a primary index: 
​ Secondary indexes are optimized for searches on non-primary key columns, and while they may not be as fast as primary indexes, they are still efficient.

It is not useful for range queries: 
​ Secondary indexes can be used for efficient range queries on non-primary key columns.

Source: "Database Management Systems" by Raghu Ramakrishnan

The WHERE clause filters rows before the GROUP BY operation and does not work with aggregate functions. It is used to filter individual rows from the table.

Example:
 
​This query retrieves only employees whose age is greater than 30 → filtering rows individually.
​
​other options:
​
​GROUP BY → Groups rows based on one or more columns (used with aggregate functions like SUM(), COUNT()).
HAVING → Filters groups created by GROUP BY, not individual rows.
ORDER BY → Sorts the output rows but does not filter them.
​
​Sources: Data Communications and Networking by Behrouz A. Forouzan

There are several common techniques to resolve collisions in hash tables:

Linear Probing:
​When a collision occurs, the algorithm checks the next available index in a linear fashion. Linear probing is one method to resolve collisions by checking subsequent indices.

Quadratic Probing:
​Similar to linear probing, but it checks indices at increasing intervals (e.g., index + 1², + 2², + 3²). Quadratic probing also resolves collisions by checking subsequent indices, but with quadratic increments.

Chaining:
​When a collision occurs, each table entry stores a linked list of all keys that hash to the same index. This allows multiple values to be stored at the same index. Chaining resolves collisions by linking multiple values at the same index using a linked list.

Example:

• Linear Probing: If index 5 is occupied, the algorithm checks index 6, then index 7, and so on.

• Quadratic Probing: If index 5 is occupied, the algorithm checks index 6, then index 9 (5 + 1²), then index 14 (5 + 2²), and so on.

• Chaining: If two keys hash to the same index, the second key is added to the linked list at that index.

​ All three methods are valid collision resolution techniques in hash tables.

Source: "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein

The goal of query optimization is to improve the efficiency of query execution. The DBMS analyzes multiple ways of executing a query and selects the most efficient one based on cost, which typically includes factors like CPU time, disk I/O, and memory usage.

Example:

If a query retrieves data from multiple tables, the optimizer might decide to use an index or reorder the join operations to minimize disk reads and CPU time, improving the overall performance of the query.

Option:

To make the database design simpler: 
​ Query optimization focuses on execution efficiency, not database design.

To reduce the cost of executing queries: 
​ The purpose of query optimization is to minimize resource consumption (e.g., CPU, memory, I/O) during query execution.

To improve the physical storage of data: 
​ Physical storage optimization is a separate process, typically handled during database design or maintenance.

To eliminate redundant data in the database: 
​ Data redundancy elimination is handled through normalization, not query optimization.

Source: "Database Management Systems" by Raghu Ramakrishnan

Query optimization focuses on improving the execution of SQL queries based on factors like the selectivity of conditions, available indexes, and the structure of the query. Database schema is generally fixed and doesn't change with query optimization.

Example:

Selectivity of predicates: A predicate like WHERE age > 30 may be more selective if there are fewer people over 30, and this will influence the optimizer’s choice of execution plan.

Available indexes: The optimizer uses indexes on columns to reduce disk I/O during query execution.

Option:

Selectivity of predicates: 
​ Selectivity refers to how much of the data is being filtered by the predicates, which is considered during optimization.

Available indexes: 
​ The optimizer checks which indexes are available to speed up query execution.

Query structure: 
​ The structure of the query (e.g., joins, subqueries) affects how the optimizer evaluates execution plans.

Database schema: 
​ The schema is fixed and does not change during query optimization.

Source: "SQL Performance Explained" by Markus Winand

The commit operation is used to make all changes made by the transaction permanent. Once a transaction is committed, its effects are visible to other transactions, and the changes are written to the database permanently. This ensures that the database remains in a consistent state.

Example:

If you transfer money from one account to another, the commit operation ensures that the debit from one account and the credit to the other account are permanently recorded in the database.

Option:

A command to cancel the transaction: 
​ Rollback is the operation that cancels a transaction.

A command to start a transaction: 
​ A transaction is typically started by a begin transaction operation, not a commit.

A command to make the transaction's changes permanent: 
​ Commit is used to finalize a transaction and make its changes permanent.

A command to roll back the transaction: 
​ Rollback is used to undo the changes of a transaction, not commit.

Source: "Database System Concepts" by Abraham Silberschatz

Shadow paging is a recovery technique in which every page in the database has two copies: the original and the shadow copy. When a transaction modifies a page, the modification is done to the shadow copy. If a failure occurs, the system can use the original page to recover the database.

Example:

During a transaction, if a page is modified, the shadow page is updated. If the system crashes, the original page is used to maintain the database's consistency, and the modified shadow page is discarded.

Option:

Shadow paging: 
​ This technique uses both shadow pages and original pages to ensure consistency in case of a crash.

Database mirroring: 
​ Mirroring is about maintaining a duplicate of the database, not a recovery technique.

Normalization: 
​ Normalization is a data design process, not related to recovery.

Data redundancy: 
​ Redundancy is generally minimized in databases, but it's not a recovery technique.

 Source: "Fundamentals of Database Systems" by Elmasri and Navathe

RBAC simplifies management by assigning users to roles (e.g., Admin, Manager, Guest) instead of giving permissions individually.

Option:

DAC → Owner controls access.
MAC → Enforced by system security policies.
ABAC → Access decided based on user attributes (time, location, etc.).

Example: Bank software: “Teller” can update customer accounts, “Manager” can approve loans.
​
​Source: Fundamentals of Database Systems (7th Edition) by Elmasri & Navathe.

SQL → is designed for relational databases (tables, rows, columns), not directly for XML.

XQuery → is a W3C standard query language for XML. It is specifically designed to extract and manipulate data stored in XML format.

DTD (Document Type Definition) → defines the structure and rules of an XML document (like schema validation), but is not a query language.

C++ → is a general-purpose programming language, not used directly for querying XML data.

Therefore, the query language commonly associated with XML data is XQuery.
​
​Example:
​Suppose we have XML data:
​
​XQuery Example:
​
​Output:
​Computer Networks

​This query retrieves the title of books authored by "Forouzan".

Source: Fundamentals of Database Systems (7th Edition) by Elmasri & Navathe 

In XPath, the root node is the top-most element of the XML document.

Using / (single slash) selects the root node and all of its immediate child nodes.

This is different from //, which selects nodes from anywhere in the document.

⇒ Think of / as:

• Start at the root node
• Go one step down (child nodes only)

Example:
​

​​XPath: /bookstore/*

→ Selects all child nodes of → i.e., all elements.

XPath: //book

→ Selects all elements anywhere in the document.

Options:

ক) / → Selects child nodes of the root element.
খ) // → Selects nodes from anywhere in the document, not just direct children.
​​গ) * → Matches all element nodes at the current level, but needs context (e.g., /bookstore/*).
ঘ) . → Refers to the current node itself, not its children.
​
​Source: Data Communications and Networking by Behrouz A. Forouzan

> The for loop iterates over every element.
> The return clause outputs each .

So, if there are 10 students, it returns all 10 elements.

Sources: Computer Networks (4th Edition) by Andrew S. Tanenbaum.

In a Relational Database (RDBMS), we create simple tables with rows and columns.

In an Object-Relational Database (ORDBMS), we extend this by introducing new object types (e.g., custom structures, inheritance).

The SQL extension CREATE TYPE is used to define user-defined object types (UDTs) that can then be used inside tables.

This allows ORDBMS to support complex data structures, like objects, multimedia, and spatial data.

CREATE TYPE is part of the SQL:1999 (SQL3) standard, which introduced object-relational features.
​Example:
​
​Here, Address is a user-defined object type created with CREATE TYPE.
​
​Sources: Fundamentals of Database Systems (7th Edition) by Elmasri & Navathe 
​
​

⇒ OODBMS (Object-Oriented Database Management System)
​• Stores objects directly.

• Each object has a unique Object Identity (OID), independent of its value.

• Supports encapsulation, inheritance, and polymorphism.
​
​⇒ ORDBMS (Object-Relational Database Management System)
​• Extends relational model with object features.

• Provides user-defined data types, inheritance, and sometimes object identity (OID) to link complex objects.

Therefore, the common feature between OODBMS and ORDBMS is Object Identity (OID).

This allows both systems to uniquely identify and manipulate objects independent of their values.
​
​Example:

Suppose we store a Student object:
​
​Student {

  OID: 105,

  Name: "Rahim",

  Age: 2
​2

}
​
Source: Fundamentals of Database Systems (7th Edition) by Elmasri & Navathe.

• Range Queries → Queries like:
​           
​SELECT * FROM Students WHERE Age BETWEEN 20 AND 25;
​
​Here, we don’t just need one exact record; we need a range of values.

• Hashed File Organization is efficient for exact match queries, but not suitable for ranges because hashing destroys order.
• Sequential File Organization allows range queries if data is sorted, but scanning may be very slow for large files.
• Direct Access is similar to random access → efficient for one record, not for ranges.

• Indexed File Organization (e.g., B+ Tree indexes) is most efficient for range queries because:
​         →Index maintains sorted order of keys.
​         →You can quickly find the starting point of the range.
​         →Then scan sequentially through index pointers.
​In practice, B+ Trees are widely used for range queries in DBMS.

Example:
​
​Index (Age) → [18, 19, 20, 21, 22, 23, 24, 25, 26]

Query: Age BETWEEN 20 AND 25
Step 1: Index locates 20 quickly
Step 2: Scan forward → 21, 22, 23, 24, 25

​Very efficient compared to scanning the entire file.
​
​Option:

ক) Sequential → Works for ranges if sorted, but linear scan is slow.
খ) Hashed →  Bad for range queries since hashing doesn’t preserve order.
গ) Indexed →  Best choice. Maintains order → fast search for range queries.
ঘ) Direct → Random/direct access good for single records, not ranges.

Source: Fundamentals of Database Systems by Elmasri & Navathe.

Hashed File Organization uses a hash function to calculate the address of a record directly from its search key.
This makes it the fastest method for exact match queries (e.g., searching for a student ID = 2025001).
No need to scan sequentially or use tree traversal → a direct lookup gives the result in O(1) time (on average).

Example:

If a student’s roll number is the key, the hash function might map 2025001 → bucket 7. The record can then be directly retrieved from bucket 7.​
​
Hash Function: h(key) = key % 10

Search Key = 2025001
h(2025001) = 2025001 % 10 = 1
→ Record stored in Bucket 1 (directly accessed).
​
​Very efficient for equality conditions like WHERE Roll = 2025001.

Options:

ক) Sequential → Reads records one after another. Very slow for exact match unless the data is ordered.
খ) Hashed → Best for exact match queries because it jumps directly to the record using the hash function. ✔
গ) Indexed → Efficient for range queries (age BETWEEN 20 AND 30) or ordered searches, but slower than hashing for a single exact match.
ঘ) Clustered → Stores related records together (physically ordered by key), useful for range queries, but not as fast as hashing for a single exact lookup.

Source: Fundamentals of Database Systems by Elmasri & Navathe.

⇒ Sequential Access means data is read one record after another in the order they are stored, without skipping.
⇒ It is similar to reading a book page by page.
⇒ Common in magnetic tapes or situations where batch processing is required.

 For example, payroll systems where all employee records are processed in sequence at month’s end.

Example:
​File Records: [101, 102, 103, 104, 105]
Sequential Access → Read 101 → then 102 → then 103 → then 104 → then 105
​You cannot jump directly to 104 without first passing 101, 102, and 103.

Options:

ক) Direct Access → Allows retrieval of records by directly jumping to a specific location using key-to-address mapping. (Faster, not sequential).
খ) Random Access → Same as direct; records can be read/written in any order.
গ) Sequential Access → Reads records in sequence, from beginning to end.
ঘ) Hashed Access → Uses a hash function to directly compute the address of a record (fast for exact match lookups.
​
​Source: Data Communications and Networking by Behrouz A. Forouzan.