Physical Schema

The core component dictating how graph elements are serialized and persisted. This includes the on-disk file structure (e.g., adjacency lists, compressed sparse rows) and the binary format for nodes, edges, and properties. Choices here directly impact write amplification, compression ratios, and cache locality. For example, a system using index-free adjacency will store direct pointers to neighboring nodes, while others may use indexed lookups.

Defines the auxiliary data structures created to accelerate specific query patterns without scanning the entire graph. Common index types include:

• Label/Type Indexes: For fast retrieval of all nodes with a given label.
• Property Indexes: B-tree or hash indexes on specific property values (e.g., Person.name).
• Composite Indexes: On multiple properties.
• Full-Text Search Indexes: For text property content.
• Spatial Indexes: For geospatial queries. The physical schema specifies which indexes are created, their structure, and update policies.

Determines how the graph is divided across multiple machines or disks in a distributed system. This is critical for horizontal scalability. Strategies include:

• Vertex-Cut Partitioning: Edges are partitioned, and vertices are replicated.
• Edge-Cut Partitioning: Vertices are partitioned, and edges crossing partitions create network overhead.
• Property Graph Sharding: Sharding by label or a key property (e.g., tenant_id). The physical schema defines the partitioning key, replication factor, and data locality rules.

Specifies how graph data is loaded and managed in RAM. This includes:

• Page Cache Configuration: Size and eviction policies for disk blocks.
• Hot Data Caching: Prioritizing certain subgraphs (e.g., recent transactions) in memory.
• Buffer Pool Management: For managing concurrent access to in-memory data pages.
• Off-Heap Memory Allocation: For storing large property values or vector embeddings separately. These settings directly control latency and throughput for traversal-heavy workloads.

The low-level implementation of data integrity and isolation guarantees. This component details:

• Locking Granularity: Row-level vs. page-level vs. graph-level locks.
• Multi-Version Concurrency Control (MVCC): How transaction snapshots and version chains are stored.
• Write-Ahead Logging (WAL): The format and flush policy for crash recovery.
• ACID Compliance Boundaries: What is guaranteed within a single partition vs. across the cluster. This ensures predictable behavior under concurrent load.

Defines the algorithms used to reduce the physical storage footprint of the graph. This includes:

• Property Value Encoding: Using dictionary encoding for repetitive string values (e.g., city names).
• Delta Encoding: Storing only the difference between sequential numeric IDs.
• Bit-Packing: For small integer properties.
• General-Purpose Compression: Applying LZ4 or Zstd to entire data pages. Effective compression reduces I/O and increases effective cache size but adds CPU overhead for decompression.

A logical schema is an abstract, implementation-independent data model that defines the structure and meaning of data. It specifies entity types, relationship types, attributes, and constraints without detailing storage mechanisms. It serves as the blueprint from which a physical schema is derived.

• Purpose: Focuses on what the data represents, not how it is stored.
• Example: Defining that a Customer entity has a name (string) and customerId (integer), and can PURCHASED a Product.
• Contrast: The logical schema is database-agnostic, while the physical schema is specific to Neo4j, Amazon Neptune, or another system.

A graph schema language is a formal syntax for defining the structure and constraints of a graph. It is the primary tool for declaring a physical schema.

• Property Graph Examples:
  • Cypher's CREATE CONSTRAINT: Used in Neo4j to enforce uniqueness and existence.
  • Apache TinkerPop's Gremlin Schema: Allows definition of vertex/edge labels, property keys, and cardinality.
• RDF Examples:
  • SHACL (Shapes Constraint Language): A W3C standard for validating RDF graphs against a set of conditions (shapes).
  • OWL (Web Ontology Language): Used to define complex ontological constraints and inferences.
• Function: Translates logical design into executable database directives.

Index-free adjacency is a native graph storage design principle where connected nodes contain direct physical pointers to each other. This is a critical physical schema decision that optimizes traversal performance.

• Mechanism: A node stores the memory addresses or disk locations of its adjacent relationships and neighbor nodes.
• Performance Impact: Enables O(1) hop traversals, as the query engine follows pointers rather than performing index lookups for each step in a path.
• Trade-off: Optimizes for local graph navigation at the potential cost of global queries, which still require indexes. It defines the fundamental storage layout of the physical schema.

Graph partitioning is the physical process of dividing a large graph into smaller subgraphs (shards) to distribute data across a cluster. It is a core aspect of scaling a physical schema.

• Objective: To minimize cross-machine communication (edge cuts) while balancing load.
• Strategies:
  • Edge-Cut: Vertices are assigned to partitions; edges crossing partitions create network overhead.
  • Vertex-Cut: Edges are assigned to partitions; vertices are replicated across partitions.
• Impact on Queries: Determines whether a traversal can be executed locally on one machine or requires expensive distributed coordination. The partitioning strategy is a first-class element of the physical schema for distributed graph databases.

Schema evolution is the process of modifying a database's schema over time. For a physical graph schema, this involves managing changes while ensuring data integrity and backward compatibility.

• Common Operations:
  • Additive: Introducing new vertex/edge labels, property keys, or indexes (generally safe).
  • Transformative: Changing property data types, splitting/merging labels, or enforcing new constraints (requires data migration).
  • Destructive: Removing labels or properties (risks breaking existing queries).
• Tooling: Requires version-controlled schema scripts, data migration utilities, and potentially schema mapping tools to transform existing data to fit the new schema.

Schema validation is the process of verifying that the actual data instances in a graph conform to the rules defined in its physical schema. It ensures data quality and integrity.

• Validation Mechanisms:
  • Native Database Constraints: Uniqueness, property type, and existence constraints enforced at write-time (e.g., Neo4j constraints).
  • SHACL Validation: For RDF triplestores, SHACL processors check that an RDF graph conforms to a set of shapes defining allowed structure and values.
  • Application-Level Checks: Custom logic executed before or after data ingestion.
• Outcome: Produces validation reports listing violations, which guide data cleansing and pipeline corrections. It is the operational enforcement of the physical schema.