Oracle International Corporation

Oskar Van Rest

Hassan Chafi

Sungpack Hong

Vlad Ioan Haprian

Jinha Kim

Vasileios Trigonakis

Alexander Weld

Damien Hilloulin

Davide Bartolini

Xuming Meng

Jean-Pierre Lozi

Korbinian Schmid

Iraklis Psaroudakis

Tomas Faltin

Arnaud Delamare

Yahya Ez-Zainabi

Raghavan Raman

Florian Gratzer

Steven Serra

Bence Czipo

Techniques are provided herein for efficient representation of heterogeneous graphs in memory. In an embodiment, vertices and edges of the graph are segregated by type. Each property of a type of vertex or edge has values stored in a respective vector. Directed or undirected edges of a same type are stored in compressed sparse row (CSR) format. The CSR format is more or less repeated for edge traversal in either forward or reverse direction. An edge map translates edge offsets obtained from traversal in the reverse direction for use with data structures that expect edge offsets in the forward direction. Subsequent filtration and/or traversal by type or property of vertex or edge entails minimal data access and maximal data locality, thereby increasing efficient use of the graph.

Efficient, in-memory, relational representation for heterogeneous graphs

A method, apparatus, and product to provide a parser for property graph queries with precise error reporting and auto-completion based on information from property graph schemas. The approach generally comprises analysis of graph queries prior to their execution to identify issues prior to execution. In some embodiments, the approach includes any of: use of a property graph schema to determine whether names in a received property graph query exist within a corresponding property graph; determining whether the property graph query includes a comparison of mismatched data types; providing an autocomplete suggestion feature for assistance in resolving errors or corresponding to a cursor position within a query string; or evaluation of a property graph query to determine whether it would return an empty result. In some embodiments, property graph query analysis is performed using a context aware approach.

Method, product, and system to provide a parser for property graph queries with precise error reporting and auto-completion based on information from property graph schemas

Efficiently implemented herein is a deterministic semantic for property updates by graph queries. Mechanisms of determinism herein ensure data consistency for graph mutation. These mechanisms facilitate optimistic execution of graph access despite a potential data access conflict. This approach may include various combinations of special activities such as detecting potential conflicts during query compile time, applying query transformations to eliminate those conflicts during code generation where possible, and executing updates in an optimistic way that safely fails if determinism cannot be guaranteed. In an embodiment, a computer receives a request to modify a graph. The request to modify the graph is optimistically executed after preparation and according to safety precautions as presented herein. Based on optimistically executing the request, a data access conflict actually occurs and is automatically detected. Based on the data access conflict, optimistically executing the request is prematurely and automatically halted without finishing executing the request.

Deterministic semantic for graph property update queries and its efficient implementation

Techniques herein accelerate graph querying by caching neighbor vertices (NVs) of super-node vertices. In an embodiment, a computer receives a graph query (GQ) to extract result paths from a graph in a database. The GQ has a sequence of query vertices (QVs) and a sequence of query edges (QEs). The computer successively traverses each QE and QV to detect paths of the graph that match the GQ. Traversing each QE and QV entails retrieving NVs of a current graph vertex (CGV) of a current traversal path. If the CGV is a key in a cache whose keys are graph vertices having an excessive degree, then the computer retrieves NVs from the cache. Otherwise, the computer retrieves NVs from the database. If the degree is excessive, and the CGV is not a key in the cache, then the computer stores, into the cache, the CGV as a key for the NVs.

Fast graph query engine optimized for typical real-world graph instances whose small portion of vertices have extremely large degree

Techniques are described herein for space-efficient encoding of label information of property graphs. In an embodiment, an input graph is received. The input graph comprises a plurality of entities and a plurality of label sets. Each entity of said plurality of entities is associated with a label set of the plurality of label sets and each label set of the plurality of label sets comprises zero or more labels of a plurality of labels. A first mapping is generated that maps each label of the plurality of labels to a label code. A second mapping is generated that maps each label integer set of a plurality of label integer sets to a label code. Each label integer set of the plurality of label integer sets corresponds to a label set of the plurality of label sets, wherein each label integer set of the plurality of label integer sets comprises label codes from the first mapping that are mapped to each label included in the corresponding label set. A compressed label set is generated for each entity of the plurality of entities. Each compressed label set comprises a plurality of bits that indicate a zeroth state, a first state, a second state, or a third state. The compressed label sets and the first and second mappings are used to efficiently evaluate graph label queries.

Space-efficient methodology for representing label information in large graph data for fast distributed graph query

Techniques are described for generating and re-using reachability graphs for efficient execution of queries. In an embodiment, a query is received for execution on a data graph. Such a query may include one or more expressions for edges in the data graph, which when executed select one or more paths in the data graph to generate results for the query. The system uses a repository to store reachability graphs and may determine whether a reachability graph for an expression of the query for the data graph is stored in a repository. Such a reachability graph is generated by applying the expression on the data graph to qualify or disqualify the edges in the data graph to be included as part of edges of the reachability graph. For example, an edge in a reachability graph exists between two vertices when at least one edge of the data graph has qualified between two vertices of the data graph that correspond to the two vertices of the reachability graph. Based on determining that the reachability graph for the expression is stored in the repository, the system executes the query on the reachability graph without re-applying the expression on the data graph and generates the results for the query.

Reachability graph index for query processing

Techniques herein optimize subgraph pattern matching. A computer receives a graph vertex array and a graph edge array. Each vertex and each edge has labels. The computer stores an array of index entries and an array of edge label sets. Each index entry corresponds to a respective vertex originating an edge and associates an offset of the edge with an offset of the respective vertex. Each edge label set contains labels of a respective edge. The computer selects a candidate subset of edges originating at a current vertex. The edge labels of each candidate edge of the candidate subset include a same particular query edge labels. The computer selects the candidate subset based on the index array and afterwards selects a result subset of vertices from among the terminating vertices of the candidate edges. The labels of each vertex of the result subset include a same particular query vertex labels.

Efficient method for subgraph pattern matching

Techniques are described herein for allocating and rebalancing computing resources for executing graph workloads in manner that increases system throughput. According to one embodiment, a method includes receiving a request to execute a graph processing workload on a dataset, identifying a plurality of graph operators that constitute the graph processing workload, and determining whether execution of each graph operator is processor intensive or memory intensive. The method also includes assigning a task weight for each graph operator of the plurality of graph operators, and performing, based on the assigned task weights, a first allocation of computing resources to execute the plurality of graph operators. Further, the method includes causing, according to the first allocation, execution of the plurality of graph operators by the computing resources, and monitoring computing resource usage of graph operators executed by the computing resources according to the first allocation. In addition, the method includes performing, responsive to monitoring computing resource usage, a second allocation of computing resources to execute the plurality of graph operators, and causing, according to the second allocation instead of according to the first allocation, execution of the plurality of graph operators by the computing resources.

Efficient resource allocation for concurrent graph workloads

Techniques herein are for fast processing of path-finding queries in large graph databases. A computer system receives a graph search request to find a set of result paths between one or more source vertices of a graph and one or more target vertices of the graph. The graph comprises vertices connected by edges. During a first pass, the computer system performs one or more breadth-first searches to identify a subset of edges of the graph. The one or more breadth-first searches originate at the one or more source vertices. After the first pass and during a second pass, the computer system performs one or more depth-first searches to identify the set of result paths. The one or more depth-first searches originate at the one or more target vertices. The one or more depth-first searches traverse at most the subset of edges of the graph.

Fast processing of path-finding queries in large graph databases

Techniques herein are for query editing with semantic analysis of a query based on information extracted from a tuple graph. In an embodiment, a computerized method involves processing a dataset to extract an extracted schema that describes types and relationships that occur within the dataset. The dataset is not associated with a schema that is not contained in the dataset. The dataset has a graph of tuples. During an incremental parse, an abstract syntax tree (AST) that represents a query is modified. The extracted schema and the dataset are used to perform semantic analysis on the AST. In an embodiment, the tuples are resource description framework (RDF) triples. In an embodiment, the RDF triples include RDF schema statements. Extracting an extracted schema involves processing RDF schema statements. In an embodiment, the query is a SPARQL query and semantic analysis includes error alerting and code completion.

Growing community of inventors

Mountain View, CA, United States of America

Oskar Van Rest