Expressive Power of Property Graph Constraint Languages

Dit artikel presenteert het eerste systematische onderzoek naar de expressiviteit van PG-Keys, een nieuwe constrainttaal voor eigenschapsgrafieken die de GQL-standaard zal informeren, door deze via een unificerend kader te vergelijken met bestaande formalismen zoals GFD en GGD en zo een strikte hiërarchie van expressieve kracht vast te stellen.

De kern

Stel je voor dat je een enorme, complexe stad bouwt. In deze stad zijn er gebouwen (de knopen of nodes) en wegen die ze verbinden (de lijnen of edges). Maar deze stad is niet zomaar een stad; elk gebouw en elke weg heeft ook een adresboekje met extra informatie, zoals "naam", "eigenaar" of "geopend op datum". Dit noemen we een Property Graph.

Nu, als je zo'n stad wilt bouwen, wil je regels hebben. Je wilt bijvoorbeeld zeggen: "Elk gebouw moet een eigenaar hebben" of "Twee gebouwen mogen niet dezelfde naam hebben". Deze regels noemen we constraints (beperkingen of waarheidswaarden).

Deze paper is een wetenschappelijk onderzoek dat zich afvraagt: Welke taal is het beste om deze regels te schrijven? En belangrijker nog: Welke taal kan de meeste en slimste regels beschrijven?

De auteurs vergelijken drie verschillende "taalstelsels" die ontwikkelaars gebruiken om deze regels op te stellen:

1. GFD (Graph Functional Dependencies): De oude, betrouwbare standaard.
2. GGD (Graph Generating Dependencies): Een krachtigere, maar complexere taal.
3. PG-Keys: Een nieuwe, moderne taal die speciaal is ontworpen voor deze eigenschappen-rijke grafen (en die binnenkort de officiële standaard wordt).

Het Grote Experiment: De "Gedeelde Variabelen"

Om deze talen eerlijk te vergelijken, kijken de auteurs naar één specifiek trucje: Hoeveel "draadjes" mogen de twee kanten van een regel met elkaar delen?

Stel je een regel voor als een brug tussen twee eilanden:

• Eiland A (De Bron): Waar de regel begint (bijvoorbeeld: "Kijk naar alle mensen in een forum").
• Eiland B (Het Doel): Wat er moet gebeuren (bijvoorbeeld: "Zorg dat ze allemaal dezelfde taal spreken").

In de oude talen (GFD) mag je maar één persoon uit Eiland A koppelen aan één persoon op Eiland B.
In de krachtigere taal (GGD) mag je veel personen koppelen.

De auteurs ontdekten iets verrassends:

• Als je alleen maar gelijkheid mag gebruiken (bijv. "A is hetzelfde als B"), dan is de nieuwe taal (PG-Keys) net zo slim als de krachtige taal (GGD), mits je slimme trucjes gebruikt met woorden als "SINGLETON" (maximaal één) of "EXCLUSIVE" (alleen maar unieke waarden).
• Maar als je ook ongelijkheid mag gebruiken (bijv. "A is NIET hetzelfde als B"), dan wordt het nog interessanter. Dan blijkt dat de nieuwe taal (PG-Keys) precies even krachtig is als een heel specifieke, beperkte versie van de krachtige taal.

De Grootste Ontdekking: "Smaakmakers" vs. "Echte Kracht"

Het meest opvallende resultaat van dit onderzoek is dit:
De nieuwe taal (PG-Keys) heeft speciale woorden als MANDATORY (verplicht), EXCLUSIVE (uitsluitend) en SINGLETON (slechts één).

De auteurs bewijzen dat deze woorden eigenlijk alleen maar smaakmakers zijn. Ze maken het voor mensen makkelijker om regels te schrijven, maar ze voegen geen nieuwe wiskundige kracht toe.

• Vergelijking: Het is alsof je een recept hebt. Je kunt zeggen "voeg een snufje zout toe" (het woord SINGLETON) of je kunt het recept herschrijven door precies te zeggen "voeg 0,5 gram zout toe" (de complexe wiskundige taal). Het resultaat is hetzelfde, maar het ene is makkelijker te lezen.

Als je de taal (PG-Keys) gebruikt met de mogelijkheid om "niet gelijk aan" te zeggen, dan kun je elke regel die je met die speciale woorden schrijft, vertalen naar de basiswiskundige taal. De speciale woorden zijn dus syntaxis-suiker: lekker om te gebruiken, maar niet essentieel voor de kracht van de machine.

Waarom is dit belangrijk?

Deze paper is niet zomaar een theoretisch gedoe. Het gaat over de toekomst van de GQL-standaard. GQL is het nieuwe "SQL" voor graf-databases (zoals Neo4j).

De auteurs zeggen tegen de mensen die deze standaard schrijven:
"Jullie willen PG-Keys in de standaard opnemen. Dat is prima, want het is handig voor gebruikers. Maar wees je ervan bewust dat je geen 'magische' nieuwe kracht toevoegt aan de database. Je voegt alleen maar een betere interface toe. Als je echt complexe regels wilt controleren, moet je weten dat je soms de 'zware' taal (GGD) nodig hebt, of dat je slim moet zijn met je variabelen."

Samenvatting in één zin:

De auteurs hebben bewezen dat de nieuwe, populaire taal voor het controleren van graf-databases (PG-Keys) net zo krachtig is als de zware wiskundige taal (GGD), zolang je maar slimme regels gebruikt, en dat de speciale woorden in die nieuwe taal vooral bedoeld zijn om het menselijk leven makkelijker te maken, niet om de computer superkrachten te geven.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Expressive Power of Property Graph Constraint Languages" in het Nederlands.

Probleemstelling

Integriteitsconstraints zijn essentieel voor datakwaliteit en betrouwbare data-integratie. Hoewel de expressiviteit van constraints voor relationele databases (zoals functionele afhankelijkheden) grondig is onderzocht, blijft de vergelijkende expressiviteit voor property graph databases onderbelicht. De interactie tussen graftopologie en data-waarden introduceert nieuwe uitdagingen.

Recent is de taal PG-Keys geïntroduceerd om objecten in property graphs te identificeren en te refereren. Deze taal maakt gebruik van assertion keywords zoals MANDATORY, EXCLUSIVE en SINGLETON. Ondanks de groeiende interesse, is de landschap van constraint-talen voor property graphs gefragmenteerd. Er ontbreekt een formeel kader om PG-Keys te positioneren ten opzichte van bestaande formalismen zoals Graph Functional Dependencies (GFD) en Graph Generating Dependencies (GGD). Dit gebrek aan inzicht belemmert de ontwikkeling van gestandaardiseerde talen zoals GQL (Graph Query Language) en de SQL/PGQ-extensie, waarin PG-Schema (een superset van PG-Keys) als kandidaat is opgenomen.

Methodologie

De auteurs voeren het eerste systematische en principiële onderzoek uit naar de expressieve kracht van deze constraint-talen. De kern van hun aanpak bestaat uit:

1. Unificerend Kader: Om een eerlijke vergelijking mogelijk te maken, presenteren de auteurs een unificerend parametrisch kader. Hierin worden GFD, GGD en PG-Keys herformuleerd met een gemeenschappelijke structuur.
2. Query-talen: De analyse is gebaseerd op Conjunctive Regular Path Queries (CRPQ), met variaties in toegestane predikaten:
   • Alleen gelijkheid (=).
   • Gelijkheid en ongelijkheid (= en ≠).
   • Predikaten beperkt tot constanten (=c, ≠c).
3. Fragmentering: De auteurs definiëren subklassen van deze talen gebaseerd op het aantal gedeelde variabelen ($n$) tussen de "scope" (linkerzijde/vóórwaarde) en de "descriptor" (rechterzijde/nadeel) van een constraint.
   • $n$GFD en $n$GGD: Constraints waarbij maximaal $n$ variabelen gedeeld worden.
   • $m$PG-Keys: Een subklasse van PG-Keys die alleen MANDATORY gebruikt.
4. Vergelijkingsstrategie:
   • Inclusies: Bewijzen dat constraints in taal A vertaald kunnen worden naar taal B.
   • Scheiding (Separation): Bewijzen dat er constraints bestaan die in taal A uitdrukbaar zijn maar niet in taal B, zelfs niet met extensies. Dit wordt vaak bewezen door specifieke grafconstructies (zoals cliques of cycli) te gebruiken die door de ene taal worden onderscheiden maar door de andere niet.

Belangrijkste Bijdragen

1. Gedetailleerde Analyse van Taalfeatures:
   De auteurs tonen aan dat het aantal gedeelde variabelen en de toelating van ongelijkheid (≠) cruciale factoren zijn voor de expressieve kracht. Ze onthullen dat het ontwerp van PG-Keys (waarbij slechts één variabele gedeeld mag worden) een belangrijke beperking is die de expressiviteit beïnvloedt.

2. Expressiviteitsinclusies en Hiërarchieën:
   Er wordt een complete en strikte hiërarchie van expressieve kracht vastgesteld. De resultaten tonen aan wanneer PG-Keys strikt meer expressief is dan andere talen en wanneer ze equivalent zijn.

3. Scheidingsresultaten:
   De auteurs bewijzen dat bepaalde constraints inherent onuitdrukbaar zijn in specifieke talen of fragmenten. Dit leidt tot een gedetailleerd begrip van de beperkingen van elke taal.

Kernresultaten

De resultaten worden samengevat in twee hoofdscenario's, afhankelijk van de toegestane predikaten in de query-taal:

1. Scenario: Alleen Gelijkheid (CRPQ[=])

In dit scenario is de hiërarchie als volgt (waarbij $\subsetneq$ een strikte inclusie aangeeft):
$$1\text{GGD} \subsetneq \text{PG-Keys} \subsetneq \text{GGD}$$

• GFD vs. 1GGD: GFD is niet equivalent aan 1GGD; er zijn constraints in GFD die niet in 1GGD kunnen worden uitgedrukt en vice versa.
• PG-Keys vs. GGD: PG-Keys is strikt minder expressief dan GGD. GGD kan met meerdere gedeelde variabelen de SINGLETON en EXCLUSIVE keywords van PG-Keys simuleren.
• Verrassend Resultaat: Ondanks dat PG-Keys slechts één gedeelde variabele toestaat, kan het GFD simuleren door slim gebruik te maken van het SINGLETON keyword. Dit betekent dat GFD $\subseteq$ PG-Keys.

2. Scenario: Gelijkheid en Ongelijkheid (CRPQ[=, ≠])

De introductie van ongelijkheid (≠) verandert het landschap drastisch:
$$\text{GFD} \subsetneq 1\text{GGD} = \text{PG-Keys} \subsetneq \text{GGD}$$

• Equivalentie: In dit scenario zijn PG-Keys en 1GGD equivalent.
• Syntactisch Suiker: De specifieke keywords van PG-Keys (EXCLUSIVE, SINGLETON) blijken in dit context syntactisch suiker te zijn. Elke PG-Key kan worden gecompileerd naar een 1GGD (en omgekeerd) door gebruik te maken van ongelijkheidspredikaten om de unieke eigenschappen te simuleren.
• Hiërarchie: GGD blijft strikt expressiever dan zowel PG-Keys als 1GGD, omdat GGD meerdere gedeelde variabelen kan gebruiken, wat essentieel is voor bepaalde complexe constraints.

Significantie en Implicaties

1. Informatie voor Standaardisatie (GQL):
   De resultaten zijn direct relevant voor de ontwikkeling van de GQL-standaard. Het feit dat PG-Keys (in aanwezigheid van ongelijkheid) equivalent is aan 1GGD, betekent dat de complexiteit van de EXCLUSIVE en SINGLETON keywords voornamelijk ligt in de gebruikersinterface (syntaxis) en niet in de onderliggende theoretische expressiviteit. Ontwerpers van GQL kunnen hieruit concluderen dat ze deze keywords kunnen behouden voor gebruiksgemak zonder de theoretische grenzen van de taal te veranderen.

2. Fundamenteel Inzicht in Constraint-talen:
   Het paper legt bloot dat het aantal gedeelde variabelen de belangrijkste parameter is die de expressieve kracht bepaalt. Het onderscheid tussen talen die slechts één variabele delen (zoals PG-Keys en 1GGD) en talen die er meerdere kunnen delen (GGD) is fundamenteel.

3. Complexiteit en Toekomstig Onderzoek:
   De auteurs wijzen erop dat het aantal gedeelde variabelen ook van invloed is op de complexiteit van validatieproblemen. Terwijl GGD-validatie $\Pi_2^P$-compleet is, zou het beperken van het aantal gedeelde variabelen de complexiteit kunnen verlagen (naar $\Delta_2^P$). Dit opent nieuwe richtingen voor fijnmazige complexiteitsanalyses.

4. Rol van Connectiviteit:
   Het paper merkt op dat de huidige resultaten gebaseerd zijn op niet-geconnecteerde patronen. In praktische query-talen (zoals Cypher en GQL) worden vaak connectiviteitsrestricties opgelegd. De auteurs voorspellen dat dit de expressieve kracht van GGD zou kunnen verminderen en de hiërarchie zou kunnen veranderen, wat een belangrijk punt is voor toekomstig onderzoek.

Samenvattend biedt dit paper het eerste formele fundament om property graph constraint-talen te vergelijken, en positioneert PG-Keys precies binnen het spectrum van bestaande formalismen, wat cruciaal is voor de toekomstige evolutie van grafstandaarden.