Data Modeling - Entity-Relationship Diagrams, Relational Model, Constraints, Relational Algebra, Relational Calculus, Codd Rules

1. Introduction to Data Modeling

Data modeling is the process of creating a visual representation of an entire database or of the data requirements for a particular application. It serves as a blueprint for database design, helping to define the structure, relationships, and constraints of the data. Effective data modeling ensures that the database accurately reflects the real-world entities and their interactions, leading to efficient storage, retrieval, and management of information. It bridges the gap between business requirements and the technical implementation of a database.

The primary goals of data modeling are:

• To understand the data requirements of the users and the business.
• To define the structure and relationships between different pieces of data.
• To ensure data integrity and consistency.
• To facilitate communication among stakeholders (designers, developers, business analysts).
• To provide a basis for database design and implementation.

2. Entity-Relationship Diagrams (ERDs)

Entity-Relationship Diagrams (ERDs) are a fundamental tool for conceptual data modeling. They represent the structure of data in a graphical way, showing entities, their attributes, and the relationships between them. ERDs are widely used to design databases because they are intuitive and easy to understand.

2.1 Entities

An entity is a real-world object or concept that can be uniquely identified and has distinct properties. In a database context, an entity typically corresponds to a table. Examples include 'Student', 'Course', 'Employee', 'Department', 'Product', 'Order'.

2.2 Attributes

Attributes are properties or characteristics of an entity. They represent the data that will be stored about each entity instance. For example, a 'Student' entity might have attributes like 'StudentID', 'Name', 'Address', 'DateOfBirth'.

Attributes can be classified as:

• Simple Attributes: Cannot be further divided (e.g., 'Age').
• Composite Attributes: Can be divided into smaller parts (e.g., 'Address' can be divided into 'Street', 'City', 'State', 'ZipCode').
• Single-Valued Attributes: Have only one value for a given entity instance (e.g., 'StudentID').
• Multi-Valued Attributes: Can have multiple values for a given entity instance (e.g., 'PhoneNumber' for a person, as they might have a home, work, and mobile number).
• Derived Attributes: Can be calculated or derived from other attributes (e.g., 'Age' can be derived from 'DateOfBirth').
• Key Attributes: Attributes that uniquely identify an entity instance. These are often underlined in ERDs.

2.3 Relationships

A relationship represents an association between two or more entities. For example, a 'Student' entity might be related to a 'Course' entity through a 'Enrolls In' relationship.

2.4 Cardinality Ratios

Cardinality ratios define the number of instances of one entity that can be related to the number of instances of another entity. The common ratios are:

• One-to-One (1:1): Each instance of Entity A relates to at most one instance of Entity B, and vice versa. Example: A 'Person' is married to at most one 'Spouse', and a 'Spouse' is married to at most one 'Person'.
• One-to-Many (1:N): Each instance of Entity A can relate to many instances of Entity B, but each instance of Entity B relates to at most one instance of Entity A. Example: One 'Department' can have many 'Employees', but each 'Employee' belongs to only one 'Department'.
• Many-to-One (N:1): Each instance of Entity A can relate to at most one instance of Entity B, but each instance of Entity B can relate to many instances of Entity A. This is the inverse of One-to-Many. Example: Many 'Students' can enroll in one 'Course'.
• Many-to-Many (M:N): Each instance of Entity A can relate to many instances of Entity B, and each instance of Entity B can relate to many instances of Entity A. Example: Many 'Students' can enroll in many 'Courses'.

2.5 Participation Constraints

Participation constraints specify whether an entity instance must participate in a relationship or if participation is optional.

• Total Participation (Mandatory): Every instance of an entity must participate in the relationship. This is often represented by a double line connecting the entity to the relationship.
• Partial Participation (Optional): An entity instance may or may not participate in the relationship. This is represented by a single line.

2.6 ERD Notations

Several notations exist for drawing ERDs, 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. Lines connect entities to relationships, with cardinality indicated by numbers (1, N, M) and participation by single/double lines.
• Crow's Foot Notation: Uses a more streamlined graphical representation. Entities are rectangles. Lines connect entities, and the "crow's foot" symbol indicates "many," while a short line indicates "one." A circle indicates optional participation, and a perpendicular line indicates mandatory participation.

Example: A simple ERD for a university might include entities like 'Student' and 'Course'. A 'Student' has attributes like StudentID, Name. A 'Course' has attributes like CourseID, Title. The relationship is 'Enrolls In', with a many-to-many (M:N) cardinality. A student can enroll in many courses, and a course can have many students. Participation might be optional for both (a student doesn't have to be enrolled, and a course might have no students yet).

3. The Relational Model

The relational model is the most widely used database model. It organizes data into one or more tables (relations) of columns and rows, with a unique key identifying each row. Each table represents an entity type, and each row represents an instance of that entity. The relationships between tables are established through common attributes (foreign keys).

3.1 Relations (Tables)

A relation is a set of tuples (rows). In database terms, it's a table.

• Schema: The structure of a relation, defined by its name and the names of its attributes (columns). Example: `Student(StudentID, Name, Major, GPA)`.
• Tuple: A single record or row in a relation. It's an ordered set of values, one for each attribute. Example: `(101, 'Alice Smith', 'Computer Science', 3.8)`.
• Attribute: A column in a relation. It represents a property of the entity. Example: `StudentID`, `Name`, `Major`, `GPA`.
• Domain: The set of permissible values for an attribute. Example: The domain for `StudentID` might be all positive integers. The domain for `GPA` might be real numbers between 0.0 and 4.0.
• Degree: The number of attributes in a relation.
• Cardinality: The number of tuples (rows) in a relation.

3.2 Keys in the Relational Model

Keys are crucial for uniquely identifying rows and establishing relationships.

• Superkey: A set of one or more attributes that, taken collectively, uniquely identify a tuple in a relation.
• Candidate Key: A minimal superkey (i.e., no proper subset of it is a superkey). A relation can have multiple candidate keys.
• Primary Key: A candidate key that is chosen by the database designer to uniquely identify tuples in a relation. It must be unique and cannot contain null values.
• Foreign Key: An attribute (or set of attributes) in one relation that refers to the primary key of another relation. It enforces referential integrity. Example: In an `Enrollment` table with `StudentID` and `CourseID`, `StudentID` would be a foreign key referencing the `Student` table, and `CourseID` would be a foreign key referencing the `Course` table.
• Composite Key: A key that consists of two or more attributes.
• Alternate Key: Any candidate key that is not chosen as the primary key.

3.3 Relational Integrity Constraints

These rules ensure the accuracy and consistency of data in the relational model.

• Entity Integrity: Ensures that each tuple (row) in a relation is uniquely identifiable. This is achieved by the primary key constraint, which states that the primary key attribute(s) cannot have NULL values.
• Referential Integrity: Ensures that relationships between relations remain consistent. When a foreign key is used, it must either match a valid, existing primary key value in the referenced relation or be NULL (if allowed). Example: You cannot assign an employee to a department that does not exist.
• Domain Integrity: Ensures that values for a given attribute are of the correct type and within the defined domain. For example, an age attribute should only contain positive integers.

4. Relational Algebra

Relational algebra is a procedural query language used to retrieve data from a relational database. It consists of a set of operations that take one or more relations as input and produce a new relation as output. These operations form the foundation for how SQL queries are executed.

4.1 Basic Operations

These are fundamental operations for manipulating relations.

• Select (σ): Retrieves tuples (rows) from a relation that satisfy a specified condition. It filters rows.

  Syntax: σcondition(Relation)

  Example: σGPA > 3.5(Student) - Selects all students with a GPA greater than 3.5.

• Project (π): Retrieves specified columns (attributes) from a relation, removing duplicate rows. It selects columns.

  Syntax: πattribute_list(Relation)

  Example: πName, Major(Student) - Selects the Name and Major of all students, removing duplicate pairs.

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

  Syntax: Relation1 ∪ Relation2

  Example: Combining lists of undergraduate and graduate students if they share the same structure.

• Set Difference (−): Returns tuples that are in the first relation but not in the second. Both relations must have the same schema.

  Syntax: Relation1 − Relation2

  Example: Finding students who are enrolled in 'CS101' but not in 'CS202'.

• Cartesian Product (×): Combines each tuple from the first relation with each tuple from the second relation. The result has attributes from both relations.

  Syntax: Relation1 × Relation2

  Example: If `Students` has 100 tuples and `Courses` has 10 tuples, the Cartesian Product will have 1000 tuples.

• Rename (ρ): Renames a relation or an attribute. Useful for clarity or when performing operations on the same relation multiple times.

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

  Example: ρS(Student) renames the Student relation to S. ρStudentID / ssn(Student) renames the ssn attribute to StudentID.

4.2 Derived Operations

These operations can be expressed in terms of the basic operations.

• Intersection (∩): Returns tuples that are present in both relations. It can be expressed as `Relation1 ∩ Relation2 = Relation1 − (Relation1 − Relation2)`.
• Join (⋈): Combines tuples from two relations based on a related attribute.
  • Natural Join: Joins two relations on all attributes that have the same name in both relations. Duplicate attributes are removed.

    Example: `Student ⋈ Enrollment` would join based on any common attributes like `StudentID` and `CourseID` if they exist in both.

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

    Syntax: Relation1 ⋈condition Relation2

    Example: `Student ⋈<sub>Student.StudentID = Enrollment.StudentID</sub> Enrollment` joins students and enrollments where the student IDs match.

  • 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, filling missing attributes with NULL.
    • Left Outer Join: Includes all tuples from the left relation and matching tuples from the right. Unmatched tuples from the left have NULLs for right-side attributes.
    • Right Outer Join: Includes all tuples from the right relation and matching tuples from the left. Unmatched tuples from the right have NULLs for left-side attributes.
    • Full Outer Join: Includes all tuples from both relations. Unmatched tuples have NULLs for attributes of the other relation.
• Division: Used to find tuples in one relation that are associated with *all* tuples in another relation. It's more complex and less commonly used directly in queries.

5. Relational Calculus

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

5.1 Tuple Relational Calculus (TRC)

TRC uses variables that range over tuples of a relation. Queries are expressed as $\{ t \mid \Phi(t) \}$, meaning "the set of all tuples $t$ such that condition $\Phi(t)$ is true."

• Variables: Represent tuples (e.g., $t, u, v$).
• Attributes: Accessed using dot notation (e.g., $t.Name$, $t.GPA$).
• Quantifiers: Universal quantifier (∀, "for all") and existential quantifier (∃, "there exists").

Example: Find the names of students who have a GPA greater than 3.5.
{ t.Name | t ∈ Student ∧ t.GPA > 3.5 }

Example: Find the names of students who are enrolled in the 'Database Systems' course.
{ t1.Name | t1 ∈ Student ∧ ∃ t2 ∈ Enrollment (t1.StudentID = t2.StudentID ∧ ∃ t3 ∈ Course (t2.CourseID = t3.CourseID ∧ t3.Title = 'Database Systems')) }
This reads: "The set of names $t1$.Name such that $t1$ is a student AND there exists an enrollment $t2$ such that $t1$'s StudentID matches $t2$'s StudentID AND there exists a course $t3$ such that $t2$'s CourseID matches $t3$'s CourseID AND $t3$'s Title is 'Database Systems'."

5.2 Domain Relational Calculus (DRC)

DRC uses variables that range over the domains of attributes. Queries are expressed as $\{ \vec{x} \mid \Phi(\vec{x}) \}$, where $\vec{x}$ is a tuple of variables.

• Variables: Represent values from attribute domains (e.g., $s\_id, s\_name, gpa$).
• Predicates: Refer to relations and their attributes (e.g., $Student(s\_id, s\_name, \dots)$).
• Quantifiers: Similar to TRC (∀, ∃).

Example: Find the names of students who have a GPA greater than 3.5.
{ s\_name | ∃ s\_id, major, gpa (Student(s\_id, s\_name, major, gpa) ∧ gpa > 3.5) }

Relational calculus is theoretically equivalent to relational algebra, meaning any query expressible in one can be expressed in the other. It forms the basis for understanding the expressive power of database query languages.

6. Codd's 12 Rules (and more)

Edgar F. Codd, the inventor of the relational model, proposed a set of rules to define what constitutes a "relational database management system" (RDBMS). Originally 12 rules, they have since been expanded. These rules ensure that a system truly adheres to the relational principles.

6.1 The Original 12 Rules

1. Information Rule: All information in a relational database must be stored logically as values in relations (tables). No hidden data structures. 2. Guaranteed Access Rule: Every distinct atomic value in the database must be addressable using a combination of the relation name, primary key value, and attribute name. (Primary keys must be unique and non-null). 3. Systematic Treatment of NULL Values: The system must support a null value (distinct from any regular value) that represents missing or inapplicable information, and it must be systematically recognized by the system as incomplete. 4. Dynamic Relational Catalog Based on the Relational Model: The database must have a relational catalog (data dictionary) that stores information about the database structure (tables, columns, constraints). This catalog itself must be stored as relations and be accessible to authorized users. 5. Comprehensive Data Sublanguage Rule: The system must support at least one relational language that is comprehensive enough for data definition, data manipulation, and transaction control. This language must be usable interactively and within application programs. (This is where SQL comes in). 6. View Updating Rule: The system must be able to update any view that is theoretically updatable. A view is updatable if the database can uniquely determine the effect of the update on the base tables. 7. High-Level Insert, Update, and Delete: The system must support set-at-a-time operations for inserting, updating, and deleting data. This means you should be able to operate on multiple rows with a single command. 8. Physical Data Independence: Application programs and terminal activities remain unchanged when the internal representations or access methods are changed. (e.g., changing from a B-tree index to a hash index). 9. Logical Data Independence: Application programs and terminal activities remain unchanged when changes are made to the base tables that preserve the logical data (e.g., adding a new column to a table). Views help achieve this. 10. Integrity Independence: All integrity constraints (entity, referential, domain) must be definable in the relational language and stored in the system's catalog. They must be enforced by the RDBMS, not just by application programs. 11. Distribution Independence: Application programs written for a centralized system must work without modification when the system is distributed. 12. Nonsubversion Rule: If the system supports a low-level (single-record-at-a-time) access, that mechanism must not be able to subvert or bypass the integrity constraints and rules defined in the system.

6.2 Beyond the 12 Rules

While Codd's 12 rules are foundational, modern RDBMSs often go beyond them. Additional concepts considered important include:

• Transaction ACID Properties: Atomicity, Consistency, Isolation, Durability are critical for reliable transaction processing.
• Concurrency Control: Mechanisms to manage simultaneous access to data by multiple users without compromising data integrity.
• Security Features: Robust authentication and authorization mechanisms.
• Performance Optimization: Features like indexing, query optimization, caching.