Chapter 02Property Graph Databases
Property graph databases are commonly situated within the broader NoSQL landscape, although NoSQL denotes a diverse family of systems rather than a single formal data model (Sadalage and Fowler 2012). They are designed for situations in which connections between data items are just as important as the items themselves. Instead of thinking in terms of tables, rows, and foreign keys, they invite us to view data as a graph: a network of entities and the relationships that link them. In contrast to traditional relational databases, which are table-oriented, and document stores, which are collection-oriented, property graph databases are relationship-oriented. Their central idea can be summarized as follows: if the problem you are solving is fundamentally about connections, then your database model should reflect that fact.
The core abstraction of a property graph database is a labeled, attributed multigraph that may contain directed and undirected edges. In practical terms, this means that the database is built around nodes and edges that are both richly described and explicitly connected. Nodes, sometimes called vertices, represent entities in the domain: a person, a company, a product, a city, a bank account, a research paper, a device, or any other identifiable object. Each node can carry zero or more labels that classify it, such as Person, Customer, Company, Movie, Paper, or Device. Labels group nodes into sets and are used heavily in queries and indexing. It is common, for example, for a single node to have both Person and Customer labels, which captures polymorphism in the domain in a very natural way.
Edges, often referred to as relationships, connect pairs of nodes and may be directed or undirected. They express facts such as that one person is friends with another, that a customer has purchased a product, that an author has written a paper, or that a server relies on a particular service. Every edge has two endpoints and a directionality; a directed edge additionally distinguishes its source from its destination. Each edge has an edge label set; its labels classify the edge, for example, FRIENDS_WITH, PURCHASED, LIVES_IN, WORKS_FOR, WROTE, or CITES. An edge label does not by itself constitute an edge type. In GQL, the minimum and maximum cardinalities of an edge label set are implementation-defined, so an implementation may limit such a set to at most one label. Property graph databases are multigraphs, so multiple edges with possibly different label sets can connect the same pair of nodes. One person might both WORKS_FOR and INVESTED_IN the same company, or two papers might both CITES and EXTEND each other through different relationships that are relevant for different analyses. Crucially, edges are first-class citizens: they are stored natively, have their own identity, and can bear data just like nodes.
The term “property graph” refers to the fact that both nodes and edges carry properties, which are key-value pairs that describe the attributes of those elements. A Person node might have properties such as name, age, and email, while a Product node might have properties such as name, category, and price. Property values are typically typed: strings, numbers, booleans, temporal values, and often also collections such as lists and maps. A list property might store several tags, and a map property might capture structured metadata. A key differentiator from many other models is that edges can also possess properties. For instance, a PURCHASED relationship might record the timestamp of the transaction, the quantity, and the price paid; a FRIENDS_WITH relationship might store the date the friendship started or a measure of connection strength; a WROTE edge could record the contribution percentage of a particular coauthor. This ability to attach rich metadata directly to relationships allows the graph to capture not only that two entities are connected, but also how, when, and to what degree they are connected.
Node and edge labels play a central role in how property graphs are queried and optimized. Node labels, such as Person or Movie, and edge labels, such as ACTED_IN or DIRECTED, allow the system to index and constrain subsets of the graph efficiently. Queries can start from all nodes labeled Customer, or follow only edges carrying the label LIVES_IN, or enforce constraints so that every node with label Account has an accountNumber property and appropriate indexes on it. Multi-label nodes enable the modeling of heterogeneous or overlapping categories without requiring schema modifications. Similarly, labeled edges make the domain’s structure clear and expressive at the database level.
Sometimes, beyond individual nodes and edges, property graph databases treat paths as first-class concepts. A path is a sequence of alternating nodes and edges that represents a traversable route through the graph. Many queries are really questions about such paths: whether any path exists between two entities, what the shortest path is, whether there is a path whose labels match a certain pattern, or how many distinct paths of a particular shape can be found. Property graph systems typically offer built-in support for reachability queries, shortest path computations, and regular path queries that constrain the allowed sequence of edge-label tests. In some systems, entire paths, not just their endpoints, can be returned and manipulated as query results, which is vital for tasks such as explaining recommendations or tracing the provenance of data.
Interacting with a property graph database typically involves specialized graph query languages designed for pattern matching and path navigation. Cypher is the most widely known example, originally created for Neo4j and one of the principal precursors of the standardized GQL (International Organization for Standardization 2024) that is the subject of this book. Cypher uses an ASCII-art-inspired syntax, in which nodes appear in parentheses and relationships in brackets, with arrows, so that queries visually resemble the structures they match. For instance, a pattern resembling (p:Person)-[:PURCHASED]->(pr:Product) expresses a person purchasing a product. Queries specify not only which patterns to match, but also which properties to filter on and how to shape the returned results as nodes, edges, paths, or aggregates. Other systems offer similar capabilities, but the common theme is that the primary unit of querying is not a table but a graph pattern. Many property graph databases offer ACID transactions, allowing graph updates and queries to participate in familiar transactional workflows with guarantees of atomicity, consistency, isolation, and durability.
From a performance perspective, property graph databases are engineered to excel at graph-shaped workloads. They commonly maintain indexes over nodes to provide fast entry points for traversals, and sometimes over relationships as well. Once a set of starting nodes has been found, queries typically proceed by following adjacency lists, that is, by exploring the edges attached to those nodes. Storage layouts are optimized so that related nodes and edges are stored physically close together, which reduces the cost of following relationships. The result is that the cost of a query tends to be proportional to the amount of the graph that is actually traversed, rather than to the total size of the database. Deep traversals, which might require several joins in an RDBMS (Relational Database Management System), become straightforward pattern matches that remain efficient as the graph grows. Many systems also integrate or expose graph algorithms such as centrality measures, community detection, and various forms of path finding, making complex analytics on connectivity a routine part of querying.
Often, flexibility in schema is another hallmark of property graph databases. The model is schema-optional: although constraints and indexes can and often should be defined, the system does not require a rigid, global schema in the same way that a relational database does. New node and edge labels and properties can be introduced incrementally without disrupting existing data; where a constraining graph type is used, its node and edge types must be changed accordingly. This makes property graphs particularly attractive in evolving domains where data structures are not fully known in advance or where they change rapidly under business pressure. Developers can start with a simple model and refine it over time, adjusting new relationships and attributes as their understanding of the system deepens.
2.1 Use Cases and Real-World Applications
The expressive power and performance characteristics of property graph databases make them especially well-suited to a range of application domains where connected data is central. Social networks are perhaps the most intuitive example, with users linked by friendships, follows, group memberships, likes, and content interactions. Features such as “people you may know” or “mutual friends” become simple graph traversals that look for certain patterns among paths of length two or three. Recommendation engines in e-commerce and media services utilize paths that connect users, products, ratings, and categories to suggest items that are similar or complementary. Fraud detection in banking and financial services benefits significantly from viewing accounts, devices, transactions, and merchants as a graph and identifying suspicious substructures, such as rings of accounts, unusual transaction paths, or clusters that match known fraud patterns.
Knowledge graphs form another major category of applications. Large technology companies use massive property graphs to connect facts about people, organizations, places, events, and abstract concepts, providing the backbone for search engines and digital assistants. In an enterprise context, knowledge graphs integrate data from multiple systems, enabling analysts to navigate from a customer to contracts, interactions, products, support tickets, and payments within a single, coherent structure. Master data management similarly utilizes property graphs to link and reconcile multiple representations of the same real-world entity across different systems, thereby building a unified view of customers, products, or locations. Network and IT operations benefit from modeling infrastructure as a graph of devices, services, dependencies, and communication flows, enabling impact analysis when a component fails and supporting change planning. Identity and access management can be expressed as a graph of users, groups, roles, resources, and permissions, which makes it much easier to answer questions such as who effectively has access to which system through what chain of assignments.
Beyond these now classical domains, there are many specialized areas where property graphs have proven effective. Supply chain management uses graphs to represent suppliers, parts, products, logistics routes, and dependencies, allowing organizations to assess risk and analyze the impact of disruptions. Biomedical and bioinformatics applications build graphs of genes, proteins, interactions, pathways, and phenotypes to support discovery and hypothesis generation. Healthcare providers can model patients, diagnoses, treatments, and outcomes as a graph that helps to identify treatment patterns or adverse interactions. Cybersecurity teams maintain cyber threat graphs that link assets, vulnerabilities, exploits, and attackers to support threat hunting and incident response. Dependency and impact analysis in software engineering and manufacturing can utilize property graphs to represent components and their relationships within a bill of materials, enabling the tracing of consequences of a defect or vulnerability across a complex system.
Although each of these applications can be implemented with a relational database, a conventional relational schema represents connections through foreign-key values and association tables rather than stored, identity-bearing edges. Multi-hop, variable-length, or topology-driven questions therefore require chains of joins or recursive queries that reconstruct those connections, making such queries less direct as the traversed shape grows or varies. Property graphs do not displace relational systems for tabular workloads; they make relationships and traversal first-class, which aligns more closely with the connectivity-centered uses above (Sadalage and Fowler 2012).
2.2 Limitations of Property Graph Databases
Despite their strengths, property graph databases are not a universal solution and come with their own trade-offs. For workloads that consist primarily of simple, flat data with few relationships, a traditional relational database or a document store may be more straightforward and resource-efficient. Analytics that require scanning very large proportions of the data for aggregation, rather than traversing specific paths, can often be executed more effectively in columnar or data warehouse systems that are optimized for such scans. The explicit storage of edges, together with rich properties on both nodes and edges, can introduce storage overhead compared to a highly normalized relational design. Distributing a graph across multiple machines is also challenging because the natural structure of a graph does not always align with clean partitions, and traversals may need to cross physical boundaries, raising the cost of some queries and complicating the design of sharding strategies.