Source-linked AI summary
Constructions from Dots and Lines
Marko A. Rodriguez, Peter Neubauer
TL;DR
The article examines when graph representations of objects and relationships are useful in computing. It describes graph and property-graph models, graph databases, endogenous indices, and traversal-based processing, concluding that graph databases and traversal frameworks support large-scale graph data and analysis.
Problem
Computing needs data-management approaches suited to increasingly large and variegated datasets, while graph representations are useful only when their storage and processing tools can be leveraged.
Method
The article explains simple and property-graph models, graph databases, endogenous indices, and graph traversal as ways to represent, store, query, and process interconnected data.
Results
Graph databases support efficient processing of dense, interrelated datasets through fast traversals, while graph extensions such as indices can reduce lookup costs from O(n) to O(log2 n).
Takeaways & Limitations
Graphical models are beneficial when their domain relationships align with traversal-oriented processing and the available graph databases and algorithms.
Takeaways & Limitations
The article does not explore the broader database landscape in depth, and distinctions among RDF graph concepts are outside its scope.
Abstract
from arXiv · showhide
A graph is a data structure composed of dots (i.e. vertices) and lines (i.e. edges). The dots and lines of a graph can be organized into intricate arrangements. The ability for a graph to denote objects and their relationships to one another allow for a surprisingly large number of things to be modeled as a graph. From the dependencies that link software packages to the wood beams that provide the framing to a house, most anything has a corresponding graph representation. However, just because it is possible to represent something as a graph does not necessarily mean that its graph representation will be useful. If a modeler can leverage the plethora of tools and algorithms that store and process graphs, then such a mapping is worthwhile. This article explores the world of graphs in computing and exposes situations in which graphical models are beneficial.
1 The Bits and Pieces of the Dots and Lines
Graphs represent objects and their relationships as vertices and edges, while variations add labels, attributes, directions, weights, and other structures. The property graph combines many such features and can express several common graph types through simple restrictions or additions.
- Graph fundamentals: A graph models objects and their relationships as vertices and edges, with simple graphs using undirected edges between unique vertex pairs.Simple graphs exclude loops and multiple edges between the same pair of vertices.
- Graph types: Graph formalisms include multi-graphs, weighted, labeled, directed, attributed, semantic, hyper-, RDF, and pseudo graphs.These structures can represent features such as multiple edges, transition probabilities, metadata, edge orientation, arbitrary-size connections, and reflexive relationships.
- Graph types: Graph types can be combined to provide the expressivity needed to capture essential features of a domain.The article notes that the listed graph types are neither exhaustive nor universally named across domains.
- Property graphs: Property graphs support directed, labeled, attributed multi-graphs, including labels and attribute metadata on both vertices and edges.Their flexibility allows simple, semantic, RDF, and weighted graphs to be generated by removing or restricting particular features.
- Property graphs: The property graph is convenient because graph systems supporting it implicitly support other graph types through simple morphisms.The article also notes that RDF graphs use URIs, literals, and blank or anonymous nodes, a distinction outside its scope.
2 Preserving Dots and Lines
Computing offers many database models, with graph databases specializing in dense, interrelated datasets and efficient traversal. Property graphs provide a flexible representation, while graph-modeled indices support faster lookup.
- Database models: The article places graph databases among several database types, including document, triple/quad, and column stores, each targeting different data-management needs.The growing database landscape reflects varied application requirements rather than one universal solution.
- Database models: Graph databases are optimized for dense, interrelated datasets and support fast traversals along edges between vertices.Their typical data model is the property graph.
- Property graphs: Property graphs represent labeled vertices, labeled edges, and key/value attributes on both vertices and edges.They are directed, labeled, attributed, multi-graphs that can contain multiple edges between two vertices.
- Graph extensions: Graph databases can model indices within the graph structure itself because graph structures generalize tree-shaped indices.This allows graph traversal to serve as a unified framework for moving between elements and searching for them.
3 Jumping from Dot to Dot
Graph traversal is the foundation for graph algorithms and walks between vertices and edges. Gremlin illustrates traversal-based queries, including friend-of-a-friend paths, while property-graph labels require careful interpretation of algorithmic results.
- 3 Jumping from Dot to Dot: Graph traversal walks from vertex to edge to vertex while saving or manipulating graph information to compute algorithms.When traversal is the ultimate use case, graph databases are presented as the optimal storage solution.
- 3 Jumping from Dot to Dot: Gremlin expresses graph traversals as steps that move through vertices and edges, analogous to navigating a filesystem directory structure.The examples use Gremlin to demonstrate traversal behavior.
- 3 Jumping from Dot to Dot: A friend-of-a-friend traversal starts at a root vertex, follows outgoing friend-labeled edges twice, and returns the friends of its friends.The traversal filters edge labels and moves to each edge’s incoming vertex at both stages.
- 3 Jumping from Dot to Dot: The non-naïve friend-of-a-friend query excludes vertices that are already friends of the root by retaining information about previously located friends.Figure 6 distinguishes all friends-of-friends from those who are not also direct friends.
- 3 Jumping from Dot to Dot: Because property-graph edges are typed or labeled, standard algorithms for unlabeled graphs can produce ambiguous rankings and paths.The meaning of results depends on the different ways vertices may be related and the types of objects they represent.
- 3 Jumping from Dot to Dot: Evaluating a friend-of-a-friend expression yields a path that can be interpreted as a virtual, inferred, implicit, or derived edge.This reframes a multi-step traversal as a relationship between the root and the resulting vertices.
4 Conclusion
As graph data and real-world graph datasets have grown, graph databases and traversal frameworks have emerged to store, process, and use large-scale graphs.
- Internet-scale data has produced datasets reflecting graphs in technological and social systems.
- Graph databases address the need to handle and process these large-scale graphs.
- Traversal frameworks and algorithms extend graphs beyond explicit representation by shaping the evolution of modeled entities and relationships.