Les contraintes d’intégrité ont un rôle majeur pour garantir la qualité des données. Si les langages de contraintes ont été largement étudiés dans le cadre des bases de données relationnelles, leur expressivité comparative dans le cadre des bases de données graphes reste peu explorée. En particulier, l’interaction entre la topologie du graphe et les valeurs des données introduit de nouveaux défis de modélisation et de raisonnement.
Pendant ce séminaire, je présenterai une étude rigoureuse de l’expressivité du langage PG-Keys, introduit récemment. Nous le comparons à deux langages de contraintes fondamentaux pour les bases de données graphes, les Graph Functional Dependencies (GFDs) et les Graph Generating Dependencies (GGDs), dans un cadre unificateur paramétrant ces langages selon une composante topologique et une composante logique, et les étendant lorsque nécessaire. Nous identifions des fragments ayant de bons comportements, établissons des traductions syntaxiques, et montrons des résultats de séparation, ce qui permet de donner une hiérarchie complète et stricte d’expressivité. Ces résultats clarifient le rôle des PG-Keys parmi les langages de contraintes.
Je me concentrerai sur le cas des requêtes conjonctives avec prédicats d’égalité et d’inégalité, même si nos résultats peuvent être naturellement étendus à d’autres cadres, comme celui des regular path queries, je présenterai des résultats de séparation sur nos fragments, et donnerai des réécritures qui établissent la hiérarchie entre GFDs, GGDs, et PG-Keys.
ENGLISH VERSION
Integrity constraints play a central role in ensuring data quality. While constraint languages have been extensively studied for relational databases, the comparative expressiveness of constraint languages for property graph databases remains underexplored. In particular, the interplay between graph topology and data values introduces new modeling and reasoning challenges.
In this talk, I will present a principled study of the expressive power of the recently introduced PG-Keys language. We compare it with two core property graph constraint languages, Graph Functional Dependencies (GFDs) and Graph Generating Dependencies (GGDs), within a unifying framework that parametrizes these languages by topological constraints and logical predicates, and extends them when needed. We identify well-behaved fragments, establish syntactic translations, and prove separation results, yielding a complete and strict hierarchy of expressive power. The results clarify the role of PG-Keys in the landscape of property graph constraints.
I will focus on conjunctive queries with equality and inequality, although our results naturally extend to richer settings such as regular path queries, present separation results concerning our well-behaved fragments, and give rewritings establishing the hierarchy between GFDs, GGDs, and PG-Keys.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne