Back to results
US 9,542,444 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.
Claims16
A system for multi-query optimization over a given data set, the system comprising:
- a hardware memory comprising a database in communication with a network, the database comprising an input query set comprising a plurality of input queries over the given data set across the network, each input query comprising a graph pattern comprising at least one subject node, predicate edge and object node triple and a set of predicate edges contained in its graph pattern;
- and
- a computing system in communication with the database and the given dataset, the computing system comprising:
- a computer processor;
- a clustering module to cluster the plurality of input queries through 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;
- and
- a partitioning module to identify input queries having sufficiently similar sets of predicate edges and to partition the input query set into a plurality of groups, each group comprising input queries having sufficiently similar sets of predicate edges;
- wherein the clustering module clusters the plurality of input queries by using linegraphs, each linegraph comprising:
- linegraph nodes, each linegraph node corresponding to a given predicate edge in the input queries;
- linegraph edges between pairs of linegraph nodes that are associated with predicate edges sharing at least one of a common subject node and a common object node in the input queries;
- and
- a label associated with each linegraph edge and indicating a type of join between subject nodes and object nodes;
- and the clustering module is configured to cluster the input queries from one of the plurality of groups.
10 more elements
A system for multi-query optimization over a given data set, the system comprising:
- a hardware memory comprising a database in communication with a network, the database comprising an input query set comprising a plurality of input queries over the given data set across the network, each input query comprising a graph pattern comprising at least one subject node, predicate edge and object node triple;
- and
- a computing system in communication with the database and the given dataset, the computing system comprising a computer processor and a clustering module to cluster the plurality of input queries through 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 by:
- identifying a plurality of candidate merger inputs, each candidate merge 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;
- wherein the clustering module clusters the plurality of input queries by using linegraphs, each linegraph comprising:
- linegraph nodes, each linegraph node corresponding to a given predicate edge in the input queries;
- linegraph edges between pairs of linegraph nodes that are associated with predicate edges sharing at least one of a common subject node and a common object node in the input queries;
- and
- a label associated with each linegraph edge and indicating a type of join between subject nodes and object nodes.
7 more elements
Dependencies are inferred from the claim text.