lecture 1,2

Fundamental Concepts and Definitions .1

.Data: Known facts that can be recorded and have an implicit meaning ●​
.Database: A collection of related data ●​
Database Management System (DBMS): A software package/system designed to ●​
.facilitate the creation and maintenance of a computerized database
Database System: The combination of the DBMS software and the database itself ●​
.)(sometimes including applications
Mini-world: An aspect of the real world represented in a database, such as ●​
.university transcripts or company records
Metadata: Descriptions of the database structure, types, and constraints stored in ●​
.the DBMS catalog

Types of Databases and Applications .2

According to the sources, databases are used across various domains, including business,
:medicine, and law. Specific types include

.Traditional: Stores textual or numeric information ●​

.Multimedia: Stores images, audio, and video streams ●​
Geographic Information Systems (GIS): Used for maps, weather data, and satellite ●​
.imagery
Data Warehouses (OLAP): Used to extract and analyze information for decision ●​
.making
Real-time Databases: Handle rapidly changing workloads, such as the stock ●​
.market

The Database Approach vs. File Processing .3

The sources highlight several disadvantages of traditional file processing, such as data
:redundancy, inconsistency, and wasted storage. The database approach offers

.)Self-describing nature: The system contains its own description (metadata ●​

.Data Sharing: A single repository is accessed by various users ●​
Multiple Views: Different users see different subsets or virtual data based on their ●​
.interests
Concurrency Control: Ensures that multiple users can access and update data ●​
.correctly without interference
Transaction Properties: Includes Atomicity (all operations execute or none do) and ●​
.)Isolation (transactions appear to execute independently

Data Models, Schemas, and Instances .4

 Data Model: A set of concepts used to describe the structure, operations, and ●​
.constraints of a database
Conceptual Models: High-level; close to how users perceive data (e.g., ER ○​
.)Model
.Physical Models: Low-level; describe exact storage details on the computer ○​
Implementation/Representational Models: A bridge between the two, used ○​
.)by commercial DBMS (e.g., Relational Model
.Database Schema: The description of the database; it changes infrequently ●​
Database State (Instance/Snapshot): The actual data stored at a particular ●​
.moment; it changes every time the database is updated

DBMS Languages and Architecture .5

Data Definition Language (DDL): Used by DBAs and designers to specify the ●​
.conceptual schema
Data Manipulation Language (DML): Used for data retrieval, insertions, ●​
.deletions, and updates
:Architectures ●​
.Centralized: Everything (software, hardware, UI) is on a single system ○​
Client-Server: User devices (clients) connect over a network to powerful ○​
.computers (servers) that store and process the data

Entity-Relationship (ER) Model Concepts .6

Entities: Specific objects with physical existence (e.g., a person) or conceptual ●​

.)existence (e.g., a job
:Attributes: Properties describing an entity. Types include ●​
.)Simple: Atomic values (e.g., SSN ○​
Composite: Composed of components (e.g., Address consists of Street, City, ○​
.)State
Multi-valued: An entity can have multiple values (e.g., {Color} for a car), ○​
.shown in double ovals
Derived: Values calculated from other attributes (e.g., Age derived from ○​
.Birth_date), shown in dashed ovals
Key Attributes: Attributes with unique values for each entity, identified by being ●​
.underlined

Relationships and Constraints .7

Relationship Type: The schema description of how entities relate (e.g., ●​

.WORKS_FOR), represented by a diamond-shaped box
.)Degree: The number of participating entity types (e.g., Binary has degree 2 ●​
Recursive Relationship: The same entity type participates more than once in ●​
different roles (e.g., Supervisor vs. Supervisee roles in a SUPERVISION
.)relationship
.)Cardinality Ratio: Specifies the maximum participation (1:1, 1:N, or M:N ●​
:Participation Constraint ●​
.)Total: Every entity must participate (shown by a double line ○​
 .)Partial: Participation is optional (shown by a single line ○​

Weak Entity Types .8

.A Weak Entity does not have its own key attribute ●​

.It is identified through an identifying relationship with an owner entity type ●​
It always has a total participation constraint (existence dependency) regarding its ●​
.owner
Example: A DEPENDENT is a weak entity identified by its name and the EMPLOYEE ●​
.it is related to

lecture 3,4
1. Relationship Constraints and Structural Notations

●​ Cardinality Ratio: Specifies the maximum participation for an entity in a relationship.

Common ratios are One-to-one (1:1), One-to-many (1:N), and Many-to-many
(M:N).
●​ Participation Constraint: Also known as the Existence Dependency Constraint, it
specifies minimum participation.
○​ Total Participation: Every entity in the set must participate in the relationship
(existence-dependent), shown by a double line.
○​ Partial Participation: Participation is optional, shown by a single line.
●​ (min, max) Notation: An alternative notation where each entity's participation is
defined by a range. For example, a department has exactly one manager (1,1), while
an employee can manage at most one department (0,1).
●​ Attributes of Relationships: Relationship types can have their own attributes (e.g.,
"Hours" for a WORKS_ON relationship). In 1:N relationships, these can be moved to
the entity on the N-side.

2. ER-to-Relational Mapping Algorithm

This algorithm provides a step-by-step process to convert an ER conceptual schema into a

relational database schema:

●​ Step 1: Regular Entity Types: Create a relation including all simple attributes.
Choose one key as the Primary Key (PK).
●​ Step 2: Weak Entity Types: Create a relation including all simple attributes of the
weak entity. Include the PK of the owner entity as a Foreign Key (FK). The PK of this
new relation is the combination of the owner’s PK and the weak entity's partial key.
●​ Step 3: Binary 1:1 Relationship Types: There are three approaches:
1.​ Foreign Key Approach: Include the PK of one relation as an FK in the other
(preferably in the relation with total participation).
2.​ Merged Relation: Merge the two entities into a single relation (appropriate if
both have total participation).
 3.​ Cross-reference: Create a third relation to link the PKs of both entities.
●​ Step 4: Binary 1:N Relationship Types: Identify the relation at the N-side and
include the PK of the 1-side relation as an FK.
●​ Step 5: Binary M:N Relationship Types: Create a new relation to represent the
relationship. Include the PKs of both participating entities as FKs; their combination
forms the PK of this new relation.
●​ Step 6: Multivalued Attributes: Create a new relation including the attribute itself
and the PK of the parent entity as an FK.
●​ Step 7: N-ary Relationship Types (Degree > 2): Create a new relation and include
the PKs of all participating entity types as FKs. The PK is usually the combination
of these FKs.

3. Enhanced Entity-Relationship (EER) Modeling

EER modeling adds concepts like subclasses, superclasses, and inheritance to model
applications more accurately.

●​ Subclasses and Superclasses: An entity type can have subgroups (subclasses)

that inherit all attributes and relationships from the parent (superclass). This is often
called an "IS-A" relationship (e.g., a SECRETARY IS-A EMPLOYEE).
●​ Specialization vs. Generalization:
○​ Specialization: A top-down process of defining subclasses based on
distinguishing characteristics (e.g., defining ENGINEER based on job type).
○​ Generalization: A bottom-up process of identifying common features
between several entity types and creating a shared superclass (e.g.,
generalizing CAR and TRUCK into VEHICLE).
●​ Inheritance: A member of a subclass inherits all attributes and relationship
participations of the superclass.

4. Constraints on Specialization and Generalization

●​ Disjointness Constraint:
○​ Disjoint (d): An entity can be a member of at most one subclass.
○​ Overlapping (o): An entity can be a member of multiple subclasses
simultaneously.
●​ Completeness Constraint:
○​ Total Specialization: Every entity in the superclass must belong to at least
one subclass (shown by a double line).
○​ Partial Specialization: An entity may not belong to any subclass (shown by a
single line).
●​ Hierarchies and Lattices:
○​ Hierarchy: Each subclass has only one superclass (single inheritance).
○​ Lattice: A subclass can have more than one superclass (multiple
inheritance), forming a shared subclass.
lecture 5,6
1. Enhanced Entity-Relationship (EER) Modeling

●​ Specialization: This is a top-down conceptual refinement process where a set of

subclasses is defined based on distinguishing characteristics of entities in a
superclass. For example, "Engineer" and "Technician" are specializations of the
"Employee" superclass.
●​ Generalization: This is a bottom-up synthesis process where several entity types
with common features are combined into a single superclass.
●​ Attribute Inheritance: Subclasses inherit all attributes of their superclass as well as
all attributes of predecessor superclasses in a hierarchy or lattice. They can also
have local attributes specific only to the subclass.
●​ Constraints on Specialization:
○​ Disjointness: Specifies if an entity can belong to only one subclass (disjoint,
denoted by 'd') or multiple subclasses (overlapping, denoted by 'o').
○​ Completeness: Specifies if every entity in a superclass must belong to a
subclass (total, shown by a double line) or if it is optional (partial, shown by
a single line).
●​ Union Types (Categories): A category represents a subclass that is a union of
different entity types (superclasses). While a shared subclass member must exist
in all its superclasses, a category member must exist in at least one of its
superclasses.

2. Mapping EER Models to Relational Schemas

Mapping specialization into relations can be achieved through four primary options:

●​ Option 8A (Multiple relations - Superclass and Subclasses): Create a relation for

the superclass and separate relations for each subclass. This works for any
specialization.
●​ Option 8B (Multiple relations - Subclass relations only): Only create relations for
the subclasses, which include the superclass attributes. This works only for total
specializations.
●​ Option 8C (Single relation with one type attribute): Use one relation containing all
attributes of the superclass and all subclasses, plus a type attribute (discriminator).
This is used for disjoint specializations.
●​ Option 8D (Single relation with multiple type attributes): Use one relation with
Boolean flags for each subclass. This is ideal for overlapping specializations.
●​ Mapping Categories: When mapping a union type where superclasses have
different keys, it is standard to create a surrogate key (e.g., OwnerId) to serve as the
primary key for the category relation.

3. Functional Dependencies and Normalization

●​ Design Guidelines: A good relational design should ensure that each tuple
represents exactly one entity or relationship instance. Attributes of different entities
 should not be mixed, and schemas should minimize update anomalies (insertion,
deletion, and modification issues) caused by redundant information.
●​ Functional Dependency (FD): A constraint where a set of attributes X uniquely
determines the value of attributes Y ($X \rightarrow Y$). These are derived from
real-world constraints on the data.
●​ Normalization: The process of decomposing "bad" relations into smaller relations to
improve quality and avoid redundancy.
●​ Normal Forms (NF):
○​ First Normal Form (1NF): Disallows multivalued attributes or nested
relations.
○​ Second Normal Form (2NF): Every non-prime attribute must have a full
functional dependency on the primary key, meaning no attribute depends on
only a part of the key.
○​ Third Normal Form (3NF): A relation must be in 2NF and have no transitive
dependencies, meaning no non-prime attribute is determined by another
non-prime attribute.
○​ Boyce-Codd Normal Form (BCNF): A stronger version of 3NF where every
determinant in a functional dependency must be a superkey.

lecture 7,8
I. Indexing Structures for Files

Indexing is an auxiliary access structure used to speed up the retrieval of records by

providing secondary access paths without changing the physical placement of the primary
data.

●​ Core Concepts:​

○​ Index Structure: Usually consists of a file with entries in the form of <field
value, pointer to record>, ordered by the field value.
○​ Search Efficiency: An index allows for binary search, which is significantly
faster than a linear search (scanning the whole file).
○​ Index Density:
■​ Dense Index: Contains an entry for every search key value (and
every record) in the data file.
■​ Sparse (Nondense) Index: Contains entries for only some search
values, typically one for each disk block.
●​ Types of Single-Level Ordered Indexes:​

○​ Primary Index: Defined on an ordered data file where the ordering field is a
key field. It is a sparse index where each entry points to the "block anchor"
(the first record in a block).
○​ Clustering Index: Used when the data file is ordered on a non-key field
(clustering field). It contains one entry for each distinct value of the field.
 ○​ Secondary Index: Provides access via a non-ordering field (either a key or
non-key). It is typically a dense index, requiring more storage than a primary
index but offering a vast improvement over linear searches.
●​ Multilevel Indexes:​

○​ When a single-level index is large and covers many blocks, a primary index
can be created for the index itself.
○​ This process can be repeated to create third and fourth levels until the top
level fits into a single disk block, further reducing the number of block
accesses.

II. The Relational Data Model

The relational model represents data as a collection of relations, which informally resemble
tables.

●​ Terminology Mapping:​

○​ Relation: Table.
○​ Attribute: Column header.
○​ Tuple: Row (an ordered set of values).
○​ Domain: The set of valid values for a column.
○​ State: The populated data in a table at a specific time.
●​ Relational Integrity Constraints:​

○​ Domain Constraints: Every value in a tuple must belong to the defined

domain of that attribute.
○​ Key Constraints:
■​ Superkey: A set of attributes where no two tuples have the same
value.
■​ Key: A "minimal" superkey; removing any attribute destroys the
uniqueness property.
■​ Primary Key: The candidate key chosen to uniquely identify tuples; its
attributes are underlined.
○​ Entity Integrity: Primary key attributes cannot have null values, as they are
used to identify individual tuples.
○​ Referential Integrity: Specified between two relations (referencing and
referenced). The Foreign Key (FK) in the referencing relation must match a
Primary Key (PK) value in the referenced relation or be NULL.
●​ Update Operations and Violations:​

○​ Operations: INSERT, DELETE, and MODIFY.

○​ Remedies for Violations:
■​ RESTRICT/REJECT: Cancel the operation causing the violation.
■​ CASCADE: Propagate the change (e.g., deleting referencing tuples
when the referenced tuple is deleted).
 ■​ SET NULL/DEFAULT: Change the referencing foreign keys to a null
or default value.

III. Performance Comparison Example

For a file with 30,000 records across 3,000 blocks:

●​ Linear Search: Average of 1,500 block accesses.

●​ Binary Search on Data File: Approximately 12 block accesses.
●​ Primary Index Search: 7 block accesses (6 for index + 1 for data).
●​ Secondary Index Search: 10 block accesses (9 for index + 1 for data).
●​ Multilevel Index Search: 4 block accesses (3 levels + 1 for data).

lecture 9,10.
I. Relational Algebra Operations

Relational algebra is a set of operations for the relational model where the result of any
operation is a new relation, a property known as being "closed".

●​ Unary Operations:
○​ SELECT ($\sigma$): Acts as a filter to keep only tuples satisfying a specific
Boolean condition. It is commutative, meaning the order of a sequence of
SELECT operations does not matter.
○​ PROJECT ($\pi$): Performs vertical partitioning by keeping specified
columns and discarding others. It automatically removes duplicate tuples to
ensure the result is a mathematical set.
○​ RENAME ($\rho$): Used to change the names of relations or attributes,
which is essential for operations like JOIN.
●​ Set Theory Operations: Includes UNION ($\cup$), INTERSECTION ($\cap$), and
SET DIFFERENCE (–). These require "type compatibility," meaning operands must
have the same number of attributes with compatible domains.
●​ Binary and Additional Operations:
○​ CARTESIAN PRODUCT ($\times$): Combines every tuple from one relation
with every tuple of another.
○​ JOIN ($\bowtie$): A more efficient sequence of Cartesian product followed
by SELECT. Variations include EQUIJOIN (equality comparisons) and
NATURAL JOIN ($*$), which removes superfluous duplicate attributes.
○​ OUTER JOIN: Keeps tuples even if they have no matching counterparts in
the other relation, padding the result with NULL values (Left, Right, or Full).
○​ Aggregate Functions ($\mathcal{F}$): Performs mathematical summaries
like SUM, AVERAGE, COUNT, MAX, and MIN, often combined with grouping
attributes.

II. Query Processing Algorithms

Processing queries involves translating high-level SQL into algebraic operations and
executing them efficiently.

●​ External Sorting: Since database files are often too large for main memory, external
sorting uses a sort-merge strategy. It involves a sorting phase (creating small
sorted "runs") and a merging phase.
●​ SELECT Implementation Methods:
○​ Linear Search: Retrieving every record (brute force).
○​ Binary Search: Used if the file is ordered on a key attribute.
○​ Index-based Search: Using Primary, Clustering, or Secondary indexes to
retrieve single or multiple records.
●​ JOIN Implementation Methods:
○​ J1: Nested-loop Join: Compares every record of the outer loop with every
record of the inner loop.
○​ J2: Single-loop Join: Uses an existing index on one of the join attributes to
retrieve matching records directly.
○​ J3: Sort-merge Join: The most efficient method if both files are already
sorted by the join attributes.

III. Query Optimization

Query optimization is the process of choosing the most efficient execution plan from many
possible strategies.

●​ Heuristic Optimization: This approach uses rules to improve query trees:

○​ Apply SELECT and PROJECT operations as early as possible to reduce the
size of intermediate results.
○​ Break up conjunctive SELECT conditions into a cascade of operations to
move them further down the tree.
○​ Replace Cartesian Products followed by a selection with a JOIN operation.
●​ Cost-Based Optimization: Compares the estimated costs of different strategies
using catalog information.
○​ Cost Components: These include secondary storage access cost,
computation cost, and communication cost.
○​ Catalog Data: The optimizer uses statistics like the number of records ($r$),
number of blocks ($b$), indexing levels ($x$), and selectivity (the fraction of
records satisfying a condition).
○​ Selection Cardinality ($s$): The average number of records satisfying an
equality condition ($s = sl \times r$). A lower cardinality makes a condition
more desirable to execute first.