A property graph, labeled property graph, or attributed graph is a data model of various graph-oriented databases, where pairs of entities are associated by directed relationships, and entities and relationships can have properties. In graph theory terms, a property graph is a directed multigraph, whose vertices represent entities and arcs represent relationships. Each arc has an identifier, a source node and a target node, and may have properties. Properties are key-value pairs where keys are character strings and values are numbers or character strings. They are analogous to attributes in entity-attribute-value and object-oriented modeling. By contrast, in RDF 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, a property graph/attributed graph can be defined by a 7-tuple (N, A, K, V, α, κ {\displaystyle \kappa } , π), where
N is the set of nodes/vertices of the graph A is the set of arcs (directed edges) 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, 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 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, 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, 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 and relational databases, to facilitate the import of their legacy data sets into graph databases :. 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 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. 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 concept ( i.e. a generalization) for several key graph-theoretic models, which have long been widely used in classical graph algorithms
Labeled graphs 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 set (typically a character string, or an integer) Colored graphs, as used in classical graph coloring problems, are special cases of labeled graphs, whose labels are defined on a finite set of keys, matched to colors. Weighted graphs 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 are weighted graphs whose weights are interpreted as capacities. They are used in all kinds of very classical models of transport networks, used e.g. with maximum flow algorithms. Shortest path problems, as solved by very classical algorithms (like Dijkstra's algorithm), operate on weighted graphs for which the weights correspond to distances, real or virtual.
Standardization
NGSI-LD The NGSI-LD data model specified by ETSI has been the first attempt to standardize property graphs under a 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 (OWL, RDFS, RDF), which makes it possible to convert all data represented in NGSI-LD into RDF datasets, through 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, thesauri, taxonomies or microdata vocabularies, for the purpose of ensuring the semantic interoperability of the corresponding information.
GQL The ISO/IEC JTC1/SC32/WG3 group of ISO, which established the SQL standard, specified a new query language suitable for graph-oriented databases, called GQL (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. The GQL standard drew on prior industry work, including contributions from graph database vendors such as Neo4j, whose graph database also helped popularize property graphs.
… excerpt ends here. Continue reading the full article.
