Expressive Power of Property Graph Constraint Languages

This paper presents the first systematic study of the expressive power of the PG-Keys language by establishing a unifying framework to compare it with Graph Functional Dependencies (GFD) and Graph Generating Dependencies (GGD), ultimately revealing a strict hierarchy of expressiveness that clarifies PG-Keys' capabilities within the context of the upcoming GQL standard.

The Gist

Imagine you are the architect of a massive, bustling city called The Property Graph. In this city, every building (node) and every road (edge) has a name tag and a list of attributes (like "owner," "color," or "construction date").

To keep this city from falling into chaos, you need Rules of the Road (constraints). These rules tell you things like: "Every building must have a unique address," or "If two people are in the same club, they must speak the same language."

For a long time, city planners had different rulebooks for different types of cities. Some rulebooks were very strict but simple; others were flexible but hard to read. Recently, a new, popular rulebook called PG-Keys was introduced to help manage this specific type of city. But nobody knew exactly how powerful it was compared to the old rulebooks.

This paper is like a comparative review that puts all these rulebooks side-by-side to see which one can actually do the most.

The Three Main Rulebooks

The authors compare three specific languages used to write these rules:

1. GFD (The "Strict Accountant"):

   • Analogy: Imagine a rule that says, "If two people are in the same room, they must have the same shirt color."
   • How it works: It looks at a pattern (two people in a room) and forces a relationship (same shirt). It's very precise but can't easily say "There can be only one person in this room."

2. GGD (The "Generous Builder"):

   • Analogy: This is like a rule that says, "If you see a room with two people, you must build a new bridge connecting them to a third person."
   • How it works: It's very powerful. It can look at a pattern and force the creation of new connections or complex relationships. It's the "big gun" of the group.

3. PG-Keys (The "New City Planner"):

   • Analogy: This is the new, trendy rulebook designed specifically for modern cities. It has special keywords like MANDATORY (you must have this), EXCLUSIVE (only one of these allowed), and SINGLETON (exactly one of these).
   • The Catch: It has a strict design rule: The "scope" (where the rule applies) and the "descriptor" (what the rule checks) can only share one variable (one common point of reference). It's like saying, "You can only compare the current room to the next room through a single door."

The Big Discovery: The "Shared Variable" Limit

The core of the paper is a deep dive into what happens when you limit how many "doors" (shared variables) you can use to connect the two sides of a rule.

The "One-Door" vs. "Many-Door" Experiment:
The authors realized that GGD (the Generous Builder) is powerful because it can use many doors to connect ideas. PG-Keys (the New Planner) is restricted to one door.

• The Surprise: The authors found that if you allow the rules to say "these two things are NOT equal" (inequality), the One-Door restriction of PG-Keys isn't actually a weakness!
• The Metaphor: Imagine you want to check if a room has only one chair.
  • Without "Not Equal": You need to look at every chair and compare it to every other chair (many doors).
  • With "Not Equal": You can just say, "If I find two chairs, they must be different." This single "Not Equal" check is so powerful that it mimics the ability to look at many things at once.

The Verdict: A Strict Hierarchy

The paper builds a "power ladder" to show which languages can do what:

1. The Bottom Rung (GFD): Good for simple "if-then" rules, but can't handle "exactly one" or "at most one" easily.
2. The Middle Rung (PG-Keys):
   • If you only use "equals" (=), PG-Keys is stronger than GFD but weaker than GGD. It can do some unique things GFD can't, but it can't do everything GGD can.
   • However, if you allow "not equals" (≠), PG-Keys becomes just as powerful as a restricted version of GGD.
   • The "Syntactic Sugar" Revelation: The authors proved that the fancy keywords in PG-Keys (EXCLUSIVE, SINGLETON) are actually just "syntactic sugar." They look fancy, but they don't add any new power. You can rewrite any PG-Key rule into a standard GGD rule without losing any meaning. The "One-Door" limit is the only real constraint, and it's surprisingly strong.
3. The Top Rung (Full GGD): The most powerful. It can do everything the others can, plus complex multi-variable connections that even the "Not Equal" trick can't fully replicate in every scenario.

Why Does This Matter?

This research is crucial for the future of database standards (like the upcoming GQL language).

• For Designers: It tells them that they don't need to invent a whole new, complex language to get "Unique" or "Exclusive" constraints. They can use the existing, simpler logic of GGD and just add a few keywords for user-friendliness.
• For Users: It clarifies that while PG-Keys looks different, it's not a magic bullet that breaks the laws of logic. It fits neatly into the existing ecosystem of database rules.

In a Nutshell

Think of PG-Keys as a sleek, modern smartphone. It has a beautiful interface with special buttons for "One Person Only" or "Must Have."
The paper proves that under the hood, it's running the same engine as the older, clunkier GGD computer. The special buttons are just shortcuts; they don't give the phone a new superpower, they just make it easier to use. And the only real limit is that you can only connect two thoughts through a single bridge, which turns out to be a very strong bridge indeed.

Technical Summary

Here is a detailed technical summary of the paper "Expressive Power of Property Graph Constraint Languages" by Dumbrava et al.

1. Problem Statement

The paper addresses a critical gap in the theoretical understanding of property graph constraint languages. While integrity constraints for relational databases are well-studied, the comparative expressiveness of constraint languages for graph databases remains fragmented. Specifically, the authors focus on PG-Keys, a recent language proposed to inform the upcoming GQL (Graph Query Language) standard.

The core challenge is that existing formalisms—Graph Functional Dependencies (GFD), Graph Generating Dependencies (GGD), and PG-Keys—utilize different pattern languages, data predicates (equality/inequality), and structural mechanisms (e.g., how many variables can be shared between the "scope" and "descriptor" of a constraint). Without a unified framework, it is impossible to determine:

• Which language is strictly more expressive than another.
• Whether the specific design choices of PG-Keys (e.g., limiting shared variables to one) impose expressiveness limitations.
• How to translate constraints between these languages for interoperability.

2. Methodology

The authors employ a formal, principled approach to compare these languages:

• Unified Framework: They recast GFD, GGD, and PG-Keys into a common parametric framework based on Conditional Conjunctive Regular Path Queries (CRPQ). This allows for a fair comparison based solely on structural differences rather than syntactic variations.
• Query Languages: The analysis considers two settings for the underlying query language:
  1. CRPQ[=]: Queries with equality predicates only.
  2. CRPQ[=, ≠]: Queries with both equality and inequality predicates.
• Fragment Definition: They define subclasses of constraints based on the number of shared variables ($n$) between the source (scope) and target (descriptor) of the dependency:
  • $n$GFD and $n$GGD: Constraints sharing at most $n$ variables.
  • $m$PG-Keys: A subset of PG-Keys using only the MANDATORY keyword.
• Comparative Analysis: The authors establish expressiveness inclusions (via translation algorithms) and separation results (via counter-examples) to build a strict hierarchy of expressive power.

3. Key Contributions

A. Fine-Grained Language Feature Analysis

The paper identifies that the number of shared variables is the primary driver of expressive power.

• PG-Keys Restriction: PG-Keys are defined such that only one variable can be shared between the scope and descriptor.
• Impact: The authors prove that this restriction is significant in some contexts but negligible in others, depending on the availability of inequality predicates.

B. Expressiveness Inclusions and Translations

The authors provide constructive proofs showing how constraints in one language can be translated into another:

• GFD vs. GGD: GFD is a strict subset of GGD.
• PG-Keys vs. GGD:
  • With only equality (=), PG-Keys can be simulated by GGD using two disjoint copies of the scope/descriptor to enforce EXCLUSIVE and SINGLETON constraints. Thus, PG-Keys $\subseteq$ GGD.
  • With inequality (≠), a single shared variable is sufficient to simulate EXCLUSIVE and SINGLETON using negation.

C. Separation Results

The paper proves that certain inclusions are strict (i.e., the superset language can express constraints the subset cannot):

• Hierarchy of Shared Variables: For GGD, the hierarchy is strict: $n$GGD $\subsetneq$ $m$GGD (for $n < m$).
• GFD vs. 1GGD: There are constraints expressible in 1GGD (one shared variable) that cannot be expressed in GFD (which effectively has zero shared variables in the target).
• The "Surprising" Simulation: The authors demonstrate that PG-Keys can simulate GFD even with only one shared variable. This is achieved by cleverly using the SINGLETON keyword to enforce functional dependencies that would normally require multiple shared variables.

4. Key Results and Hierarchy

The paper establishes a complete and strict hierarchy of expressive power, summarized in two main theorems:

Case 1: Equality Only (CRPQ[=])

In this setting, the ability to use inequality is absent, making the SINGLETON and EXCLUSIVE keywords powerful tools for simulating structural constraints.

• Hierarchy:
  $$\text{GFD} \subsetneq \text{PG-Keys} \subsetneq \text{GGD}$$
  (Note: PG-Keys is strictly more expressive than GFD because SINGLETON can simulate GFD, but PG-Keys cannot simulate all GGDs which require multiple shared variables.)
• Key Finding: PG-Keys are strictly more expressive than GFD, but strictly less expressive than full GGD.

Case 2: Equality and Inequality (CRPQ[=, ≠])

The introduction of inequality predicates fundamentally changes the landscape.

• Hierarchy:
  $$\text{GFD} \subsetneq \text{PG-Keys} = 1\text{GGD} \subsetneq \text{GGD}$$
• Key Finding:
  • Collapse: In the presence of inequality, PG-Keys are equivalent to 1GGD. The EXCLUSIVE and SINGLETON keywords become syntactic sugar; they can be compiled into standard 1GGD constraints using inequality.
  • Strictness: Even with inequality, 1GGD (and thus PG-Keys) cannot express all constraints of full GGD (which allows $>1$ shared variables).

5. Significance and Implications

• Standardization (GQL): The results directly inform the design of the GQL standard. Since PG-Keys (a candidate for GQL) is equivalent to 1GGD in the presence of inequality, the standard can rely on the simpler 1GGD formalism for theoretical analysis without losing expressive power.
• Design Trade-offs: The paper clarifies that the restriction of PG-Keys to a single shared variable is a deliberate design choice. It simplifies the language (making it easier to implement and reason about) without sacrificing expressive power if inequality is supported.
• Complexity: The number of shared variables is identified as a key parameter for computational complexity. While GGD validation is $\Pi^P_2$-complete, fixing the number of shared variables ($n$) may lower the complexity class (potentially to $\Delta^P_2$), suggesting that restricting shared variables is not just an expressiveness trade-off but also a performance optimization.
• Future Directions: The authors highlight that connectedness constraints (common in practical query languages like Cypher) and different path semantics (e.g., shortest path vs. all walks) could alter these hierarchies, suggesting areas for future research.

In summary, this paper provides the first rigorous, systematic comparison of property graph constraint languages, proving that PG-Keys is a highly expressive language that, under standard conditions (with inequality), is equivalent to a restricted fragment of GGD (1GGD), making it a robust foundation for future graph database standards.