# US 2014/0156633 A1 · Scalable Multi-Query Optimization for SPARQL

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0156633 A1
- Document ID: US20140156633A1
- Status: Published application
- Kind: A1
- Application number: 13/691,666
- Filed: 2012-11-30
- Published: 2014-06-05
- Earliest claimed: 2012-11-30
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Songyun Duan; Anastasios Kementsietsidis; Wangchao Le; Feifei Li
- Web page: https://patentgrep.com/patent/US20140156633A1

## CPC

- G06F 16/24545: {Selectivity estimation or determination}
- G06F 16/2453: Query optimisation
- G06F 16/285: {Clustering or classification}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/24542: {Plan optimisation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Multiquery optimization is performed in the context of RDF/SPARQL. Heuristic algorithms partition an input batch of queries into groups such that each group of queries can be optimized together. The optimization incorporates an efficient algorithm to discover the common sub-structures of multiple SPARQL queries and an effective cost model to compare candidate execution plans. No assumptions are made about the underlying SPARQL query engine. This provides portability across different RDF stores.

## Claims

### Claim 1

A method for multi-query optimization, the method comprising:
identifying an input query set comprising a plurality of input queries over a given data set, each query comprising a graph pattern comprising at least one subject node, predicate edge and object node triple; and
clustering the plurality of input queries though incremental pair-wise merging based on structural similarities between graph patterns and query search cost optimization realized by a given merged graph pattern to generate an optimized query set comprising at least one query cluster.

### Claim 2 (depends on 1)

The method of claim 1, wherein clustering the plurality of inputs further comprises:
identifying a plurality of candidate merger inputs, each candidate merger input comprising an input query or an existing query cluster resulting from a previous pair-wise merging, a merger input graph pattern and a set of predicate edges contained in the merger input graph pattern; and
selecting a pair of merger inputs from the plurality of candidate merger inputs having a maximum overlap in the sets of predicate edges associated with the selected pair of merger inputs.

### Claim 3 (depends on 2)

The method of claim 2, wherein selecting the pair of merger inputs further comprises selecting a pair of merger inputs having a highest Jaccard similarity between the associated sets of predicate edges.

### Claim 4 (depends on 2)

The method of claim 2, wherein clustering the plurality of inputs further comprises generating a linegraph for each merger input in the selected pair of merger inputs by:
creating a linegraph node for each predicate edge in the set of predicate edges associated with the merger input;
identifying pairs of linegraph nodes where for each identified pair of linegraph nodes the subject node or object node contained in the merger input graph pattern and connected by a first predicate in that identified pair of linegraph nodes and the subject node or object node contained in the merger input graph pattern and connected by a second predicate in that identified pair of linegraph nodes comprise a common variable; and
creating linegraph edges between each identified pair of linegraph nodes.

### Claim 5 (depends on 4)

The method of claim 4, wherein clustering the plurality of inputs further comprises:
reducing a number of nodes in the generated linegraphs; and
using structural similarities among the nodes and edges of the generated linegraphs to determine if the merger input graphs patterns associated with the linegraphs should be merged.

### Claim 6 (depends on 5)

The method of claim 5, wherein:
creating linegraph edges between each identified pair of linegraph nodes further comprises creating a pair of linegraph edges extending in opposite directions between each identified pair of linegraph nodes, each linegraph edge in a given pair of linegraph edges comprising a label identifying a location of the common variable in the subject nodes and object nodes contained in the merger input graph pattern and connected by the predicates in that identified pair of linegraph nodes and a direction in which that linegraph edge extends between the linegraph nodes; and
reducing the number of nodes in the generated linegraphs further comprises:
associating a set of labels with each linegraph node, each set of labels comprising labels for all linegraph edges associated with a given linegraph node;
identifying sets of labels having less than a pre-determined threshold level of similarity with all other sets of labels; and
removing the linegraph nodes associated with the identified sets of labels from the linegraphs.

### Claim 7 (depends on 5)

The method of claim 5, wherein:
creating linegraph edges between each identified pair of linegraph nodes further comprises creating a pair of linegraph edges extending in opposite directions between each identified pair of linegraph nodes, each linegraph edge in a given pair of linegraph edges comprising a label identifying a location of the common variable in the subject nodes and object nodes contained in the merger input graph pattern and connected by the predicates in that identified pair of linegraph nodes and a direction in which that linegraph edge extends between the linegraph nodes; and
using structural similarities among the nodes and edges of the generated linegraphs further comprises:
associating a set of labels with each linegraph node, each set of labels comprising labels for all linegraph edges associated with a given linegraph node;
creating pairs of linegraph nodes by selecting a linegraph node from each linegraph;
determining an intersection between sets of labels associated with each created pair of linegraph nodes; and
using all determined intersections to determine if the merger input graph patterns associated with the linegraphs should be merged.

### Claim 8 (depends on 4)

The method of claim 4, wherein clustering the plurality of inputs further comprises combining the linegraphs generated for each merger input into a single product graph comprising a unique node for each combination of nodes from the linegraphs.

### Claim 9 (depends on 8)

The method of claim 8, wherein combining the linegraphs further comprises:
identifying a pairs of nodes to combine into a given unique node in the single product graph by selecting a single node from each linegraph that corresponds to an identical predicate in the merger input graph pattern associated with the linegraph containing that identified single node; and
using only the identified pairs of nodes corresponding to identical predicates in the single product graph.

### Claim 10 (depends on 9)

The method of claim 9, wherein:
creating linegraph edges between each identified pair of linegraph nodes further comprises:
creating a pair of linegraph edges extending in opposite directions between each identified pair of linegraph nodes, each linegraph edge in a given pair of linegraph edges comprising a label identifying a location of the common variable in the subject nodes and object nodes contained in the merger input graph pattern and connected by the predicates in that identified pair of linegraph nodes and a direction in which that linegraph edge extends between the linegraph nodes; and
associating a set of labels with each linegraph node, each set of labels comprising labels for all linegraph edges associated with a given linegraph node; and
combining the linegraphs further comprises combining the set of labels for the identified pairs of nodes corresponding to identical predicates in the single product graph.

### Claim 11 (depends on 8)

The method of claim 8, wherein clustering the plurality of inputs further comprises:
identifying a largest clique in the single product graph, the largest clique comprising a largest combined graph pattern obtainable from the merger input graph patterns of the selected pair of merger inputs; and
using a size of the largest clique to determine if the selected pair of merger inputs comprise sufficient structural similarities.

### Claim 12 (depends on 11)

The method of claim 11, wherein clustering the plurality of inputs further comprises:
identifying a plurality of candidate combined graph patterns obtainable from the merger input graph patterns if the largest combined graph pattern exceeds a predetermined size, each candidate combined graph pattern smaller than the largest combined graph pattern and representing a unique overlapping of the merger input graph patterns;
associating a search cost optimization realization level with each candidate combined graph pattern;
selecting the candidate combined graph pattern representing a most cost effective balance of merger input graph pattern overlap and search cost optimization realization level; and
using the selected candidate combined graph pattern to generate the optimized query set.

### Claim 13 (depends on 1)

The method of claim 1, the method further comprising:
evaluating the optimized query set over the data set to generate a set of query answers; and
parsing and distributing the set of query answers to the input queries in the input query set.

### Claim 14 (depends on 1)

The method of claim 1, wherein the input queries comprise SPARQL queries and the data set comprises a resource description framework dataset.

### Claim 15 (depends on 1)

The method of claim 1, wherein:
each input query comprises a set of predicate edges contained in its graph pattern;
the method further comprises:
identifying input queries having sufficiently similar sets of predicate edges; and
partitioning the input query set into a plurality of groups, each group comprising input queries having sufficiently similar sets of predicate edges; and
clustering the plurality of inputs further comprises clustering the input queries from one of the plurality of groups.

### Claim 16 (depends on 15)

The method of claim 15, wherein identifying input queries having sufficiently similar sets of predicate edges further comprises using Jaccard similarity between sets of predicates edges to identify the input queries.

### Claim 17

A computer-readable storage medium containing a computer-readable code that when read by a computer causes the computer to perform a method for multi-query optimization, the method comprising:
identifying an input query set comprising a plurality of input queries over a given data set, each query comprising a graph pattern comprising at least one subject node, predicate edge and object node triple; and
clustering the plurality of input queries though incremental pair-wise merging based on structural similarities between graph patterns and query search cost optimization realized by a given merged graph pattern to generate an optimized query set comprising at least one query cluster.

### Claim 18 (depends on 17)

The computer-readable storage medium of claim 17, wherein clustering the plurality of inputs further comprises:
identifying a plurality of candidate merger inputs, each candidate merger input comprising an input query or an existing query cluster resulting from a previous pair-wise merging, a merger input graph pattern and a set of predicate edges contained in the merger input graph pattern;
selecting a pair of merger inputs from the plurality of candidate merger inputs having a maximum overlap in the sets of predicate edges associated with the selected pair of merger inputs.

### Claim 19 (depends on 18)

The computer-readable medium of claim 18, wherein clustering the plurality of inputs further comprises generating a linegraph for each merger input in the selected pair of merger inputs by:
creating a linegraph node for each predicate edge in the set of predicate edges associated with the merger input;
identifying pairs of linegraph nodes where for each identified pair of linegraph nodes the subject node or object node contained in the merger input graph pattern and connected by a first predicate in that identified pair of linegraph nodes and the subject node or object node contained in the merger input graph pattern and connected by a second predicate in that identified pair of linegraph nodes comprise a common variable; and
creating linegraph edges between each identified pair of linegraph nodes.

### Claim 20 (depends on 19)

The computer-readable storage medium of claim 19, wherein clustering the plurality of inputs further comprises:
reducing a number of nodes in the generated linegraphs; and
using structural similarities among the nodes and edges of the generated linegraphs to determine if the merger input graphs patterns associated with the linegraphs should be merged.

### Claim 21 (depends on 20)

The computer-readable storage medium of claim 20, wherein:
creating linegraph edges between each identified pair of linegraph nodes further comprises creating a pair of linegraph edges extending in opposite directions between each identified pair of linegraph nodes, each linegraph edge in a given pair of linegraph edges comprising a label identifying a location of the common variable in the subject nodes and object nodes contained in the merger input graph pattern and connected by the predicates in that identified pair of linegraph nodes and a direction in which that linegraph edge extends between the linegraph nodes; and
reducing the number of nodes in the generated linegraphs further comprises:
associating a set of labels with each linegraph node, each set of labels comprising labels for all linegraph edges associated with a given linegraph node;
identifying sets of labels having less than a pre-determined threshold level of similarity with all other sets of labels; and
removing the linegraph nodes associated with the identified sets of labels from the linegraphs; and
using structural similarities among the nodes and edges of the generated linegraphs further comprises:
associating a set of labels with each linegraph node, each set of labels comprising labels for all linegraph edges associated with a given linegraph node;
creating pairs of linegraph nodes by selecting a linegraph node from each linegraph;
determining an intersection between sets of labels associated with each created pair of linegraph nodes; and
using all determined intersections to determine if the merger input graph patterns associated with the linegraphs should be merged.

### Claim 22 (depends on 19)

The computer-readable storage medium of claim 19, wherein clustering the plurality of inputs further comprises combining the linegraphs generated for each merger input into a single product graph comprising a unique node for each combination of nodes from the linegraphs by:
identifying a pairs of nodes to combine into a given unique node in the single product graph by selecting a single node from each linegraph that corresponds to an identical predicate in the merger input graph pattern associated with the linegraph containing that identified single node; and
using only the identified pairs of nodes corresponding to identical predicates in the single product graph.

### Claim 23 (depends on 22)

The computer-readable storage medium of claim 22, wherein:
creating linegraph edges between each identified pair of linegraph nodes further comprises:
creating a pair of linegraph edges extending in opposite directions between each identified pair of linegraph nodes, each linegraph edge in a given pair of linegraph edges comprising a label identifying a location of the common variable in the subject nodes and object nodes contained in the merger input graph pattern and connected by the predicates in that identified pair of linegraph nodes and a direction in which that linegraph edge extends between the linegraph nodes; and
associating a set of labels with each linegraph node, each set of labels comprising labels for all linegraph edges associated with a given linegraph node; and
combining the linegraphs further comprises combining the set of labels for the identified pairs of nodes corresponding to identical predicates in the single product graph.

### Claim 24 (depends on 22)

The computer-readable storage medium of claim 22, wherein clustering the plurality of inputs further comprises:
identifying a largest clique in the single product graph, the largest clique comprising a largest combined graph pattern obtainable from the merger input graph patterns of the selected pair of merger inputs; and
using a size of the largest clique to determine if the selected pair of merger inputs comprise sufficient structural similarities.

### Claim 25 (depends on 24)

The computer-readable storage medium of claim 24, wherein clustering the plurality of inputs further comprises:
identifying a plurality of candidate combined graph patterns obtainable from the merger input graph patterns if the largest combined graph pattern exceeds a predetermined size, each candidate combined graph pattern smaller than the largest combined graph pattern and representing a unique overlapping of the merger input graph patterns;
associating a search cost optimization realization level with each candidate combined graph pattern;
selecting the candidate combined graph pattern representing a most cost effective balance of merger input graph pattern overlap and search cost optimization realization level; and
using the selected candidate combined graph pattern to generate the optimized query set.