Back to results
US 10,095,742 B2Granted
Scalable multi-query optimization for SPARQL
AssigneeInternational Business Machines Corporation
InventorsSongyun Duan, Anastasios Kementsietsidis, Wangchao Le, Feifei Li
Life of this patent
Estimating the term…
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.
Claims15
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 input query comprising subject nodes, object nodes and a set of predicate edges;
- partitioning the plurality of input queries by:
- identifying a plurality of groups of input queries, each group of input queries comprising input queries from the plurality of input queries;
- determining a Jaccard similarity for the sets of predicates edges for queries in each one of a plurality of potential groups of input queries;
- and
- including in the plurality of groups of input queries only those potential groups of input queries where the Jaccard similarity indicates a substantial overlap in the sets of predicate edges associated with the input queries in a given group of input queries;
- and
- rewriting queries in each group from a first type of query that selects results based on a set of triple patterns to a second type of query that selects results based on the set of triple patterns in combination with at least one set of optional triple patterns by merging queries in each group of queries having structurally similar sub-queries using hierarchical clustering to generate a plurality of query clusters, each query cluster comprising the second type of query.
5 more elements
A computer-readable storage medium containing a computer-readable code that when read by a computer case 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 input query comprising subject nodes, object nodes and a set of predicate edges;
- partitioning the plurality of input queries by:
- identifying a plurality of groups of input queries, each group of input queries comprising input queries from the plurality of input queries;
- determining a Jaccard similarity for the sets of predicates edges for queries in each one of a plurality of potential groups of input queries;
- and
- including in the plurality of groups of input queries only those potential groups of input queries where the Jaccard similarity indicates a substantial overlap in the sets of predicate edges associated with the input queries in a given group of input queries;
- and
- rewriting queries in each group from a first type of query that selects results based on a set of triple patterns to a second type of query that selects results based on the set of triple patterns in combination with at least one set of optional triple patterns by merging queries in each group of queries having structurally similar sub-queries using hierarchical clustering to generate a plurality of query clusters, each query cluster comprising the second type of query.
5 more elements
A system for multi-query optimization over a given data set, the system comprising:
- a database in communication with a network, the database comprising an input query set comprising a plurality of input queries over a given data set, each input query comprising subject nodes, object nodes and a set of predicate edges;
- and
- a computing system in communication with the database and the given dataset, the computing system comprising:
- a partitioning module to partition the plurality of input queries by identifying a plurality of groups of input queries, each group of input queries comprising input queries from the plurality of input queries, and the sets of predicate edges associated with the input queries in a given group of input query have a sufficient number of predicates in common to be substantially overlapping;
- and
- a clustering module to:
- rewrite queries in each group from a first type of query that selects results based on a set of triple patterns to a second type of query that selects results based on the set of triple patterns in combination with at least one set of optional triple patterns;
- and
- merge queries in each group of queries having structurally similar sub-queries using hierarchical clustering to generate a plurality of query clusters, each query cluster comprising the second type of query by:
- generating a singleton cluster for each query in each group of queries;
- determining a cost associated with merging any two singleton clusters in each query into single combined cluster corresponding to a single second type of query by determining an optimized query cost resulting from an optimized query generated by merging any two singleton clusters;
- and merging only singleton clusters where the cost associated with merging indicates that merging is cost-effective for optimizing multi-query processing by:
- obtaining a cost of performing queries for each individual singleton cluster;
- and
- comparing the cost of performing queries for each individual singleton cluster with the optimized query cost.
12 more elements
Dependencies are inferred from the claim text.