Every relation exists in two dimensions: horizontally across its attributes and vertically down its tuples. These dimensions have precise names and profound implications for database design, query performance, and system capacity.

The degree of a relation refers to its width—the number of attributes it contains. The cardinality refers to its depth—the number of tuples it holds. Together, these measures characterize the structural properties of any relation.

Understanding degree and cardinality is essential for:

• Estimating storage requirements
• Analyzing query complexity
• Designing efficient schemas
• Evaluating join costs
• Making normalization decisions

In this page, we explore these fundamental concepts with mathematical precision and practical insight, establishing the vocabulary and understanding that database professionals rely upon.

Definition (Degree of a Relation):

The degree (also called arity) of a relation R is the number of attributes in its schema. If R has schema R(A₁, A₂, ..., Aₙ), then the degree of R is n.

Notation:

• degree(R) = n
• |schema(R)| = n
• R is an "n-ary relation" (unary, binary, ternary, etc.)

Examples:

Properties of Degree:

1. Degree is fixed by the schema. Once defined, a relation's degree doesn't change with data—it changes only with schema evolution (ALTER TABLE ADD COLUMN).

2. Degree ≥ 1. A relation with zero attributes is called a nullary relation. It can have at most one tuple (the empty tuple). This is a degenerate case rarely encountered.

3. Degree affects storage. More attributes generally mean more bytes per tuple, though compression and null handling complicate this.

4. Degree affects query complexity. Joining on more attributes, selecting more columns, and processing wider rows all increase query costs.

Definition (Cardinality of a Relation):

The cardinality of a relation R is the number of tuples it contains. Since a relation is a set, cardinality equals the set's size.

Notation:

• |R| = number of tuples in R
• card(R) = cardinality of R
• n(R) = count of R

Examples:

Properties of Cardinality:

1. Cardinality varies with data. Unlike degree, cardinality changes as data is added or removed. Schema doesn't constrain cardinality (except through application logic).

2. Cardinality ≥ 0. An empty relation (with no tuples) is perfectly valid. It represents no facts matching the predicate.

3. Cardinality directly affects performance. Query time often scales with cardinality—scanning 1 million rows takes longer than scanning 1 thousand.

4. Maximum cardinality is bounded by domains. The maximum possible cardinality is the product of domain sizes: |dom(A₁)| × |dom(A₂)| × ... × |dom(Aₙ)|. For infinite domains (like integers or strings), this is unbounded.

5. Cardinality statistics drive optimization. Query optimizers maintain cardinality estimates for tables and use them to choose efficient execution plans.

When we represent relations as tables, degree and cardinality correspond directly to the table's visual dimensions:

• Degree = Number of columns
• Cardinality = Number of rows

This intuitive mapping makes it easy to think about relation structure visually.

Dimensional Analysis:

We can think of a relation as a matrix-like structure with:

• degree(R) columns
• |R| rows
• degree(R) × |R| "cells" (individual values)

For the Employee relation above:

• degree = 4 (ID, Name, Dept, Salary)
• cardinality = 5 (five employees)
• total cells = 20

Column Operations:

Operations that change degree:

• Projection (π): Reduces degree by selecting a subset of attributes
• Cartesian Product (×): Increases degree by combining attributes from two relations
• Natural Join (⋈): May reduce or preserve degree depending on shared attributes

Row Operations:

Operations that change cardinality:

• Selection (σ): Reduces cardinality by filtering tuples
• Union (∪): Increases cardinality by combining tuples from two relations
• Cartesian Product (×): Multiplies cardinalities
• Join: Cardinality depends on matching tuples

Query optimization is fundamentally about choosing the most efficient execution plan. Cardinality estimation—predicting how many tuples flow through each operation—is the cornerstone of this process.

Why Estimation Matters:

Consider joining three tables: A, B, and C.

• Order 1: (A ⋈ B) ⋈ C
• Order 2: (A ⋈ C) ⋈ B
• Order 3: (B ⋈ C) ⋈ A

The costs can differ by orders of magnitude depending on which intermediate results are smallest. If |A ⋈ B| = 1000 and |B ⋈ C| = 10,000,000, we want to compute A ⋈ B first.

How Databases Estimate Cardinality:

Selection Cardinality Formula:

For a selection σ_{condition}(R), the estimated cardinality is:

|σ_{condition}(R)| ≈ |R| × selectivity(condition)

Where selectivity is the fraction of tuples satisfying the condition:

• Equality on key: selectivity = 1/|R| (one match)
• Equality on non-key with NDV distinct values: selectivity ≈ 1/NDV
• Range condition: depends on distribution (uniform assumption or histogram)

Join Cardinality Formula:

For a join R ⋈ S with join attribute having NDV(R) and NDV(S) distinct values:

|R ⋈ S| ≈ (|R| × |S|) / max(NDV(R.attr), NDV(S.attr))

This assumes uniform distribution and referential integrity. Real queries may deviate significantly.

Degree and cardinality directly impact storage requirements. Understanding this relationship helps in capacity planning and schema design.

Storage Size Formula (Simplified):

Storage ≈ cardinality × average_tuple_size
        ≈ cardinality × Σ(attribute_sizes)
        ≈ |R| × Σᵢ(size(Aᵢ))

For instance:

• Employee table with 100,000 employees
• Attributes: ID (4 bytes), Name (50 bytes), Dept (20 bytes), Salary (8 bytes)
• Average tuple size ≈ 82 bytes
• Total storage ≈ 100,000 × 82 = 8.2 MB (before indexes and overhead)

Degree Considerations for Schema Design:

1. Wide tables (high degree):

   • More data per row—may exceed page size limits
   • Slower full-table scans (more data to read per row)
   • Advantage for queries needing many columns (one seek per row)
   • Column-family stores may be more efficient

2. Narrow tables (low degree):

   • More tables needed to represent same data (normalization)
   • Joins required to reconstruct complete entity
   • Faster scans when few columns needed
   • Better suited to row-oriented storage

Cardinality Considerations:

1. Large cardinality (millions+):

   • Indexing becomes essential for point queries
   • Full table scans become expensive
   • Partitioning may be necessary
   • Memory for caching becomes critical

2. Small cardinality (hundreds/thousands):

   • Full scans are cheap—indexes may not help
   • Entire table may fit in cache
   • Lookup joins are efficient

When analyzing relational operations, understanding the bounds on result cardinality helps validate query logic and estimate performance.

Minimum Cardinality:

The smallest possible size of an operation's result.

For common operations:

• Selection σ(R): min = 0 (no tuples satisfy the predicate)
• Projection π(R): min = 1 (all tuples project to the same values)
• Union R ∪ S: min = max(|R|, |S|) (when one is a subset of the other)
• Intersection R ∩ S: min = 0 (disjoint relations)
• Difference R − S: min = 0 (S contains all of R)
• Cartesian Product R × S: min = 0 (if either operand is empty)
• Natural Join R ⋈ S: min = 0 (no matching tuples)

Maximum Cardinality:

The largest possible size of an operation's result.

Practical Application:

Knowing cardinality bounds helps:

1. Debugging Queries: If a join returns way more rows than expected, it might be performing a Cartesian product (missing join condition). If |R ⋈ S| ≈ |R| × |S|, the join condition is probably ineffective.

2. Validating Results: If selection returns 0 rows but you expected some, either the data doesn't match or the predicate is wrong.

3. Capacity Planning: Maximum cardinality gives worst-case storage needs. A report aggregating from a 1B-row table should not produce 1B rows (if it might, there's a design issue).

4. Query Optimization: Pushing down selections (reducing cardinality early) exploits the fact that smaller cardinality means faster subsequent operations.

Normalization—the process of organizing relations to reduce redundancy—has direct effects on degree and cardinality. Understanding this relationship illuminates the tradeoffs in database design.

Effect of Normalization on Degree:

When you normalize a relation (decompose it into smaller relations):

• Individual relation degrees decrease (fewer attributes per table)
• Total number of relations increases
• More joins are required to reconstruct the original data

Example: Decomposing an Unnormalized Relation:

Cardinality Changes with Normalization:

Normalization typically:

• Reduces cardinality in tables containing repeated data (employee info no longer duplicated)
• Creates new tables for relationships (Assignment table)
• May increase total rows across all tables (but reduces total storage due to less redundancy)

The Tradeoff:

Rule of Thumb:

• OLTP (transactional) systems favor normalization (frequent updates, data integrity)
• OLAP (analytical) systems favor denormalization (complex reads, few updates)

We have thoroughly explored degree and cardinality—the fundamental dimensions that characterize every relation. Let's consolidate the essential understanding:

What's Next:

Having understood the structure and dimensions of tuples and relations, we'll now explore tuple operations—the fundamental operations that create, retrieve, update, and delete tuples. This completes our understanding of tuples as both data structures and units of manipulation.