# US 11,907,255 B2 · Access-frequency-based entity replication techniques for distributed property graphs with schema > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,907,255 B2 - Document ID: US11907255B2 - Status: Granted - Kind: B2 - Application number: 17/686,938 - Filed: 2022-03-04 - Published: 2023-09-07 - Granted: 2024-02-20 - Earliest claimed: 2022-03-04 - Assignees: Oracle International Corporation - Applicants: Oracle International Corporation - Inventors: Jinsu Lee; Petr Koupy; Vasileios Trigonakis; Sungpack Hong; Hassan Chafi - Web page: https://patentgrep.com/patent/US11907255B2 ## CPC - G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor - G06F 16/2282: {Tablespace storage structures; Management thereof} - G06F 16/284: {Relational databases} - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract In an embodiment, multiple computers cooperate to retrieve content from tables in a relational database. Each table contains respective rows. Each row contains a vertex of a graph. Many high-degree vertices are identified. Each high-degree vertex is connected to respective edges in the graph. A count of the edges of each high-degree vertex exceeds a degree threshold. A central computer detects that all vertices in a high-degree subset of tables are high-degree vertices. Based on detecting the high-degree subset of tables, multiple vertices of the graph that are not in the high-degree subset of tables are replicated. Within local storage capacity limits of the computers, this degree-based replication may be supplemented with other vertex replication strategies that are schema based, content based, or workload based. This intelligent selective replication maximizes system throughput by minimizing graph data access latency based on data locality. ## Claims ### Claim 1 A computer-implemented method comprising: storing, in a relational database, a plurality of tables, wherein: each table of the plurality of tables contains a respective plurality of rows, and each row of the plurality of rows of each table contains a vertex of a graph; identifying a plurality of high-degree vertices, wherein: each high-degree vertex in the plurality of high-degree vertices is connected to a respective plurality of edges in the graph, and a count of the plurality of edges of each high-degree vertex exceeds a degree threshold; detecting that all vertices in a high-degree subset of tables of the plurality of tables are high-degree vertices; and replicating, based on said detecting all vertices in the high-degree subset of tables are high-degree vertices, a plurality of vertices of the graph that are not in the high-degree subset of tables to a plurality of computers. ### Claim 2 (depends on 1) The method of claim 1 wherein the plurality of vertices of the graph that are not in the high-degree subset of tables are in a connected subset of tables that are connected only to the high-degree subset of tables. ### Claim 3 (depends on 2) The method of claim 2 wherein said replicating the plurality of vertices of the graph that are in the connected subset of tables comprises sending, by each computer in the plurality of computers, for each vertex in the connected subset of tables: an identifier of the vertex, and a count of edges in the graph that are connected to the vertex. ### Claim 4 (depends on 3) The method of claim 3 wherein said sending, by each computer in the plurality of computers and for each vertex in the connected subset of tables, is in response to receiving, by each computer, a request that contains an identifier of each table in the connected subset of tables. ### Claim 5 (depends on 2) The method of claim 2 wherein said replicating the plurality of vertices of the graph that are in the connected subset of tables comprises inferring, from a schema of the relational database, that all vertices in a particular table that is not in the high-degree subset of tables can be connected by edges in the graph only to vertices in one selected from a group consisting of: one table of the high-degree subset of tables, and one or more tables of the high-degree subset of tables. ### Claim 6 (depends on 5) The method of claim 5 further comprising: inferring, from the schema of the relational database, that all vertices in a second table that is not in the high-degree subset of tables can be connected by edges in the graph only to vertices in the particular table; including the second table in the connected subset of tables. ### Claim 7 (depends on 2) The method of claim 2 further comprising: selecting a plurality of traversal paths that contain exactly three respective vertices in the graph that are connected by two respective edges in the graph, wherein for each traversal path in the plurality of traversal paths: the three respective vertices contains a respective first vertex in a first table that is in the connected subset of tables and a respective second vertex in a second table of the high-degree subset of tables, and the respective second vertex is connected to the two respective edges; calculating a ratio of a count of vertices in the first table to a count of traversal paths in the plurality of traversal paths, wherein said replicating the plurality of vertices of the graph that are in the connected subset of tables is based on said calculating the ratio of the count of vertices to the count of traversal paths. ### Claim 8 (depends on 2) The method of claim 2 further comprising based on executions of a plurality of queries, for each accessed table of the plurality of tables, detecting a respective usage count selected from a group consisting of: a count of said executions that reference the accessed table, a count of operators that reference the accessed table in execution plans of the plurality of queries, and a count of table scans of the accessed table. ### Claim 9 (depends on 1) The method of claim 1 further comprising decreasing a remaining vertex capacity by a count of the plurality of high-degree vertices in the graph. ### Claim 10 (depends on 9) The method of claim 9 wherein said replicating the plurality of vertices of the graph that are not in the high-degree subset of tables comprises limiting, based on the remaining vertex capacity, a count of vertices to be replicated that are not in the high-degree subset of tables. ### Claim 11 (depends on 10) The method of claim 10 wherein said limiting the count of vertices to be replicated that are not in the high-degree subset of tables comprises sorting, by degree, multiple vertices in multiple tables that are not in the high-degree subset of tables. ### Claim 12 (depends on 10) The method of claim 10 further comprising detecting, before said limiting the count of vertices to be replicated that are not in the high-degree subset of tables, that the remaining vertex capacity is positive. ### Claim 13 (depends on 1) The method of claim 1 wherein said detecting all vertices in the high-degree subset of tables are high-degree vertices comprises: distributing a respective subset of all vertices in a particular table to each computer in the plurality of computers; detecting, by each computer in the plurality of computers, that the respective subset of said all vertices in the particular table contains only high-degree vertices. ### Claim 14 (depends on 13) The method of claim 13 wherein said detecting that all vertices in the particular table are high-degree vertices comprises sending, to a central computer by each computer in the plurality of computers, an indication that the respective subset of said all vertices in the particular table contains only high-degree vertices. ### Claim 15 (depends on 14) The method of claim 14 wherein the indication for the particular table contains an identifier of the particular table. ### Claim 16 One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause: storing, in a relational database, a plurality of tables, wherein: each table of the plurality of tables contains a respective plurality of rows, and each row of the plurality of rows of each table contains a vertex of a graph; identifying a plurality of high-degree vertices, wherein: each high-degree vertex in the plurality of high-degree vertices is connected to a respective plurality of edges in the graph, and a count of the plurality of edges of each high-degree vertex exceeds a degree threshold; detecting that all vertices in a high-degree subset of tables of the plurality of tables are high-degree vertices; and replicating, based on said detecting all vertices in the high-degree subset of tables are high-degree vertices, a plurality of vertices of the graph that are not in the high-degree subset of tables to a plurality of computers. ### Claim 17 (depends on 16) The one or more non-transitory computer-readable media of claim 16 wherein the plurality of vertices of the graph that are not in the high-degree subset of tables are in a connected subset of tables that are connected only to the high-degree subset of tables. ### Claim 18 (depends on 16) The one or more non-transitory computer-readable media of claim 16 wherein the instructions further cause decreasing a remaining vertex capacity by a count of the plurality of high-degree vertices in the graph. ### Claim 19 (depends on 18) The one or more non-transitory computer-readable media of claim 18 wherein said replicating the plurality of vertices of the graph that are not in the high-degree subset of tables comprises limiting, based on the remaining vertex capacity, a count of vertices to be replicated that are not in the high-degree subset of tables. ### Claim 20 (depends on 16) The one or more non-transitory computer-readable media of claim 16 wherein said detecting all vertices in the high-degree subset of tables are high-degree vertices comprises: distributing a respective subset of all vertices in a particular table to each computer in the plurality of computers; detecting, by each computer in the plurality of computers, that the respective subset of said all vertices in the particular table contains only high-degree vertices.