CY 405 Database Management System

1. Data and Database

Data represents facts or values that can be collected and processed. A database is an organized collection of related data. For example, a university database may contain student records, course information, faculty information and examination records.

The usefulness of a database does not simply come from storing information. The database must also provide mechanisms for retrieving relevant information efficiently and maintaining its correctness.

2. File Organization and Access Methods

File organization determines how records are physically arranged in storage. Different organizations can provide different performance characteristics for searching, inserting and updating records.

Access methods determine how records can be located. Sequential access is useful when records are processed in order, whereas direct or indexed access can provide faster retrieval for suitable queries.

3. Characteristics of a DBMS

• Controlled access to data
• Data sharing
• Integrity enforcement
• Transaction management
• Concurrency control
• Backup and recovery facilities
• Data independence

4. Data Models

A data model provides concepts for describing the structure of a database. It helps represent entities, relationships, constraints and other aspects of stored information.

The relational model represents information using relations or tables. The Entity Relationship model provides a conceptual representation using entities, attributes and relationships.

5. Schema and Instance

A database schema describes the structure of a database. It specifies elements such as tables, attributes, relationships and constraints.

A database instance represents the actual data stored in the database at a particular moment. The schema generally changes less frequently, while the instance changes whenever data is inserted, modified or deleted.

6. DBMS Architecture

DBMS architecture describes how the different layers and components of a database system are organized. Database systems can be discussed using levels of abstraction so that users do not need to understand every physical storage detail.

7. Data Independence

Data independence refers to the ability to change a particular level of database structure without requiring inappropriate changes at higher levels.

Physical data independence concerns changes to physical storage structures. Logical data independence concerns changes to the logical structure while minimizing effects on external views.

8. Entity Relationship Model

The Entity Relationship model is used for conceptual database design. An entity represents a distinguishable real-world object or concept. Examples include Student, Course, Employee and Department.

Attributes describe properties of entities. Relationships describe associations between entities. Cardinality specifies how many instances of one entity can be associated with another.

9. Attributes and Entity Types

An attribute represents a property of an entity. For a Student entity, examples might include Roll Number, Name and Branch.

Attributes may be simple or composite, single-valued or multivalued, and stored or derived depending upon the nature of the data.

10. Relationships, Cardinality and Participation

A relationship represents an association between entity types. Cardinality describes the number of participating entities. Common cardinality forms include one-to-one, one-to-many and many-to-many.

Participation specifies whether participation of an entity in a relationship is mandatory or optional according to the defined constraints.

1. Relation, Tuple, Attribute and Domain

In the relational model, data is represented using relations. A relation can be visualized as a table. Each row is called a tuple and each column corresponds to an attribute.

A domain defines the set of permitted values associated with an attribute. For example, an Age attribute may be restricted to suitable integer values.

2. Keys

Keys are used to identify records and establish relationships between relations.

• Super Key
• Candidate Key
• Primary Key
• Alternate Key
• Foreign Key
• Composite Key

3. Integrity Constraints

Integrity constraints help maintain valid data. Common relational constraints include domain constraints, key constraints and referential integrity constraints.

A primary key generally identifies tuples uniquely, while a foreign key provides a mechanism for representing relationships between tables.

4. Relational Algebra

Relational algebra is a procedural query language based on operations performed on relations. Understanding these operations helps students understand the theoretical foundation of relational query processing.

• Selection
• Projection
• Rename
• Union
• Intersection
• Difference
• Cartesian Product
• Join
• Division

5. SQL

SQL, or Structured Query Language, provides commands for defining, manipulating and querying relational databases. SQL is declarative, meaning the user generally describes what information is required rather than specifying every low-level step used to obtain it.

Example: Creating a Table

CREATE TABLE Student (
    RollNo INT PRIMARY KEY,
    Name VARCHAR(50),
    Branch VARCHAR(50),
    Semester INT
);

This statement creates a Student table with a primary key and attributes for student information.

Example: Retrieving Data

SELECT Name, Branch
FROM Student
WHERE Semester = 4;

The query retrieves the name and branch of students whose semester value is 4.

Example: Updating Data

UPDATE Student
SET Branch = 'Cyber Security'
WHERE RollNo = 101;

UPDATE modifies existing records that satisfy the specified condition.

SQL Joins

A join combines related information from multiple tables. For example, Student and Course tables can be combined when they share a suitable relationship.

SELECT Student.Name, Course.CourseName
FROM Student
JOIN Course
ON Student.CourseID = Course.CourseID;

Nested Queries, Views and Triggers

A nested query is a query placed inside another query. A view provides a virtual representation of selected database information. A trigger is a database mechanism that can execute an associated action automatically when specified database events occur.

1. Functional Dependency

A functional dependency describes a relationship between attributes in a relation. If one set of attributes determines another set, the dependency can be represented using an expression such as X → Y.

For example, if each RollNo uniquely identifies a student's Name, then RollNo can functionally determine Name under the assumed database rules.

2. Why Normalization Is Needed

Poorly designed tables may contain repeated information. Such designs can lead to insertion, deletion and update anomalies.

Normalization provides a systematic approach for decomposing relations into better-structured relations while considering dependencies and decomposition properties.

3. First Normal Form — 1NF

A relation is generally considered to satisfy first normal form when attributes contain atomic values according to the relational model's assumptions, rather than repeating groups or inappropriate multivalued fields inside a single cell.

4. Second Normal Form — 2NF

Second normal form builds on 1NF and addresses partial dependency in relations with composite candidate keys. The goal is to ensure that non-key attributes do not depend only on part of a composite key.

5. Third Normal Form — 3NF

Third normal form further reduces dependency problems by addressing transitive dependencies under the formal conditions of 3NF.

6. BCNF

Boyce-Codd Normal Form is a stronger normal form than 3NF. In simplified terms, BCNF requires the determinant of every non-trivial functional dependency to be a candidate key, subject to the formal definition.

7. Dependency Preservation

When a relation is decomposed, dependency preservation considers whether the important functional dependencies can still be enforced using the decomposed relations without requiring an expensive reconstruction of the original relation.

8. Lossless Join Decomposition

A decomposition should ideally allow the original relation to be reconstructed without introducing spurious tuples. Such a decomposition is called lossless with respect to the relevant relation and dependencies.

1. Transaction

A transaction is a logical unit of database work. It may consist of multiple operations that together represent one meaningful task.

A banking transfer is a common conceptual example. The operation may involve deducting an amount from one account and adding it to another. Treating related operations as one logical unit is important for maintaining consistency.

2. Desirable Transaction Properties

Database transaction processing is commonly discussed using the ACID properties:

• Atomicity: a transaction's operations are treated as a logical unit.
• Consistency: integrity constraints should remain satisfied.
• Isolation: concurrent execution should provide suitable isolation semantics.
• Durability: committed changes should survive appropriate failures.

3. Schedules

A schedule represents the order in which operations from multiple transactions are executed.

Schedules are important because transactions may execute concurrently. The order of read and write operations can affect the final state of the database.

4. Serializability

Serializability is a correctness criterion used to determine whether a concurrent schedule is equivalent, under the relevant definition, to an acceptable serial execution.

Conflict serializability can be studied using conflicting read/write operations and a precedence graph. A cycle in the graph indicates that the schedule is not conflict serializable.

5. Two Phase Locking

Two Phase Locking, commonly called 2PL, divides the locking behavior of a transaction into two conceptual phases: a growing phase and a shrinking phase.

The growing phase allows locks to be acquired, while the shrinking phase allows locks to be released without acquiring new locks under the basic protocol.

6. Timestamp-Based Concurrency Control

Timestamp-based methods assign ordering information to transactions and use timestamps to determine whether conflicting operations can proceed.

The central idea is to enforce an ordering of conflicting operations according to the chosen timestamp protocol.

7. Deadlocks

A deadlock occurs when transactions wait for resources held by one another in such a way that none of them can continue.

Deadlock handling may involve prevention, avoidance, detection and resolution strategies. These approaches differ in how and when the system attempts to prevent the deadlock condition.

8. Recovery

Recovery techniques help restore a database to a consistent state after certain failures. The syllabus includes deferred update, immediate update, shadow paging and checkpoints.

1. Secondary Storage

Database systems often manage data volumes much larger than the amount that can be kept entirely in main memory. Secondary storage therefore plays an important role in database systems.

Storage access characteristics influence database performance. Efficient organization and retrieval mechanisms are therefore essential for large databases.

2. Indexing

An index is an auxiliary data structure that can help locate records more efficiently than scanning every record in a file.

The benefit of indexing depends on factors such as the query, data distribution, index structure, storage characteristics and maintenance cost.

3. Single-Level and Multilevel Indices

A single-level index provides one level of index entries. As the index itself becomes large, multiple levels can be introduced so that higher levels help locate appropriate portions of lower levels.

4. Hashing

Hashing uses a hash function to map a search key to a location or bucket. It can provide efficient equality-based access when the hashing structure and workload are appropriate.

Hash collisions occur when multiple keys map to the same location. A hashing implementation must therefore provide an appropriate collision-handling mechanism.

5. Query Processing

Query processing involves transforming a user's query into an execution process that obtains the requested result.

Different algorithms may be available for implementing relational operations such as selection, projection and joins.

6. Query Optimization

Query optimization aims to choose an efficient execution strategy from possible alternatives. The goal is to reduce relevant resource costs while producing the required result.

Optimization can consider factors such as available indexes, relation sizes, access paths and join strategies.

7. Contemporary DBMS Case Study

A contemporary DBMS can be studied by examining its data model, query language, indexing approach, transaction capabilities, concurrency mechanisms, recovery features and typical use cases.

When studying a case study, focus not only on the product name but also on the database concepts demonstrated by the system.