Loading learning content...
Precise notation is the foundation of rigorous analysis. Just as functional dependencies use the single arrow (→) to express determinacy, multivalued dependencies employ a distinct notation system to express independence. Mastering this notation is essential for reading database literature, writing formal specifications, and communicating dependency constraints unambiguously.
The double arrow (→→) is more than a symbol—it encapsulates the tuple-swapping semantics we explored in the previous page. Understanding the notation deeply means understanding what MVDs truly express.
By the end of this page, you will be fluent in MVD notation. You'll understand the double-arrow symbol, know multiple ways to write and read MVD statements, grasp the relationship between notation components and MVD semantics, and be able to interpret MVD expressions from academic papers and textbooks.
The fundamental notation for multivalued dependencies uses the double-headed arrow: →→
Standard Form:
X →→ Y
Components:
How to Read It:
There are several equivalent ways to read X →→ Y:
The double arrow →→ was introduced by Ronald Fagin in 1977 in his seminal paper on multivalued dependencies and fourth normal form. Some older texts use alternative notations like X ⇒⇒ Y or X ↠ Y (using a twoheadrightarrow), but →→ is now the universally accepted standard in database theory literature.
Typography and Representation:
In different contexts, you may see the double arrow rendered as:
| Context | Representation |
|---|---|
| ASCII text | X -->> Y or X ->> Y |
| LaTeX | X \twoheadrightarrow Y or X \rightarrow\rightarrow Y |
| Unicode | X →→ Y (two consecutive arrows) |
| Informal | X =>> Y |
Regardless of how it's typeset, the meaning is identical: X multi-determines Y.
Both the left-hand side (LHS) and right-hand side (RHS) of an MVD can be sets of attributes, not just single attributes. The notation conventions follow similar patterns to functional dependencies.
Notation for Attribute Sets:
| Notation | Meaning | Example |
|---|---|---|
| A | Single attribute A | EmpID →→ Skill |
| AB | Set {A, B} (juxtaposition) | AB →→ C means {A,B} →→ {C} |
| {A, B} | Explicit set notation | {EmpID, Dept} →→ {Skill} |
| XY | Union of sets X and Y | If X = {A} and Y = {B}, then XY = {A, B} |
Examples with Multiple Attributes:
AB →→ CD
This means: {A, B} →→ {C, D}
Interpretation: Given any values for attributes A and B, the set of (C, D) pairs is independent of the remaining attributes in the relation.
Real-World Example:
Consider a relation:
R(CourseID, Semester, Instructor, TextBook)
If the instructors for a course are independent of the textbooks used (both may vary by semester), we write:
CourseSemester →→ Instructor
CourseSemester →→ TextBook
Or using juxtaposition:
CS →→ I (where C = CourseID, S = Semester, I = Instructor)
CS →→ T (where T = TextBook)
In formal database literature, attributes are often denoted by single capital letters, and sets are written by juxtaposition (concatenation). So ABC means {A, B, C}. This compact notation is essential for reading theoretical papers efficiently. When you see AB →→ CD, read it as {A, B} →→ {C, D}.
Because MVDs express independence, they inherently involve three parts of the relation schema:
Some authors make this three-part structure explicit using the pipe notation:
# Standard notationX →→ Y # Explicit complement notation (equivalent)X →→ Y | Z # Where Z = R - X - Y (all attributes not in X or Y) # Example in relation R(EmpID, Skill, Language):# X = {EmpID}, Y = {Skill}, Z = {Language} EmpID →→ Skill # Standard formEmpID →→ Skill | Language # Explicit complement formThe Pipe (|) Notation:
The expression X →→ Y | Z explicitly names both sides of the independence:
Why Use Pipe Notation?
The pipe notation serves several purposes:
Recall from Page 1: If X →→ Y holds, then X →→ (R - X - Y) automatically holds. The pipe notation X →→ Y | Z makes this symmetry visually apparent. You're not specifying two constraints—you're specifying one constraint that implies both MVDs.
Full Example with Pipe Notation:
Relation: Employee(EmpID, Skill, Language, Project)
If skills and languages are independent (for each employee), but projects are related to skills:
EmpID →→ Skill | Language # Skills independent of languages
# (Implicitly: EmpID →→ Language | Skill)
Note: The attribute Project is not in this MVD, suggesting there's a different dependency structure involving Project (perhaps EmpID, Skill →→ Project or a functional dependency).
MVDs are always defined with respect to a specific relation schema. The context matters because the complement (Z = R - X - Y) depends on what attributes exist in R.
Context-Specifying Notation:
Some formal treatments make the context explicit:
| Notation | Meaning |
|---|---|
| X →→ Y | Implicit context (assumed known) |
| X →→ Y [R] | MVD holds in relation schema R |
| X →→_R Y | Subscript indicating schema R |
| R: X →→ Y | Schema prefix notation |
Why Context Matters:
Consider the MVD EmpID →→ Skill.
In R₁(EmpID, Skill, Language):
In R₂(EmpID, Skill, Language, Project, Salary):
These are different constraints even though the notation looks the same. The addition of more attributes creates a stronger independence claim.
Embedded MVDs:
When discussing projections or subsets of attributes, we use the notation:
X →→ Y [R']
This means: "The MVD X →→ Y holds when we consider only the attributes of R' (which is a subset of R)."
Never interpret an MVD without knowing the full relation schema. The statement 'X →→ Y holds' is incomplete—you must know R to understand what Y is independent FROM. This is fundamentally different from FDs, which are less context-dependent.
In practice, relation schemas have multiple dependency constraints. We need notation for sets of dependencies and for mixing FDs with MVDs.
Set Notation for MVDs:
# A set of MVDs for relation R(A, B, C, D, E)M = { A →→ BC, A →→ D, AB →→ E} # Note: A →→ BC and A →→ D are not independent statements!# By complementation:# A →→ BC implies A →→ DE (since DE = R - A - BC)# A →→ D implies A →→ BCE (since BCE = R - A - D)# These constraints may interact in complex ways.Mixed Dependency Sets (FDs and MVDs):
Real schemas often have both functional dependencies and multivalued dependencies:
R(CourseID, Semester, Instructor, TextBook, Credits)
F = {
CourseID → Credits # FD: Course determines credit hours
}
M = {
CourseID, Semester →→ Instructor # MVD: Instructors independent of textbooks
}
D = F ∪ M # The complete set of dependencies
Universal Notation:
Some authors use a unified notation where:
When specifying a complete set of dependencies for a relation, it's common to list only the 'base' dependencies from which all others can be derived using axioms. For MVDs, this is more complex than for FDs because MVD axioms include rules that generate FDs from MVDs and vice versa.
Academic papers on database theory use precise notational conventions. Here's a guide to interpreting common patterns you'll encounter:
Common Patterns:
| You See | It Means |
|---|---|
| X →→ Y | Multivalued dependency: X multi-determines Y |
| X → Y | Functional dependency (single arrow) |
| X →→ Y | Z | X multi-determines Y, with Z as complement |
| X ⇉ Y | Alternative symbol for MVD (rare) |
| r(R) | Instance r of relation schema R |
| r |= X →→ Y | Instance r satisfies the MVD X →→ Y |
| F |= X →→ Y | MVD X →→ Y is implied by dependency set F |
| attr(R) | The set of attributes in schema R |
| R - X | Set difference: attributes in R but not in X |
Formal Definition in Papers:
When papers introduce MVDs formally, they typically write something like:
Definition: Let R be a relation schema with attribute set U. A multivalued dependency X →→ Y (where X, Y ⊆ U) holds in an instance r of R if for all tuples t₁, t₂ ∈ r with t₁[X] = t₂[X], there exists a tuple t₃ ∈ r such that:
- t₃[X] = t₁[X]
- t₃[Y] = t₁[Y]
- t₃[U - X - Y] = t₂[U - X - Y]
Shorthand Notations:
Papers often use these shorthands:
| Symbol | Meaning |
|---|---|
| U | Universal set of all attributes in R |
| Z | Complement: U - X - Y |
| t[X] | Projection of tuple t onto attributes X |
| πₓ(r) | Projection of relation r onto X |
| r₁ ⋈ r₂ | Natural join of relations r₁ and r₂ |
When working with MVD notation, precision is paramount. Here are common mistakes and how to avoid them:
You've now gained fluency in the notation system for multivalued dependencies. Let's consolidate:
What's Next:
With notation mastered, the next page explores the Independence Concept in depth. We'll examine what it truly means for attribute sets to be independent, explore the philosophical and mathematical foundations of independence in data, and see how this concept guides database design decisions.
You can now read and write MVD notation fluently. This notation literacy is essential for understanding database theory literature, specifying schema constraints precisely, and communicating dependency structures unambiguously. Next, we'll deepen our understanding of what 'independence' truly means in the context of MVDs.