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.
Claims25
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.
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.
Dependencies are inferred from the claim text.