PaperlayerView exact revision on arXiv

Source-linked AI summary

PG-Schema: Schemas for Property Graphs

Renzo Angles, Angela Bonifati, Stefania Dumbrava, George Fletcher, Alastair Green, Jan Hidders, Bei Li, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Stefan Plantikow, Ognjen Savković, Michael Schmidt, Juan Sequeda, Sławek Staworko, Dominik Tomaszuk, Hannes Voigt, Domagoj Vrgoč, Mingxi Wu, Dušan Živković

arXiv:2211.10962v4cs.DB

TL;DR

Property-graph schema support is limited despite demand and ongoing standardization efforts. PG-Schema proposes types and constraints with formal syntax and semantics; its feature comparison finds that no surveyed formalism or system covers every feature, while identifying a representation issue for introspection.

  • Problem

    Property-graph systems lack comprehensive schema support despite demand for schema compliance, leaving a need for a unified schema language.

    Source: §1 · p. 2

  • Method

    PG-Schema combines PG-Types and PG-Keys, with locally verifiable types and constraints, and specifies syntax and semantics for descriptive and prescriptive schemas.

    Source: §1 · p. 4, Existing graph technologies · p. 21

  • Results

    The comparison finds that no formalism or system covers all surveyed schema features, and PG-Schema aims to provide an extensible foundation.

    Source: Conclusion · p. 21

  • Takeaways & Limitations

    PG-Schema supports tractable validation when each constraint is tractable and supports schema-first, partial-schema, and flexible-schema use.

    Source: Existing graph technologies · p. 21

    PG-Schema does not support introspection because no commonly agreed representation captures PG-Types' type combinations; representing them intuitively remains future work.

    Source: Existing graph technologies · p. 21

Abstract

from arXiv · show

Property graphs have reached a high level of maturity, witnessed by multiple robust graph database systems as well as the ongoing ISO standardization effort aiming at creating a new standard Graph Query Language (GQL). Yet, despite documented demand, schema support is limited both in existing systems and in the first version of the GQL Standard. It is anticipated that the second version of the GQL Standard will include a rich DDL. Aiming to inspire the development of GQL and enhance the capabilities of graph database systems, we propose PG-Schema, a simple yet powerful formalism for specifying property graph schemas. It features PG-Types with flexible type definitions supporting multi-inheritance, as well as expressive constraints based on the recently proposed PG-Keys formalism. We provide the formal syntax and semantics of PG-Schema, which meet principled design requirements grounded in contemporary property graph management scenarios, and offer a detailed comparison of its features with those of existing schema languages and graph database systems.

1 INTRODUCTION

PG-Schema addresses limited property-graph schema support with a formal language intended to serve descriptive and prescriptive roles. It combines flexible PG-Types and PG-Keys constraints, and the paper specifies its syntax and semantics and compares it with existing systems and languages.

1 INTRODUCTION

  • Schema compliance is desirable but lacking, and inspection of eleven property-graph engines found no system with comprehensive schema support, motivating a unified language.The desired support would structure nodes, edges, and properties and enforce constraints.Source: §1 · p. 2
  • PG-Schema is proposed as a concrete contribution to efforts around the GQL standard and a future standardized property-graph schema language.The proposal consolidates and extends discussions from the Property Graph Schema Working Group.Source: §1 · pp. 2–3
  • A fraud-detection exploration illustrates how schema information can guide searches, suggest connection patterns, and support query formulation.The scenario is explicitly described as highly simplified and not representative of the actual complexity of such tasks and techniques.Source: §1 · pp. 3–4
  • PG-Schema combines PG-Types for node and edge labels, properties, and allowed connections with PG-Keys for integrity constraints, including keys and participation constraints.Its type definitions support rich inheritance and abstract types; strict and loose schemas and partial validation support descriptive and prescriptive use.Source: §1 · pp. 4–5
  • The paper presents an analysis of schema requirements, a formalism intended to meet them, and full syntax and semantics for incorporation into standards and systems.It also provides a parser and compares PG-Schema with schemas in other data models and practical graph-database systems.Source: §1 · p. 5

2 DESIGN REQUIREMENTS

The requirements treat schemas as serving both descriptive and prescriptive roles across evolving and stable data. They call for expressive graph types and constraints alongside flexibility, usable syntax, schema generation, and efficient validation.

2 DESIGN REQUIREMENTS

  • The requirements reflect a systematic process informed by research literature, industry use cases, and forthcoming GQL and SQL/PGQ standards.They aim to address schema needs across schema-first, flexible-schema, and partial-schema scenarios.Source: §2 · p. 5

2.2 Types and Constraints

  • Types group similar graph elements, while constraints express semantic information and impose limits that may require checking beyond an individual element.Types are local and typically checked statically; constraints are more global and typically checked dynamically.Source: §2.2 · p. 6

2.1 Property Graphs and Database Schemas

  • Schemas support understanding by mapping database objects to real-world entities, while their prescriptive role sets guarantees for reads and limits writes.These functions connect schema information to both user comprehension and data manipulation.Source: Property Graph Types · pp. 6–7, Flexibility · p. 6

Property Graph Types.

  • Property graph schemas should define node and edge types, endpoint types, and practical content types for describing graph elements.The requirements reflect nodes as objects with properties and edges as relationships between object kinds.Source: Property Graph Types · p. 7

Property Graph Constraints.

  • Schemas should support keys, participation constraints, type hierarchies, and fine-grained composition of compatible node and edge types.Keys also provide modeling capabilities for weak entities and functional relationships.Source: Property Graph Constraints · p. 7

Flexibility.

  • Graph databases support evolving applications, so schemas should span schema-first to schema-later with extensible, evolvable designs.Schemas can be prescriptive over stable data, descriptive of evolving data, or combine both roles.Source: Flexibility · p. 6, Property Graph Constraints · p. 7

Usability.

  • Practical schemas should be implementable, deriveable from graph instances, declarative, semantically defined, and efficient to validate.Validation should also report errors; schema generation should provide a constraint-free descriptive schema when none is specified.Source: Usability · pp. 7–8

3 DATA MODEL

The data model formalizes a property graph using finite sets of nodes and edges, endpoint mappings, labels, and property records. Records associate property names with values and provide the content of graph elements.

3 DATA MODEL

  • A record is a finite-domain partial function from property names to values, and an element's record is its content.The model assumes countable sets of labels, property names, and values.Source: §3 · p. 8
  • A property graph is a tuple of finite node and edge sets, an edge-to-endpoints function, a labels function, and a records function.Edges are disjoint from nodes; labels map nodes and edges to finite label sets, and records map them to property records.Source: §3 · p. 8
  • Each edge maps to an ordered pair of nodes, identifying its source and target endpoints.The endpoint mapping is total over the edge set.Source: §3 · p. 8

4 PG-SCHEMA

PG-Schema separates data-shape definitions in PG-Types from integrity constraints in PG-Keys. Its base node types express allowed labels and properties, with openness controls for additional content.

4 PG-SCHEMA

  • PG-Schema has two parts: PG-Types describe data shape and component types, while PG-Keys specify integrity constraints such as keys and participation constraints.PG-Types cover node, edge, and graph types.Source: §4 · p. 8

4.1 PG-Types by Example

  • PG-Types support open and closed definitions, allowing designers to control whether unmentioned labels or properties are permitted.OPEN can be specified separately for labels and properties.Source: §4.1 · p. 9, Base Node Types · p. 10

Base Node Types.

  • Base node types specify allowed label combinations and property requirements, including optional properties; OPEN permits additional labels.Label expressions use &, |, and optional labels to describe allowed combinations.Source: Base Node Types · p. 10

Base Edge Types.

PG-Schema edge types specify edge labels, properties, and endpoint types, while graph types combine node and edge types with a validation mode. Strict and loose graph types differ in whether every graph element must receive a type.

Base Edge Types.

  • Edge types specify allowed labels, contents, and endpoint types, and can use type alternatives to permit different endpoint types.The example edge type connects personType nodes, with customerType also allowed as an endpoint alternative.Source: Base Edge Types · p. 10

Graph Types.

  • A graph type combines node and edge types, and may include constraints; the example fraudGraphType contains three node types and one edge type.Its declarations can include types created within the graph type or imported into it.Source: Graph Types · p. 10
  • STRICT requires every graph node and edge to receive at least one declared or imported type, whereas LOOSE permits partial validation.A loose graph type does not require any particular element type to occur in the graph.Source: Graph Types · p. 11

Inheritance.

PG-Types support reuse through inheritance across node, edge, and graph types. Inherited specifications accumulate, with compatibility required when properties overlap.

Inheritance.

  • Node-type inheritance combines parent labels and properties, and overlapping properties must have compatible types.The employeeType example inherits Person, Salaried, name, optional birthday, and salary; a conflicting name type would make the type ill-defined.Source: Inheritance · pp. 11–12
  • Edge types can inherit from other edge types while adding properties or restricting endpoint types.buddyType inherits friendType and restricts its endpoint to employeeType.Source: Inheritance · p. 12
  • Graph inheritance imports all node and edge types from one graph type into another.The example imports socialGraphType into fraudGraphType.Source: Inheritance · p. 12

Including Types in Label Expressions.

PG-Types can combine previously defined types in label expressions, enabling compositional definitions. Abstract types cannot be directly instantiated but can contribute specifications through inheritance.

Including Types in Label Expressions.

  • The & operator supports intersections for open types, whose combined nodes can satisfy both component types.Combining closed types can instead yield a type whose nodes do not satisfy either component type individually.Source: Including Types in Label Expressions · p. 12
  • The | operator defines union types, allowing alternatives that preserve the label-and-property requirements of each component type.In the example, A is paired with propertyA and B with propertyB, rather than mixing either label with the other property's requirement.Source: Including Types in Label Expressions · pp. 12–13
  • Abstract types cannot be directly instantiated, but inherited properties can make them useful as components of a more specialized type.The example uses abstract salariedType to contribute salary to employeeType.Source: Including Types in Label Expressions · p. 13

4.2 Formal Definition and Semantics

The formal semantics defines graph types through base types and conformance rules. It also distinguishes a graph’s conformance from the mapping that records which types each element matches.

4.2 Formal Definition and Semantics

  • The formal definition is syntax-independent; the paper later connects it to the declarative syntax to provide its semantics.Source: §4.2 · p. 13

Types and conformance.

  • A formal base type is a pair of a label subset and a set of records; an element conforms when its labels match and its content belongs to that set.Record types in the concrete syntax specify allowed records, such as records containing an integer a and string b.Source: Types and conformance · p. 13
  • A formal graph type is a tuple containing disjoint finite node- and edge-type-name sets and mappings from those names to formal base types.Source: Types and conformance · p. 13
  • The node mapping assigns each node type a set of formal base types, while the edge mapping assigns each edge type triples for source, edge, and target.Source: Types and conformance · p. 13
  • The formalism distinguishes conformance from typings to handle strict and loose typing.Source: Types and conformance · p. 13
  • A node conforms to a node type when it conforms to one of that type’s base types; an edge conforms when its endpoints and itself match a mapped triple.Source: Types and conformance · p. 13
  • A graph conforms to a formal graph type when every graph element conforms to at least one type in that graph type.Source: Types and conformance · p. 13
  • The typing mapping records, for each node or edge, the set of types to which it conforms; graph conformance requires every such set to be non-empty.Source: Types and conformance · p. 14

Schema compilation.

Schema compilation interprets syntactic type definitions as formal graph types by unravelling and normalising definitions. The resulting type mappings support validation under loose or strict typing.

Schema compilation.

  • Schema compilation unravels and normalises type definitions to interpret the syntax as formal graph types.Source: Schema compilation · p. 14
  • Because type definitions are acyclic, compilation can unravel them bottom-up, interpreting each node-type expression as a family of allowed formal base types.The expressions are built from labels and type names using ?, &, and |, with optional OPEN and content descriptions.Source: Schema compilation · p. 14
  • A content description specifies property keys, base types, and optionality; OPEN permits additional keys, while closed descriptions restrict records to the listed keys.Source: Schema compilation · p. 14
  • The combination operator joins compatible records and combines their labels, enabling intersections to combine formal base types.For compatible records, shared keys must have equal values; the operation is akin to the relational natural join.Source: Schema compilation · p. 14
  • Edge-type expressions compile to triples of formal base types for source, edge, and target, which are combined with the endpoint expressions to define the edge type.Source: Schema compilation · p. 15
  • After unravelling, compilation excludes type names defined as ABSTRACT from the node- and edge-type-name sets.Source: Schema compilation · p. 15
  • For LOOSE types, validation computes each element’s typing; for STRICT types, it additionally requires every graph element to receive at least one type.Source: Schema compilation · p. 15

4.3 Validation and Graph Type Generation

The paper describes validation against graph types and a simple way to generate a graph type from a property graph. More refined schema inference is left to future work.

4.3 Validation and Graph Type Generation

  • Validation identifies conforming nodes for each node type, then uses that information to identify conforming edges; the syntax-based procedure can be implemented efficiently in an expressive graph query language.The language needs standard set operations and the ability to identify nodes and edges by labels, property names, and property value types.Source: §4.3 · p. 15
  • Graph-type generation creates an anonymous type for each node’s labels and properties, reuses identical types, then applies an analogous procedure to edges using endpoint types.The authors leave more refined schema generation to schema inference as future work.Source: §4.3 · p. 15

4.4 Adding Constraints

PG-Schema uses PG-Keys for constraints and extends their syntax to refer to graph types. The examples show constraints for keys, foreign keys, best-friend cardinality, and participation.

4.4 Adding Constraints

  • PG-Keys express constraints with MANDATORY, SINGLETON, and EXCLUSIVE qualifiers over query results.MANDATORY requires at least one matching tuple, SINGLETON permits at most one, and EXCLUSIVE prevents tuples from being shared across different values.Source: §4.4 · p. 16
  • PG-Schema extends PG-Keys by allowing type names wherever PG-Keys allows labels; a type name matches every node conforming to that type.Source: §4.4 · p. 16
  • The social-graph example uses PG-Keys for a person id key, a customer-to-person id foreign key, and a limit of one best-friend edge per person.The paper also identifies participation constraints and SQL-style CHECK constraints as expressible with PG-Keys.Source: §4.4 · p. 16
  • In LOOSE graph types, PG-Keys still apply: other node types may be present, while the id-key constraint remains applicable to personType nodes.Source: §4.4 · p. 17
  • After computing graph typings, PG-Keys can be evaluated using types as if they were graph labels.Source: §4.4 · p. 17
  • The authors conclude that PG-Schema meets all requirements identified earlier in the paper.Source: §4.4 · p. 17

5 RELATIONSHIP TO OTHER PARADIGMS

The comparison evaluates schema formalisms across type, constraint, and schema features, finding varied support and no system or formalism that covers them all. PG-Schema supports many of these features, while the paper outlines possible extensions for others.

5.1 Existing Graph Schema Features; Conclusion.

  • The comparison groups capabilities into type, constraint, and schema features, and finds that no surveyed formalism or system covers them all.Source: §5.1 · p. 17, Conclusion · p. 21

Conceptual data models.

  • ER-based models generally support inheritance and complex attributes, but most allow only one single-attribute key; ORM2 is a notable exception.Source: Conceptual data models · pp. 17–18

RDF formalisms.

  • RDF formalisms vary in validation tractability: the most expressive cases are generally intractable, though practically useful fragments can be tractable.Source: RDF formalisms · p. 18

Tree-structured data.

  • XML schema languages differ in their support for types and constraints; XML Schema offers complex keys, while DTDs lack inheritance and abstract types.JSON Schema supports unions and intersections of open types, nested values, and introspection, but not key constraints.Source: Tree-structured data · p. 19

Existing graph technologies.

  • Graph technologies vary in type and constraint support: some offer type hierarchies, while support for cardinality and binary-relation constraints is limited to selected systems.The reviewed systems differ in validation, introspection, and schema modes.Source: Existing graph technologies · pp. 19–20
  • PG-Schema separates locally verifiable types from constraints, enabling tractable validation when each constraint is tractable and meaningful partial validation.It supports strict, loose, and flexible schemas; its type-feature support is largely complete, while some property type features are delegated to an open property type system.Source: Existing graph technologies · p. 21

Range constraints; Complex datatypes.

Intersections and unions for content types; Advanced cardinalities.

6 SUMMARY AND LOOKING AHEAD

PG-Schema unifies property-graph schema capabilities in a proposal for future GQL versions. It combines a rich type system and integrity constraints with potential value for standardization, graph database vendors, and future research.

6 SUMMARY AND LOOKING AHEAD

  • PG-Schema is the first unifying property-graph schema language and serves as a recommendation for future GQL versions.The proposal resulted from academia-industry collaboration to bridge gaps and accelerate standardization.Source: §6 · p. 22

Summary.

  • PG-Schema supports node and edge types, complex type hierarchies, and integrity constraints through a formal language with defined syntax and semantics.It supports descriptive and prescriptive roles, agile evolution, flexible validation, and usability.Source: Summary · p. 23
  • Its core combines PG-Types, including multi-inheritance, with PG-Keys for complex key and participation constraints.The language is extensible with features such as range constraints, complex data types, content type combinators, and advanced cardinalities.Source: Summary · p. 23

Looking Ahead.

  • The proposal offers graph database vendors an opportunity to increase functionality for current and future customer demands, and provides a basis for academic research.The authors hope the academia-industry collaboration model will be replicated in other communities.Source: Looking Ahead · p. 23

Related papers

Loading 2211.10962v4…