Database Fundamentals

Data Model: A set of concepts that can be used to describe the structure of a database (data, relationships between data, and constraints).

Data Model Operations:

• Basic Operations: Add, Delete, Retrieve, Update
• User-defined Operations: e.g., Compute GPA

A data model is the main tool for providing data abstraction by hiding storage details.

• Provide concepts close to how users perceive data
• Concerned with WHAT data is represented (not HOW)
• Often expressed with graphical notation: ER diagram, UML
• No detail about computer implementation or storage

Examples: Entity-Relationship Model, Object-Oriented Model

• Provide concepts between high-level and low-level
• Balance user views with some computer storage details
• Concerned with HOW data is represented in the database
• Hide some details of data storage

Examples: Relational, Hierarchical, Network Data Models

• Provide concepts describing how data is stored as files
• Represent: record formats, record orderings, access paths
• Access Path: A structure that makes the search for particular DB records efficient

Database Schema: The description of a database. Includes descriptions of the database structure and the constraints.

• Specified during database design
• Not expected to change frequently
• Also called Intension

Database Instance (State): The actual data stored in a database at any particular moment in time. Also called Extension.

• Initial Database State: When database is first loaded
• Valid State: A state that satisfies structure and constraints
• Database state changes every time the database is updated

A convenient tool for visualizing schema levels in a DB system.

Proposed to support:

• Program-data independence
• Support of multiple views of the data

• Contains multiple external schemas or views
• Each schema describes the part of DB a user group is interested in
• Hides the rest of the database from that user group

Describes: That part of the database relevant to each user

• Contains one conceptual schema
• Describes structure and constraints of whole database

Describes: WHAT data is stored, relationships, and constraints

• Contains one internal schema
• Describes physical storage structures and access paths

Describes: HOW data is stored

Data Independence: The capacity to change the schema at one level without having to change the schema at the next higher level.

1. Logical Data Independence

Capacity to change the conceptual schema without changing external schemas or application programs.

2. Physical Data Independence

Capacity to change the internal schema without changing the conceptual schema.

• Used by DBA and database designers to specify the conceptual schema
• DDL compiler translates statements and provides DB schema stored in catalog
• Also used to define internal and external schemas (views)

Examples: CREATE TABLE, ALTER TABLE, DROP TABLE, CREATE VIEW

• Used to specify database retrievals and updates
• DML commands can be embedded in a host language (COBOL, C)
• Or applied directly as stand-alone commands (query language)

Examples: SELECT, INSERT, UPDATE, DELETE

A DBMS is a complex software system with multiple components that work together to manage the database.

• Stored Data Manager: Controls access to DBMS information stored on disk (database and catalog)
• DDL Compiler: Processes schema definitions and stores them in the catalog
• Runtime Database Processor: Handles database access at runtime (executes privileged commands, query plans, and canned transactions)
• Query Compiler: Handles interactive queries by parsing, analyzing, compiling, and optimizing them
• Precompiler: Extracts DML commands from application programs written in host language

The catalog stores:

• Names of files, data items, and storage details
• Mapping information between schemas at different levels
• Constraints on the data
• Descriptive information (owner, creation date, usage statistics)

Most DBMSs have database utilities that help the DBA manage the database system:

• Used to load existing data files into the database
• Converts data from various formats (text, spreadsheet) to database format
• Reformats data for storage in the database

• Creates a backup copy of the database
• Usually dumps entire database onto tape or other storage medium
• Incremental backups are also supported (only changes since last backup)

• Reorganizes database file structures
• Improves performance by optimizing storage
• Creates new indexes or removes old ones

• Monitors database usage and provides statistics to DBA
• Helps DBA make decisions about reorganization or optimization
• Tracks query execution times, disk access patterns, etc.

• Data Dictionary/Repository: Stores catalog information and design decisions
• Report Writers/Generators: Create reports from database data
• Application Development Environments: Tools to develop GUI applications
• Communication Software: Allows users to access database remotely

Database systems can be organized using different architectures based on how components are distributed.

• All DBMS functionality, application programs, and user interface run on a single machine
• Users access through terminals (dumb terminals with no processing power)
• All processing is done on the central computer
• Example: Mainframe systems

• Specialized servers with specific functionality (print server, file server, web server, database server)
• Client machines provide user interface and local processing
• Clients access servers when needed
• Connected via network (LAN or Internet)

• Tier 1 (Client): User interface programs and application programs run on client
• Tier 2 (Server): Query and transaction functionality provided by server
• Client sends SQL queries to database server
• Server processes queries and returns results
• Uses standards like ODBC (Open Database Connectivity) and JDBC (Java Database Connectivity)

• Tier 1 (Presentation/Client): User interface (Web browser, mobile app)
• Tier 2 (Business Logic/Application Server): Application programs, business rules, data validation
• Tier 3 (Database Server): DBMS and database storage
• Common for web applications
• Better security: clients cannot directly access database

Aspect	Two-Tier	Three-Tier
Complexity	Simpler	More complex
Scalability	Limited	Better
Security	Direct DB access	DB hidden from client
Use Case	Small applications	Web/Enterprise apps

1. According to Data Model

• Hierarchical: DB as tree of nodes, access top-to-bottom using pointers
• Network: DB as graph, access using links
• Relational: DB as collection of relations (tables), access using values
• Object: Uses OO language functionality

2. According to Number of Users

• Single-user: One user at a time (PC)
• Multi-user: Multiple users concurrently

3. According to Purpose

• General-purpose
• Special-purpose

4. According to Number of Sites

• Centralized: Data stored at a single site
• Distributed: Data distributed on many sites (Network)

Entity: A "thing" in the real world such as an object, subject, or event that can be identified in the Universe of Discourse (UoD) and is distinguishable from other similar objects.

Entities are important things in the miniworld described in the database.

Physical Entity: Tangible things like Building, Car, Person

Conceptual Entity: Abstract concepts like Student, Employee, Course

Entity Type: Describes the schema/intension for a set of entities which have the same attributes. Represented as a rectangle box in ER diagram.

Entity Set: The collection of all entities of a particular entity type at any point in time (extension/instance).

Each Entity Type is described by its NAME and a list of its attributes.

Strong Entity:

• Existence does NOT depend on other entities
• Has a key on its own
• Notation: Single rectangle
• Examples: Student, Course, Employee

Weak Entity:

• Existence DEPENDS on another strong entity (owner)
• Has a partial key (discriminator)
• Notation: Double rectangle
• Examples: Section (depends on Course), Dependent (depends on Employee)

Attributes: Important features of an entity that describe its properties. They are relevant for the miniworld and have to be recorded in the database.

A particular entity will have a value for each of its attributes.

Key Attribute: One or more attributes that uniquely identifies each entity of the entity set. Also called uniqueness constraint.

• Value identifies each entity uniquely
• Must be distinct for each entity in the entity set
• Unique for every extension of the entity type
• Cannot be NULL valued
• Notation: Underlined name inside oval

Domain/Value Set: Set of possible values that may be assigned to the attribute. Denoted by Dom(attribute).

Cardinality of a domain: The number of possible values that the domain can contain.

Null Value: Used when attribute value is unknown (not available) or not applicable.

Important: NULL is NOT 0 (zero) and NOT a blank string!

Simple vs Composite Attributes

Simple (Atomic): Cannot be further divided. Example: Age, Sex, Title

Composite: Can be divided into smaller subparts with independent meanings.

• Name(FirstName, LastName, MiddleName)
• Address(Street, City, State, Country)
• Phone(AreaCode, PhoneNumber, Extension)

Single-valued vs Multi-valued Attributes

Single-valued: Have only one value. Example: Gender = F

Multi-valued: Have a set of values. Notation: Double oval

• Degree = {BSc, Master, Ph.D.}
• Phone = {Home, Office, Mobile}
• Color = {White, Blue, Red}

Note: In relational model, attributes are always single-valued (atomic)!

Stored vs Derived Attributes

Stored: Actually stored in the database

Derived: Can be calculated from other stored attributes. Notation: Dashed oval

• Age can be derived from Birth_date
• Yearly_Salary = 12 * Monthly_Salary
• Number_of_Employees derived from counting employees in department

Relationship Type: An association among two or more entity types. A relationship relates entities with a specific meaning.

Relationship Set: A set of relationship instances of a particular relationship type.

Notation: Diamond shape connected to entity rectangles by lines.

Degree: The number of participating entity types in a relationship.

• Binary (Degree 2): Two entity types - Most common
• Ternary (Degree 3): Three entity types
• N-ary (Degree n): N entity types

Recursive Relationship: When the same entity type participates more than once in the same relationship type in different "roles".

Relationship types can also have attributes, similar to entity types.

• 1:1 relationships: Attributes can be migrated to either participating entity
• 1:N relationships: Attributes can be migrated to the N-side entity
• M:N relationships: Attributes CANNOT be migrated - must stay with relationship

Cardinality Ratio: Specifies the number of relationship instances that an entity can participate in.

One-to-One (1:1)

An entity in A is associated with at most ONE entity in B, and vice versa.

One-to-Many (1:N) / Many-to-One (N:1)

An entity in A is associated with ANY NUMBER of entities in B, but an entity in B is associated with at most ONE entity in A.

Many-to-Many (M:N)

An entity in A is associated with ANY NUMBER of entities in B, and vice versa.

Participation Constraint: Specifies whether an entity MUST participate in a relationship instance or can exist independently.

Total Participation (Existence Dependency)

Every entity of the entity type MUST participate in the relationship.

Notation: Double line connecting entity to relationship

Partial Participation

Entities CAN exist independently without participating in the relationship.

Notation: Single line connecting entity to relationship

Identifying Relationship: A relationship between a strong entity and a weak entity type.

• The key of the strong entity is required to uniquely identify instances of the weak entity
• The weak entity has a partial key that, combined with the owner's key, uniquely identifies it
• Notation: Double diamond for identifying relationship

Symbol	Meaning
Rectangle	Entity Type
Double Rectangle	Weak Entity Type
Diamond	Relationship Type
Double Diamond	Identifying Relationship
Oval	Attribute
Oval with underlined text	Key Attribute
Double Oval	Multi-valued Attribute
Dashed Oval	Derived Attribute
Oval hierarchy	Composite Attribute
Double Line	Total Participation
Single Line	Partial Participation
1, M, N labels	Cardinality Ratio

There are several alternative notations used for ER diagrams. Different tools and textbooks may use different notations, but they all represent the same concepts.

The original notation proposed by Peter Chen in 1976:

• Entities: Rectangles
• Relationships: Diamonds
• Attributes: Ovals connected to entities/relationships
• Cardinality: Numbers (1, M, N) on relationship lines
• Participation: Single line (partial) or double line (total)

This is the notation used throughout this course.

Also known as Information Engineering (IE) notation. Popular in industry tools:

• Entities: Rectangles (with attributes listed inside)
• Relationships: Lines connecting entities (no diamond)
• Cardinality symbols at line ends:
  • Circle (○) = Zero (optional)
  • Line (|) = One (mandatory)
  • Crow's foot (⋈) = Many

Symbol	Meaning
||	One and only one (mandatory)
○|	Zero or one (optional)
|⋈	One or many (mandatory)
○⋈	Zero or many (optional)

Specifies the minimum and maximum number of relationship instances:

• Written as (min, max) next to the entity
• min = 0: Partial participation
• min = 1: Total participation
• max = 1: Each entity participates in at most one relationship
• max = N: No limit on participation

UML (Unified Modeling Language) can also represent ER concepts:

• Entities: Classes (rectangles with 3 compartments: name, attributes, methods)
• Relationships: Associations (lines with multiplicity)
• Cardinality: Written as multiplicity (1, 0..1, 1..*, 0..*)
• Composition: Filled diamond (strong ownership)
• Aggregation: Empty diamond (weak ownership)

UML Multiplicity	Meaning
1	Exactly one
0..1	Zero or one
1..*	One or more
0..* or *	Zero or more

Aspect	Chen	Crow's Foot	(Min,Max)	UML
Entity	Rectangle	Rectangle	Rectangle	Class box
Relationship	Diamond	Line only	Diamond	Line
Attributes	Ovals	Inside entity	Ovals	Inside class
Cardinality	1, M, N	Symbols	(min,max)	Multiplicity
Common Use	Academic	Industry tools	Academic	Software design

EN: A Domain D is a set of atomic (indivisible) values. Each domain has a logical definition (meaning) and a data type or format. Examples: USA_phone_numbers (10-digit character string), SSN (9-digit string), Names (character strings). A domain is typically specified by: data-type, format, and range/values.

EN: An Attribute A is the name of a role played by some domain D in the relation. D is called the domain of A, denoted as dom(A). Different attributes can have the same domain. Example: Home_phone and Office_phone can both have the domain Phone_numbers but play different roles.

EN: A tuple t is an ordered set of values <v₁, v₂, ..., vₙ> corresponding to the attributes of a relation. Each value vᵢ is an element of dom(Aᵢ) or is a special NULL value. The ith value in tuple t, which corresponds to attribute Aᵢ, is referred to as t[Aᵢ] or t.Aᵢ.

EN:

• Relation Schema R(A₁, A₂, ..., Aₙ): The "intention" - describes the structure including relation name, attribute names, and their domains. It is relatively static (rarely changes).
• Relation Instance r(R): The "extension" - the actual set of tuples (rows) in the relation at any given time. It changes frequently as data is inserted, deleted, or updated.
• Degree: The number of attributes n in the schema
• Cardinality: The number of tuples in the current instance

EN:

1. Ordering of tuples: Tuples in a relation are NOT ordered (a relation is a SET of tuples)
2. Ordering of values in a tuple: Values within a tuple ARE ordered (alternative: self-describing tuples)
3. Values in tuples: All values are considered atomic (indivisible) - flat relational model
4. No duplicate tuples: A relation cannot have two identical tuples (key constraint)
5. NULL values: Represent unknown, not available, or not applicable values

EN: A Superkey (SK) of a relation R is a set of attributes that contains at least one unique identifier for every tuple. No two tuples can have the same values for SK. Any superset of a superkey is also a superkey. A superkey may contain redundant attributes.

EN: A Candidate Key (CK) is a minimal superkey - a superkey with no redundant attributes. If we remove any attribute from a candidate key, it is no longer a superkey. A relation may have multiple candidate keys. Example: In EMPLOYEE, both SSN and {Fname, Lname, Bdate} could be candidate keys.

EN: The Primary Key (PK) is the candidate key chosen by the database designer to uniquely identify tuples. It is underlined in the relation schema. Primary key values cannot be NULL (Entity Integrity Constraint). Each relation must have a primary key. Example: EMPLOYEE(SSN, Fname, Lname, Bdate, Address).

EN: A Composite Key is a key that consists of two or more attributes. Example: In a relation ENROLLMENT(Student_ID, Course_ID, Grade), the combination of {Student_ID, Course_ID} forms a composite primary key.

EN: A Foreign Key (FK) is a set of attributes in one relation that references the primary key of another relation (or the same relation). It creates a link between two relations. The FK must either contain a value matching a PK value in the referenced relation, or be NULL. Example: Dno in EMPLOYEE references Dnumber in DEPARTMENT.

EN:

Key Type	Description	Can be NULL?
Superkey	Any set of attributes that uniquely identifies tuples	May contain NULLs
Candidate Key	Minimal superkey (no redundant attributes)	No
Primary Key	Chosen candidate key for identification	NO (Entity Integrity)
Foreign Key	References primary key in another relation	Yes (if partial participation)

EN: Constraints are conditions that must hold on all valid relation instances. There are three main types of relational integrity constraints:

1. Key Constraints: No duplicate tuples (uniqueness)
2. Entity Integrity Constraints: No NULL primary keys
3. Referential Integrity Constraints: Foreign keys must match existing primary keys or be NULL

Another type is Domain Constraints which specifies that values must be from the attribute's domain.

EN: Domain Constraints specify that within each tuple, the value of each attribute A must be an atomic value from the domain dom(A). The data types associated with domains include: integers, real numbers, characters, fixed-length strings, variable-length strings, date, time, timestamp, etc.

EN: Key Constraints state that no two tuples in a relation can have the same combination of values for all their attributes. This is based on the definition that a relation is a SET of tuples, and sets do not allow duplicate elements. The superkey uniquely identifies any tuple. A candidate key is a minimal superkey.

EN: The primary key cannot be NULL in any tuple of a relation. This is because the primary key is used to identify individual tuples. If PK = NULL, we cannot identify certain tuples. Note: Other attributes (non-PK) can be NULL. For composite primary keys, no individual attribute can be NULL.

EN: A referential integrity constraint is specified between two relations and is used to maintain consistency among tuples. It states: A tuple in the referencing relation (R1) that refers to another relation (R2) must refer to an existing tuple in R2.

If a foreign key FK in R1 references PK in R2, then for each tuple t1 in R1:

• Either t1[FK] = NULL
• Or there exists a tuple t2 in R2 such that t1[FK] = t2[PK]

EN: Database operations that can cause constraint violations:

• INSERT: Can violate domain constraints, key constraints, entity integrity (NULL PK), or referential integrity
• DELETE: Can violate referential integrity (if tuple is referenced by FK)
• UPDATE (MODIFY): Can violate any constraint depending on what is changed

When referential integrity is violated on DELETE/UPDATE, options include: RESTRICT (reject), CASCADE (propagate), SET NULL, or SET DEFAULT.

There are three basic operations that can change the states of relations in a database:

• INSERT: Add a new tuple to a relation
• DELETE: Remove an existing tuple from a relation
• UPDATE (MODIFY): Change values of some attributes in an existing tuple

Each operation may cause constraint violations, and the DBMS must handle them appropriately.

Purpose: Add a new tuple to a relation R

Syntax: INSERT INTO R VALUES (v1, v2, ..., vn)

Possible Constraint Violations:

• Domain Constraint: If an attribute value is not in the correct domain
  Example: Inserting Age = 'Twenty' when Age must be integer
• Key Constraint: If the key value already exists in the relation
  Example: Inserting a student with SSN that already exists
• Entity Integrity: If the primary key value is NULL
  Example: Inserting a student with NULL Student_ID
• Referential Integrity: If a foreign key value does not exist in the referenced relation
  Example: Inserting an employee with Dept_No = 9 when no department 9 exists

If violation occurs: REJECT the insertion

Purpose: Remove a tuple from a relation R

Syntax: DELETE FROM R WHERE condition

Possible Constraint Violations:

• Referential Integrity ONLY: If the tuple being deleted is referenced by a foreign key in another relation
  Example: Deleting a department that has employees assigned to it

Note: DELETE cannot violate domain, key, or entity integrity constraints.

Purpose: Change the value(s) of one or more attributes in an existing tuple

Syntax: UPDATE R SET attribute = value WHERE condition

Possible Constraint Violations:

• If updating a NON-KEY attribute:
  • Domain Constraint - if new value not in domain
• If updating a PRIMARY KEY:
  • Similar to DELETE + INSERT
  • Key Constraint - if new PK value already exists
  • Entity Integrity - if new PK value is NULL
  • Referential Integrity - if old PK was referenced by FK
• If updating a FOREIGN KEY:
  • Referential Integrity - if new FK value doesn't exist in referenced relation

When a referential integrity constraint is violated by DELETE or UPDATE, the DBMS can handle it using one of the following options:

Option	Action	Example
RESTRICT	Reject the operation that causes violation	Cannot delete department if employees exist
CASCADE	Propagate the operation to referencing tuples	Delete department → automatically delete all its employees
SET NULL	Set FK value to NULL in referencing tuples	Delete department → set employees' Dept_No to NULL
SET DEFAULT	Set FK value to default value in referencing tuples	Delete department → set employees' Dept_No to default dept

Constraint	INSERT	DELETE	UPDATE
Domain	✓ Can violate	✗ No	✓ Can violate
Key	✓ Can violate	✗ No	✓ If PK changed
Entity Integrity	✓ Can violate	✗ No	✓ If PK changed
Referential Integrity	✓ Can violate	✓ Can violate	✓ Can violate

Given: EMPLOYEE(SSN, Name, Dept_No) and DEPARTMENT(Dept_No, Dept_Name)

1. INSERT Example:

INSERT INTO EMPLOYEE VALUES ('123456789', 'John Smith', 5)

• ✓ Valid if SSN is unique and Department 5 exists
• ✗ Violates Key Constraint if SSN already exists
• ✗ Violates Referential Integrity if Department 5 doesn't exist

2. DELETE Example:

DELETE FROM DEPARTMENT WHERE Dept_No = 5

• ✓ Valid if no employees reference Department 5
• ✗ Violates Referential Integrity if employees work in Department 5
• Solution: Use CASCADE, SET NULL, or SET DEFAULT

3. UPDATE Example:

UPDATE EMPLOYEE SET Dept_No = 9 WHERE SSN = '123456789'

• ✓ Valid if Department 9 exists
• ✗ Violates Referential Integrity if Department 9 doesn't exist

EN: For each regular (strong) entity type E, create a relation R that includes all the simple attributes of E.

• Include only simple component attributes of a composite attribute (not the composite attribute itself)
• Choose one key attribute of E as primary key for R
• If the key of E is composite, the set of simple attributes together form the primary key

EN: Entity Types: EMPLOYEE, DEPARTMENT, PROJECT

Results:

• EMPLOYEE (Ssn, Fname, Minit, Lname, Bdate, Address, Sex, Salary)
• DEPARTMENT (Dnumber, Dname)
• PROJECT (Pnumber, Pname, Plocation)

Note: Composite attribute "Name" is decomposed into Fname, Minit, Lname. The underlined attributes are primary keys.

EN: For each weak entity type W with owner entity type E:

• Create a relation R and include all simple attributes of W as attributes of R
• Include the primary key of the owner entity E as a foreign key in R
• The primary key of R is the combination of:
  • The primary key of the owner entity (as FK)
  • The partial key (discriminator) of the weak entity

EN: Weak Entity: DEPENDENT (depends on EMPLOYEE)

Result:

• DEPENDENT (Essn, Dependent_name, Sex, Bdate, Relationship)

Where:

• Essn = Primary key of EMPLOYEE (as FK) - renamed from Ssn
• Dependent_name = Partial key of DEPENDENT
• Primary Key = {Essn, Dependent_name} (combination)

EN: For each binary 1:1 relationship type:

1. Identify relations S and T that correspond to the participating entity types
2. Choose one relation (say S) and include the primary key of T as a foreign key in S
3. It is better to choose S as the entity type with TOTAL participation (to minimize NULL values)
4. Include all simple attributes of the 1:1 relationship as attributes of S

EN: Binary 1:1 Relationship: MANAGES (between EMPLOYEE and DEPARTMENT)

Result:

• DEPARTMENT (Dnumber, Dname, Mgr_ssn, Mgr_start_date)

Why DEPARTMENT?

• DEPARTMENT has total participation (every department has a manager)
• Mgr_ssn = FK referencing EMPLOYEE(Ssn)
• Mgr_start_date = Relationship attribute

EN: For each binary 1:N relationship type:

1. Identify relation S that represents the entity type at the N-side
2. Include as foreign key in S the primary key of relation T (the 1-side entity)
3. Include any simple attributes of the 1:N relationship as attributes of S

Key Rule: FK goes to the N-side (many side)!

EN: Binary 1:N relationships: WORKS_FOR, CONTROLS, SUPERVISION

Results:

• WORKS_FOR (N:1): EMPLOYEE (Ssn, ..., Dno)
  → Dno is FK referencing DEPARTMENT(Dnumber)
• CONTROLS (1:N): PROJECT (Pnumber, ..., Dnum)
  → Dnum is FK referencing DEPARTMENT(Dnumber)
• SUPERVISION (1:N Recursive): EMPLOYEE (Ssn, ..., Super_ssn)
  → Super_ssn is FK referencing EMPLOYEE(Ssn) - same table!

EN: For each binary M:N relationship type:

1. Create a NEW relation S to represent the relationship
2. Include as foreign keys the primary keys of BOTH participating entity relations
3. The combination of these foreign keys forms the PRIMARY KEY of S
4. Include any simple attributes of the M:N relationship as attributes of S

M:N relationships ALWAYS create a new table!

EN: Binary M:N Relationship: WORKS_ON (EMPLOYEE works on PROJECT)

Result:

• WORKS_ON (Essn, Pno, Hours)

Where:

• Essn = FK referencing EMPLOYEE(Ssn)
• Pno = FK referencing PROJECT(Pnumber)
• Primary Key = {Essn, Pno} (combination of both FKs)
• Hours = Relationship attribute

EN: For each multi-valued attribute A:

1. Create a NEW relation R
2. Include an attribute corresponding to A
3. Include the primary key K of the entity that has A as a foreign key
4. The primary key of R = {A, K} (combination)
5. If A is composite, include its simple components

EN: Multi-valued Attribute: Locations (of DEPARTMENT)

Result:

• DEPT_LOCATIONS (Dnumber, Dlocation)

Where:

• Dnumber = FK referencing DEPARTMENT(Dnumber)
• Dlocation = The multi-valued attribute value
• Primary Key = {Dnumber, Dlocation}

EN: For each n-ary relationship type (where n > 2):

1. Create a NEW relation S to represent the relationship
2. Include as foreign keys the primary keys of ALL n participating entity relations
3. The combination of all foreign keys forms the PRIMARY KEY of S
4. Include any simple attributes of the n-ary relationship

Example: A ternary relationship SUPPLY(Supplier, Part, Project) would create a table with 3 FKs.

Definition: A functional dependency X → Y means that the value of attribute set X uniquely determines the value of attribute set Y.

Formal Definition: X → Y holds if and only if whenever two tuples t1 and t2 have t1[X] = t2[X], then they must also have t1[Y] = t2[Y].

Notation:

• X → Y: X functionally determines Y (or Y is functionally dependent on X)
• X is called the determinant (left-hand side, LHS)
• Y is called the dependent (right-hand side, RHS)

Trivial FD: X → Y where Y ⊆ X (the dependent is a subset of the determinant)

Example: {Ssn, Ename} → Ssn is trivial.

Non-trivial FD: X → Y where Y ⊄ X (the dependent is not entirely contained in the determinant)

Example: Ssn → Ename is non-trivial.

Completely Non-trivial FD: X → Y where X ∩ Y = ∅ (no overlap between determinant and dependent)

Full Functional Dependency: Y is fully functionally dependent on X if:

• X → Y, AND
• Removing any attribute from X breaks the dependency

Partial Functional Dependency: Y is partially dependent on X if:

• X → Y, AND
• Some proper subset of X can still determine Y

Definition: Z is transitively dependent on X if:

• X → Y (X determines Y)
• Y → Z (Y determines Z)
• Y ↛ X (Y does not determine X)
• Therefore: X → Z (through Y)

The dependency goes through an intermediate attribute Y that is not a superkey.

Armstrong's rules are sound (only derive correct FDs) and complete (can derive all FDs that hold).

Primary Rules (RAT):

• IR1 - Reflexive Rule: If Y ⊆ X, then X → Y
• IR2 - Augmentation Rule: If X → Y, then XZ → YZ (for any Z)
• IR3 - Transitive Rule: If X → Y and Y → Z, then X → Z

Secondary Rules (derived from RAT):

• IR4 - Decomposition (Splitting): If X → YZ, then X → Y and X → Z
• IR5 - Union (Combining): If X → Y and X → Z, then X → YZ
• IR6 - Pseudo-transitive: If X → Y and WY → Z, then WX → Z

Definition: A relation is in 1NF if and only if:

• All attributes contain only atomic (indivisible) values
• No repeating groups or arrays
• Each row is unique (has a primary key)

Violations:

• Multi-valued attributes (e.g., multiple phone numbers in one cell)
• Composite attributes stored as single values
• Repeating groups (e.g., Item1, Item2, Item3 columns)

Definition: A relation is in 2NF if and only if:

• It is in 1NF, AND
• No partial dependencies: Every non-prime attribute is fully functionally dependent on the entire primary key

Key Terms:

• Prime attribute: An attribute that is part of any candidate key
• Non-prime attribute: An attribute that is not part of any candidate key
• Partial dependency: A non-prime attribute depends on only part of the primary key

Note: 2NF issues only occur when the primary key is composite (multiple attributes).

Definition: A relation is in 3NF if and only if for every non-trivial FD X → Y:

• X is a superkey, OR
• Y is a prime attribute (part of some candidate key)

Alternative Definition: A relation is in 3NF if:

• It is in 2NF, AND
• No transitive dependencies: No non-prime attribute depends on another non-prime attribute

Normal Form	Requirement	Eliminates
1NF	Atomic values only	Repeating groups
2NF	1NF + No partial dependencies	Partial dependencies
3NF	2NF + No transitive dependencies (or RHS is prime)	Transitive dependencies

The CREATE TABLE statement is used to create a new table in the database.

Syntax:

CREATE TABLE employee (
    emp_id      NUMBER(4),
    emp_name    VARCHAR2(30),
    hire_date   DATE,
    salary      NUMBER(8,2)
);

Data Type	Description
VARCHAR2(n)	Variable-length character data (up to n characters)
CHAR(n)	Fixed-length character data (exactly n characters)
NUMBER(p,s)	Numeric data with precision p and scale s
DATE	Date and time values

The PRIMARY KEY constraint uniquely identifies each row in a table. It must contain unique values and cannot contain NULL values.

Column-level syntax:

Table-level syntax:

-- Column-level PRIMARY KEY
CREATE TABLE department (
    dept_id NUMBER(4) PRIMARY KEY,
    dept_name VARCHAR2(30)
);

-- Table-level PRIMARY KEY
CREATE TABLE department (
    dept_id NUMBER(4),
    dept_name VARCHAR2(30),
    PRIMARY KEY (dept_id)
);

The FOREIGN KEY constraint establishes a relationship between two tables. It references the PRIMARY KEY of another table.

Syntax:

A FOREIGN KEY constraint enforces referential integrity: you cannot insert a value that does not exist in the parent table.

CREATE TABLE employee (
    emp_id NUMBER(4) PRIMARY KEY,
    emp_name VARCHAR2(30),
    dept_id NUMBER(4),
    FOREIGN KEY (dept_id) REFERENCES department(dept_id)
);

The INSERT statement adds new rows to a table.

Syntax:

Rules:

• Character and date values must be enclosed in single quotes
• Column list is optional if values are provided for all columns in order

INSERT INTO department (dept_id, dept_name)
VALUES (10, 'Accounting');

INSERT INTO employee
VALUES (101, 'John Smith', '15-JAN-2020', 5000);

There are two methods to insert NULL values:

• Implicit method: Omit the column from the column list
• Explicit method: Specify NULL in the VALUES list

-- Implicit: omit commission column
INSERT INTO employee (emp_id, emp_name, salary)
VALUES (102, 'Jane Doe', 4500);

-- Explicit: specify NULL
INSERT INTO employee (emp_id, emp_name, salary, commission)
VALUES (103, 'Bob Wilson', 4000, NULL);

The UPDATE statement modifies existing rows in a table.

Syntax:

Important: Without a WHERE clause, ALL rows in the table will be updated!

-- Update specific employee's salary
UPDATE employee
SET salary = 5500
WHERE emp_id = 101;

-- Update multiple columns
UPDATE employee
SET salary = 6000, dept_id = 20
WHERE emp_id = 102;

The DELETE statement removes rows from a table.

Syntax:

Important: Without a WHERE clause, ALL rows will be deleted!

Integrity Constraint Error: You cannot delete a row that is referenced by a FOREIGN KEY in another table.

-- Delete specific employee
DELETE FROM employee
WHERE emp_id = 103;

-- Delete all employees in department 10
DELETE FROM employee
WHERE dept_id = 10;

When performing DML operations, you may encounter integrity constraint violations:

• INSERT: Cannot insert a FOREIGN KEY value that doesn't exist in the parent table
• UPDATE: Cannot update a PRIMARY KEY value if it's referenced by a FOREIGN KEY
• DELETE: Cannot delete a row if its PRIMARY KEY is referenced by a FOREIGN KEY in a child table

A Functional Dependency (FD) is a constraint between two sets of attributes in a relation schema.

If X and Y are two sets of attributes in the same relation schema R, then X → Y means that X functionally determines Y.

• FD is a property of the meaning or semantics of the attributes
• The FD specifies a restriction on the possible tuples that can form a relation instance r of R

The FD constraint is that for any two tuples t1 and t2 in the relation instance r(R) that have:

This means:

• The values of the Y component of a tuple depend on, or are determined by, the X component
• The values of X uniquely (or functionally) determine the values of Y
• If X → Y holds, then Y is functionally dependent on X

X is termed the left-hand-side (LHS) or determinant

Y is termed the right-hand-side (RHS)

FD1: DNO → DLOC
FD2: DNO → DNAME

Inference Rules combine known facts to produce ("infer") new facts.

There are 6 inference rules (IR1-IR6). IR1-IR3 are called Armstrong's Inference Rules.

These rules are sound (logically correct) and complete (can imply any possible logical FD).

A set of attributes always determines itself or any of its subsets.

Adding the same set of attributes to both the LHS & RHS of a FD results in another valid FD.

FDs are transitive.

IR4: Decomposition Rule

We can remove attributes from the RHS and decompose the FD.

IR5: Additive (Union) Rule

We can union attributes from the RHS and combine FDs into a single FD (reverse of IR4).

IR6: Pseudo Transitive Rule

A variant of IR3.

Definition: Given a set F of functional dependencies on R, the closure of F denoted by F+ is the set of all functional dependencies inferred from F via the inference rules.

To compute F+:

1. Let F+ = F
2. Apply the inference rules repeatedly until no more changes occur in F+

A→B and A→C then A→BC (Rule 5)
A→BC and BC→D then A→D (Rule 3)
A→B and A→D then A→BD (Rule 5)
A→C and A→D then A→CD (Rule 5)
A→B and A→C and A→D then A→BCD (Rule 5)

Given a relation schema R and a set of FDs that hold on R. Let α be a set of attributes in R. Then:

Use: If α+ contains all attributes of R, then α is a candidate key.

Initially, A+ = {A}
From A→B we get A+ = {A, B}
From B→C we get A+ = {A, B, C}
Therefore A+ = {A, B, C} = all attributes of R
So A is a candidate key!

Normalization is a method for organizing data elements in a database into tables to minimize duplication.

Why Normalization?

• Reduce redundant data
• Remove inconsistent data
• Reduce anomalies
• Increase data integrity
• Simplify data maintenance
• Take less disk space

Goal: In each table, all non-key attributes should be dependent on the primary key.

A relation schema is in 1NF if:

• Domains of attributes include only atomic (simple, indivisible) values
• The value of an attribute is a single value from the domain of that attribute

No composite attributes and no multivalued attributes.

A relation schema is in 2NF if for all FDs (α→β), one of the following is satisfied:

1. β ⊆ α (trivial FD), or
2. α is a super key, or
3. Each attribute in β is prime, or
4. α is not a proper subset of a key (no partial dependency)

Key point: Remove partial dependencies to achieve 2NF.

A relation schema is in 3NF if for all FDs (α→β), one of the following is satisfied:

1. β ⊆ α (trivial FD), or
2. α is a super key, or
3. Each attribute in β is prime (part of some candidate key)

Prime attribute: An attribute that is a member of any candidate key.

Nonprime attribute: An attribute that is not a member of any candidate key.

Key point: Remove transitive dependencies to achieve 3NF.

A relation schema is in BCNF if for all FDs (α→β), one of the following is satisfied:

1. β ⊆ α (trivial FD), or
2. α is a super key

BCNF is stricter than 3NF - it removes the third condition about prime attributes.

Decomposition for BCNF:

• R1 = α ∪ β (contains the violating FD)
• R2 = R - β (remaining attributes)

1. 1NF: Remove repeating groups and multivalued attributes
2. 2NF: Remove partial dependencies
3. 3NF: Remove transitive dependencies
4. BCNF: Every determinant must be a super key

When a relation satisfies 3NF:

• Partial dependencies are removed
• Transitive dependencies are removed
• All attributes are dependent on the primary key
• Tables are small and well-formed