# Property graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Property_graph
> Markdown URL: https://mediated.wiki/source/Property_graph.md
> Source: https://en.wikipedia.org/wiki/Property_graph
> Source revision: 1347607194
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Mathematical model used by graph-oriented databases

A **property graph**, **labeled property graph**, or **attributed graph** is a [data model](/source/Data_model) of various [graph-oriented databases](/source/Graph_database),[1] where pairs of entities are associated by directed relationships, and entities and relationships can have properties.

In [graph theory](/source/Graph_theory) terms, a property graph is a [directed](/source/Directed_graph) [multigraph](/source/Multigraph), whose [vertices](/source/Vertex_(graph_theory)) represent entities and [arcs](/source/Glossary_of_graph_theory#arc) represent relationships. Each arc has an identifier, a source node and a target node, and may have properties.

Properties are [key-value](/source/Key-value) pairs where keys are character strings and values are numbers or character strings. They are analogous to [attributes](/source/Attribute_(computing)) in [entity-attribute-value](/source/Entity%E2%80%93attribute%E2%80%93value_model) and [object-oriented](/source/Object-oriented_modeling) modeling. By contrast, in [RDF](/source/Resource_Description_Framework) graphs, "properties" is the term for the arcs. This is why a clearer name is *attributed graphs,* or graphs*with* properties.

This data model emerged in the early 2000s.

## Formal definition

Building upon widely adopted definitions,[2][3] a property graph/attributed graph can be defined by a [7-tuple](/source/Tuple) (N, A, K, V, α, κ {\displaystyle \kappa } , π), where

- N is the set of nodes/[vertices](/source/Vertices_(graph_theory)) of the graph

- A is the set of arcs (directed [edges](/source/Edge_(graph_theory))) of the graph

- K is a set of keys, taken from a countable set, defining the nature of attributes/properties

- V is a set of values, to be associated with these keys in order to define full-fledged attributes

- α : A → N × N {\displaystyle \alpha \colon A\to N\times N} is a *[total function](/source/Map_(mathematics))*, defining the multigraph proper. For a ∈ A, u∈ N, v ∈ N, α (a) = (u, v) means that a is an arc of the graph having node u for origin and node v for target

- κ {\displaystyle \kappa } is a *[binary relation](/source/Binary_relation)* over (A∪N) and K (formally defined as a subset of the cartesian product (A∪N)×K ), associating zero, one or several keys to each arc and node of the graph

- π : κ → V {\displaystyle \pi \colon \kappa \to V} is a *[partial function](/source/Partial_function)*, providing values for the properties of the nodes and the arcs which include them. For u ∈ N, a ∈ A and k ∈ K, π (u, k) (respectively π (a, k)) is the value associated with the property key k for the node u, (respectively the arc a), if the corresponding attribute property is defined there.

A complementary construct, used in several implementations of property graphs with commercial graph databases, is that of *[labels](https://neo4j.com/docs/getting-started/current/graphdb-concepts/#graphdb-labels)*, which can be associated both with nodes and arcs of the graph. Labels have a practical rather than theoretical justification, as they were originally intended for users of [Entity-Relationship models](/source/Entity-relationship_model) and [relational databases](/source/Relational_database), to facilitate the import of their legacy [data sets](/source/Data_sets) into [graph databases](/source/Graph_database) :. labels make it possible to associate the same identifier (that of the relational table, or of the ER entity) to all graph nodes which would correspond to the different rows of this relational table, or to [instances](/source/Instance_(computer_science)) of the same generic entity / class. With the proposed definition, these labels could in fact be viewed as attributes defined only by a key, without an associated value (this is why κ {\displaystyle \kappa } is defined separately as a binary relation, and π as a partial function). The basic definition thus becomes much clearer, simpler, and satisfies a principle of [parsimony](/source/Ockham's_razor). Alternatively, and more consistently, labels can be defined through type graphs, as special types associated with nodes and arcs.

## Relations with other models

### Graph theory and classical graph algorithms

Attributed graphs are especially useful and relevant in that they are an "umbrella" [hypernymic](/source/Hyponymy_and_hypernymy) concept ( i.e. a generalization) for several key [graph-theoretic](/source/Graph_theory) models, which have long been widely used in classical [graph algorithms](https://en.wikipedia.org/wiki/Category:Graph_algorithms)

- [Labeled graphs](/source/Graph_labeling) associate labels to each vertex and/or edge of a graph. Matched with attributed graphs, these labels correspond to *attributes comprising only a key*, taken from a [countable](/source/Countable_set) set (typically a character string, or an integer) - Colored graphs, as used in classical [graph coloring](/source/Graph_coloring) problems, are special cases of labeled graphs, whose labels are defined on a *finite* set of keys, matched to colors.

- [Weighted graphs](/source/Glossary_of_graph_theory#weighted_graph) associate a *numerical value* to arcs/edges, and, when relevant, to the vertices of a directed or undirected graph. These weights correspond to the values of a *set of attributes with the same key*. For example, for a model of a road network, where each segment has a length and a capacity (number of vehicles per unit time) can be represented by an edge with two weights. - [Flow networks](/source/Flow_network) are weighted graphs whose weights are interpreted as a *capacities*. They are used in all kinds of very classical models of transport networks, used e.g. with [maximum flow](/source/Maximum_flow_problem) algorithms. - [Shortest path problems](/source/Shortest_path_problem), as solved by very classical algorithms (like [Dijkstra's algorithm](/source/Dijkstra's_algorithm)), operate on weighted graphs for which the weights correspond to *distances*, real or virtual.

## Standardization

### [NGSI-LD](/source/NGSI-LD)

The [NGSI-LD](/source/NGSI-LD) data model specified by [ETSI](/source/ETSI) has been the first attempt to standardize property graphs under a [de jure](/source/De_jure) standards body. Compared to the basic model defined here, the NGSI-LD meta-model adds a formal definition of basic categories (entity, relation, property) on the basis of [semantic webstandards](/source/Semantic_web) ([OWL](/source/Web_Ontology_Language), [RDFS](/source/RDF_Schema), [RDF](/source/Resource_Description_Framework)), which makes it possible to convert all data represented in NGSI-LD into RDF datasets, through [JSON-LD](/source/JSON-LD) serialization. NGSI-LD entities, relations and properties are thus defined by reference to types which can themselves be defined by reference to [ontologies](/source/Ontology_(information_science)), [thesauri](/source/Thesaurus_(information_retrieval)), [taxonomies](/source/Taxonomy) or [microdata](/source/Microdata_(HTML)) vocabularies, for the purpose of ensuring the [semantic interoperability](/source/Semantic_interoperability) of the corresponding information.

### [GQL](/source/Graph_Query_Language)

The [ISO/IEC JTC1/SC32](/source/ISO%2FIEC_JTC_1%2FSC_32)/WG3 group of [ISO](/source/International_Organization_for_Standardization), which established the [SQL](/source/Structured_Query_Language) standard, specified a new [query language](/source/Query_language) suitable for graph-oriented databases, called [GQL](/source/Graph_Query_Language) (Graph Query Language). This standard includes the specification of a property graph data model, which should be along the lines of the basic model described here, possibly adding notions of labels, types, and [schemas](/source/Database_schema) .

## Type graphs and schemas

Graph-oriented databases are, compared to [relational databases](/source/Relational_database), touted for *not* requiring the prior definition of a [schema](/source/Database_schema) to start populating the base. This is desirable and suitable for environments and applications where one operates under an [open world assumption](/source/Open-world_assumption), such as the description of [complex systems](/source/Complex_systems) and [systems of systems](/source/System_of_systems), characterized by bottom-up organization and evolution, not control of a single stakeholder. However, even in such environments, it may be needed to constrain the representation of specific subsets of the information entered into the database, in a way that may resemble a traditional database schema, while keeping the openness of the overall graph for addition of unforeseen data or configurations. For example, the description of a [smart city](/source/Smart_city) falls under the open world assumption and will be described by the upper level of a graph database, without a schema. However, specific technical sub-systems of this city remain top-down [closed-world](/source/Closed-world_assumption) systems managed by a single operator, who may impose a stronger structuring of information, as customarily represented by a schema.

The notions of "type graphs" and schemas[2] make it possible to meet this need, with types playing a role similar to that of *labels* in classical graph databases, but with the added possibility of specifying relations between these types and constraining them by keys and properties. The type graph is itself a property graph, linked by a relation of [graph homomorphism](/source/Graph_homomorphism) with the graphs of instances that use the types it defines, playing a role similar to that of a schema in a [data definition language](/source/Data_definition_language).

The [ontologies](/source/Ontology_(information_science)), [thesauri](/source/Thesaurus) or [taxonomies](/source/Taxonomies) used to reference NGSI-LD types are also defined by graphs, but these are RDF graphs rather than property graphs, and they typically have broader scopes than database schemas. The complementary use, possible with NGSI-LD types, of type graphs *and* referencing of external ontologies, makes it possible to enforce strong data structuration and consistency, while affording [semantic grounding](/source/Symbol_grounding_problem) and [interoperability](/source/Semantic_interoperability).

## References

1. **[^](#cite_ref-1)** Angles, Renzo (2012-04-01). ["A comparison of current graph database models"](https://www.researchgate.net/publication/261076480). *International Conference on Data Engineering*. IEEE.

1. ^ [***a***](#cite_ref-:0_2-0) [***b***](#cite_ref-:0_2-1) Bonifati, Angela; Furniss, Peter; Green, Alastair; Harmer, Russ; Oshurko, Eugenia; Voigt, Hannes (2019), Laender, Alberto H. F.; Pernici, Barbara; Lim, Ee-Peng; de Oliveira, José Palazzo M. (eds.), ["Schema Validation and Evolution for Graph Databases"](http://link.springer.com/10.1007/978-3-030-33223-5_37), *Conceptual Modeling*, vol. 11788, Cham: Springer International Publishing, pp. 448–456, [arXiv](/source/ArXiv_(identifier)):[1902.06427](https://arxiv.org/abs/1902.06427), [doi](/source/Doi_(identifier)):[10.1007/978-3-030-33223-5_37](https://doi.org/10.1007%2F978-3-030-33223-5_37), [ISBN](/source/ISBN_(identifier)) [978-3-030-33222-8](https://en.wikipedia.org/wiki/Special:BookSources/978-3-030-33222-8), retrieved 2021-09-15{{[citation](https://en.wikipedia.org/wiki/Template:Citation)}}: CS1 maint: work parameter with ISBN ([link](https://en.wikipedia.org/wiki/Category:CS1_maint:_work_parameter_with_ISBN))

1. **[^](#cite_ref-3)** Gutierrez, Claudio; Hidders, Jan; Wood, Peter T. (2018), ["Graph Data Models"](https://doi.org/10.1007/978-3-319-63962-8_81-1), in Sakr, Sherif; Zomaya, Albert (eds.), *Encyclopedia of Big Data Technologies*, Cham: Springer International Publishing, pp. 1–6, [doi](/source/Doi_(identifier)):[10.1007/978-3-319-63962-8_81-1](https://doi.org/10.1007%2F978-3-319-63962-8_81-1), [ISBN](/source/ISBN_(identifier)) [978-3-319-63962-8](https://en.wikipedia.org/wiki/Special:BookSources/978-3-319-63962-8), retrieved 2021-09-15

---
Adapted from the Wikipedia article [Property graph](https://en.wikipedia.org/wiki/Property_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Property_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.