Data Modeling: ER Diagrams, Relational Model, Relational Algebra and Calculus, Constraints and Codd Rules

1. Introduction to Data Modeling

Data modeling is the process of creating a visual representation of an entire system's data or the information used by a process. It helps in understanding the relationships between different data elements, their attributes, and how they interact. A good data model is crucial for designing efficient, scalable, and maintainable database systems. It acts as a blueprint, ensuring that all stakeholders have a common understanding of the data requirements.

The primary goals of data modeling include:

• Identifying and defining data entities.
• Establishing relationships between entities.
• Specifying attributes of entities.
• Ensuring data integrity and consistency.
• Facilitating communication between designers, developers, and users.

2. Entity-Relationship (ER) Diagrams

Entity-Relationship (ER) diagrams are a high-level conceptual data model used to represent the structure of a database. They are graphically based and consist of entities, attributes, and relationships. ER diagrams are particularly useful during the initial design phase to capture the business requirements and the overall structure of the data.

2.1 Entities

An entity is a real-world object or concept that can be distinctly identified. In a database context, an entity typically represents a table. For example, in a university database, 'Student', 'Course', and 'Professor' can be considered entities.

2.2 Attributes

An attribute is a property or characteristic of an entity. For example, for the 'Student' entity, attributes could be 'StudentID', 'Name', 'Address', and 'DateOfBirth'. Attributes are represented as ovals connected to the entity they describe.

Attributes can be classified into different types:

• Single-valued attributes: Attributes that can have only one value for a given entity instance (e.g., 'StudentID').
• Multi-valued attributes: Attributes that can have multiple values for a given entity instance (e.g., 'Phone Numbers' for a 'Customer').
• Derived attributes: Attributes whose values can be calculated from other attributes (e.g., 'Age' can be derived from 'DateOfBirth').
• Composite attributes: Attributes that can be divided into smaller sub-parts (e.g., 'Address' can be composed of 'Street', 'City', 'State', 'ZipCode').

2.3 Relationships

A relationship represents an association between two or more entities. For example, a 'Professor' 'Teaches' a 'Course'. Relationships are represented as diamonds connecting the related entities.

Relationships are characterized by their cardinality, which defines the number of instances of one entity that can be associated with instances of another entity.

• One-to-One (1:1): Each instance of Entity A is associated with at most one instance of Entity B, and vice versa. Example: A 'Person' has one 'Passport'.
• One-to-Many (1:N): Each instance of Entity A can be associated with many instances of Entity B, but each instance of Entity B is associated with at most one instance of Entity A. Example: A 'Department' has many 'Employees'.
• Many-to-One (N:1): Each instance of Entity A can be associated with at most one instance of Entity B, but each instance of Entity B can be associated with many instances of Entity A. Example: Many 'Students' enroll in one 'Course'.
• Many-to-Many (M:N): Each instance of Entity A can be associated with many instances of Entity B, and each instance of Entity B can be associated with many instances of Entity A. Example: Many 'Students' enroll in many 'Courses'.

2.4 ER Diagram Notations

Several notations exist for ER diagrams, with Chen notation and Crow's Foot notation being the most common.

• Chen Notation: Entities are represented by rectangles, attributes by ovals, and relationships by diamonds. Cardinality is indicated by numbers (1, N, M) near the connecting lines.
• Crow's Foot Notation: Entities are represented by rectangles. Relationships are shown as lines connecting entities, with symbols at the ends indicating cardinality. A circle represents zero, a dash represents one, and a crow's foot symbol represents many.

2.5 Weak Entities

A weak entity is an entity that cannot be uniquely identified by its own attributes alone. It relies on a relationship with another entity (called the owner or identifying entity) for its existence and identification. A weak entity has a partial key, which is an attribute that, combined with the primary key of the owner entity, uniquely identifies an instance of the weak entity. Weak entities are typically represented by a double rectangle in ER diagrams, and the identifying relationship by a double diamond.

3. The Relational Model

The relational model is the most widely used data model for database systems. It organizes data into one or more tables (relations) of columns and rows, with a unique key identifying each row. Data is represented as a collection of relations.

3.1 Relations (Tables)

A relation is a two-dimensional table consisting of rows and columns.

• Tuples (Rows): Each row in a relation represents a single record or instance of an entity.
• Attributes (Columns): Each column represents a characteristic or property of the entity.
• Domain: The set of permissible values for an attribute. For example, the domain for 'Age' might be integers from 18 to 100.
• Degree: The number of attributes in a relation.
• Cardinality: The number of tuples (rows) in a relation.

3.2 Keys

Keys are attributes or sets of attributes that are used to uniquely identify tuples within a relation or to establish relationships between relations.

• Superkey: A set of one or more attributes that, taken collectively, uniquely identify a tuple.
• Candidate Key: A minimal superkey; that is, a superkey such that no proper subset of it is also a superkey.
• Primary Key: One of the candidate keys chosen by the database designer to uniquely identify tuples in a relation. It must be unique and non-null.
• Alternate Key: Any candidate key that is not chosen as the primary key.
• Foreign Key: An attribute (or set of attributes) in one relation that refers to the primary key of another relation. It enforces referential integrity.

3.3 Constraints

Constraints are rules that enforce data integrity and consistency within the database.

• Domain Constraints: Ensure that values for an attribute are from its defined domain.
• Key Constraints: Ensure that primary keys are unique and non-null.
• Referential Integrity Constraints: Enforced by foreign keys, ensuring that relationships between tables are valid. A foreign key value must either match a primary key value in the referenced table or be null (unless specified otherwise).
• Entity Integrity Constraints: Ensure that all primary key values are unique and not null.

4. Relational Algebra

Relational algebra is a procedural query language that consists of a set of operations used to retrieve data from relational databases. It defines how to manipulate relations to produce new relations. The operands for these operations are relations, and the results are also relations.

4.1 Fundamental Operations

These operations form the basis of relational algebra.

• Select (σ): Selects tuples (rows) that satisfy a given condition.

  Syntax: σcondition(RelationName)

  Example: σSalary > 50000(Employee) - Retrieves all employees with a salary greater than 50000.

• Project (π): Selects columns (attributes) from a relation and removes duplicate rows.

  Syntax: πAttributeList(RelationName)

  Example: πName, Salary(Employee) - Retrieves the names and salaries of all employees.

• Union (∪): Combines tuples from two relations that have the same attributes and compatible domains. Duplicate tuples are removed.

  Syntax: Relation1 ∪ Relation2

  Requirement: Both relations must have the same number of attributes, and corresponding attributes must have compatible domains.

• Set Difference (−): Returns tuples that are in the first relation but not in the second.

  Syntax: Relation1 - Relation2

  Requirement: Same as Union.

• Cartesian Product (×): Combines every tuple of the first relation with every tuple of the second relation.

  Syntax: Relation1 × Relation2

  Example: If Relation1 has 'n' tuples and Relation2 has 'm' tuples, the result will have 'n*m' tuples.

• Rename (ρ): Renames a relation or an attribute.

  Syntax: ρNewName(RelationName) or ρNewAttributeName/OldAttributeName(RelationName)

4.2 Set Operations

These operations treat relations as sets of tuples.

• Intersection (∩): Returns tuples that are common to both relations.

  Syntax: Relation1 ∩ Relation2

  Note: A ∩ B is equivalent to (A ∪ B) - (A - B).

4.3 Join Operations

Joins combine tuples from two relations based on a related attribute.

• Natural Join (⋈): Combines two relations based on common attributes. It performs a Cartesian product and then selects tuples where the common attributes have equal values. Duplicate common attributes are eliminated in the result.

  Syntax: Relation1 ⋈ Relation2

  Example: Employee ⋈ Department - Joins Employee and Department tables on common attributes like 'DeptID'.

• Theta Join (⋈_θ): A generalized join operation that combines tuples based on a specified condition (θ). It's a Cartesian product followed by a select operation.

  Syntax: Relation1 ⋈condition Relation2

• Equi Join: A Theta Join where the condition involves only equality comparisons.
• Outer Join: Includes tuples that do not have a match in the other relation, along with the matched tuples.
  • Left Outer Join (⟕): Includes all tuples from the left relation and matching tuples from the right. Unmatched tuples from the right are filled with nulls.
  • Right Outer Join (⟖): Includes all tuples from the right relation and matching tuples from the left. Unmatched tuples from the left are filled with nulls.
  • Full Outer Join (⟗): Includes all tuples from both relations. Unmatched tuples are filled with nulls.

4.4 Division (÷)

Division is used to find tuples in one relation that are associated with *all* tuples in another relation. It's often used for queries like "Find all students who have taken all courses".

Syntax: R1 ÷ R2

If R1 has attributes (A, B) and R2 has attribute (B), then R1 ÷ R2 will have attribute (A). A tuple 'a' will be in the result if for every tuple 'b' in R2, the tuple (a, b) exists in R1.

5. Relational Calculus

Relational calculus is a non-procedural (declarative) query language for the relational model. Unlike relational algebra, it describes *what* data to retrieve, not *how* to retrieve it. There are two main types: Tuple Relational Calculus (TRC) and Domain Relational Calculus (DRC).

5.1 Tuple Relational Calculus (TRC)

TRC uses tuple variables (ranging over relations) and quantifiers (∀ for all, ∃ for exists) to express queries. A query is a set of tuples { t | P(t) }, where P(t) is a condition involving tuple variables.

Example: Find the names of employees who earn more than 50000.

{ t.Name | ∃ e ∈ Employee (e.Name = t.Name AND e.Salary > 50000) }

This reads: "The set of all t.Name such that there exists an employee 'e' where e.Name is t.Name and e.Salary is greater than 50000."

5.2 Domain Relational Calculus (DRC)

DRC uses domain variables (ranging over attribute domains) and quantifiers. A query is a set of tuples { (x₁, x₂, ..., x_n) | P(x₁, x₂, ..., x_n) }, where P is a condition involving domain variables.

Example: Find the names of employees who earn more than 50000.

{ (Name) | ∃ E_Name, E_Salary (E_Name ∈ Employee.Name, E_Salary ∈ Employee.Salary AND E_Salary > 50000 AND Name = E_Name) }

This reads: "The set of all Name values such that there exists E_Name and E_Salary from the Employee relation where E_Salary is greater than 50000 and Name is equal to E_Name."

6. Codd's 12 Rules

Edgar F. Codd, the inventor of the relational model, proposed 12 rules that a database management system must follow to be considered truly relational. These rules ensure that the database adheres strictly to the relational model principles.

Rule #	Rule Name	Description
0	Foundational Rule	The system must use its relational capabilities exclusively to manage data.
1	Information Rule	All information in a relational database must be represented explicitly at the logical level and only by values in relations.
2	Guaranteed Access Rule	Every distinct, atomic value in the database must be addressable using a primary key, attribute name (column name), and tuple identifier (row identifier).
3	Systematic Treatment of Null Values	The database must support a null value (distinct from any regular value) that is explicitly represented and systematically ignored by the system.
4	Dynamic Relational Catalog Based on the Relational Model	The database description (catalog) must be stored in relations and be accessible to authorized users. Users should be able to query it using the same language used for data.
5	Comprehensive Data Sublanguage Rule	The system must support at least one relational language that is: Comprehensible High-level Capable of data definition, data manipulation, and transaction management
6	View Updating Rule	The system must be able to update any view that is theoretically updatable.
7	High-Level Insert, Update, and Delete	The system must support set-at-a-time operations for inserting, updating, and deleting data. This means operations should be able to handle multiple rows at once.
8	Physical Data Independence	Application programs and ad hoc query facilities are logically unaffected by changes in the physical storage or access methods.
9	Logical Data Independence	Application programs and ad hoc query facilities are logically unaffected when the data definition that allows the base tables to be changed (e.g., adding a column) is changed.
10	Integrity Independence	All integrity constraints (entity, referential, domain) must be definable in the relational language and stored in the catalog. They must not be stored solely in application programs.
11	Distribution Independence	Application programs written for a distributed database system should logically operate as though the database were centralized.
12	Non-subversion Rule	The system must not contain any mechanism that allows data to be subverted or bypassed (e.g., by writing low-level access routines).