Islands technique of graph synthesis

A system for generating schema-constrained synthetic property graph data for use in a database schema or data architecture, the system comprising:

• a processor;
• and
• a memory storing instructions that, when executed by the processor, cause the system to:
• define an islands schema that functions as a type system for a property graph, the islands schema specifying archipelago structures, vertex types, edge types, property constraints, probabilistic parameters, and joining rules, wherein each archipelago structure comprises a root vertex type and zero or more additional vertex types;
• for each vertex type specified by the islands schema, define zero or more potential property keys, a likelihood that each potential property key is created, a value generator class for generating a property value for a created property key, and configuration parameters for the value generator class, wherein the configuration parameters constrain generated property values;
• for each edge type specified by the islands schema, define an in-vertex type, an out-vertex type, zero or more potential edge property keys, a likelihood value between 0.0 and 1.0 for creating the edge type, a number of chances to create the edge type, and an indication of whether the edge type is created during an initial archipelago generation phase or during a stitching phase;
• generate, during the initial archipelago generation phase, a plurality of disconnected archipelagos in parallel according to the islands schema by executing a generator function that maps values in a numeric range to corresponding generated archipelagos;
• for each disconnected archipelago of the plurality of disconnected archipelagos, create a root vertex of the root vertex type specified for the disconnected archipelago and recursively generate connected vertices and edges from the root vertex according to the vertex types, edge types, likelihood values, numbers of chances to create, property keys, value generator classes, and configuration parameters specified in the islands schema;
• wherein, to recursively generate the connected vertices and edges, the instructions cause the system to evaluate each potential property key for a vertex according to the likelihood specified for the potential property key, call the value generator class associated with the potential property key when the potential property key is selected, generate a property value constrained by the configuration parameters associated with the value generator class, evaluate edge types referenced by the vertex type of the vertex being generated, and determine whether to create each potential edge according to the likelihood value and the number of chances to create specified for the corresponding edge type;
• push edge creation operations onto a stack and push vertex creation operations onto the stack above corresponding edge creation operations, such that vertices are generated before connecting edges associated with the vertices are written;
• transform nested lists of return values generated during the initial archipelago generation phase into sequential streams per disconnected archipelago;
• stitch the plurality of disconnected archipelagos together during the stitching phase by identifying, from the islands schema, joining edge types that were not processed during the initial archipelago generation phase;
• for each joining edge type, set up a pair of streams that read previously materialized vertices of the in-vertex type and the out-vertex type associated with the joining edge type;
• implement a probabilistic zip function that pairs a first vertex read from a first stream of the pair of streams with a second vertex read from a second stream of the pair of streams, weights a probabilistic determination using data from the first vertex, data from the second vertex, and the islands schema, and determines whether to create a joining edge between the first vertex and the second vertex;
• create additional edges between vertices of different disconnected archipelagos according to the probabilistic zip function and the joining rules specified in the islands schema;
• generate property values for the additional edges according to value generator classes and configuration parameters specified for the joining edge types in the islands schema;
• validate property values generated for vertices and edges against constraints specified in the islands schema;
• and
• maintain counts of generated edges of each edge type to determine consistency of the generated schema-constrained synthetic property graph data with the islands schema;
• wherein separation of the initial archipelago generation phase from the stitching phase enables the plurality of disconnected archipelagos to be generated independently in parallel while preserving schema-defined vertex types, edge types, property constraints, local archipelago structures, and cross-archipelago joining relationships in the schema-constrained synthetic property graph data.