×

Systems and methods for query evaluation over distributed linked data stores

  • US 10,031,922 B2
  • Filed: 07/10/2015
  • Issued: 07/24/2018
  • Est. Priority Date: 03/24/2015
  • Status: Active Grant
First Claim
Patent Images

1. An apparatus, comprising:

  • at least one memory; and

    at least one processing device operatively coupled to the at least one memory and configured to;

    implement a data query evaluation system at each data source of a set of distributed and networked linked data sources, wherein the distributed and network linked data sources respectively correspond to a plurality of nodes connected over a network, wherein the data query evaluation system at each data source is configured to;

    receive a query over the set of distributed and network linked data sources;

    decompose the query into a set of sub-queries of the query;

    evaluate each sub-query in the set of sub-queries with respect to each data source in the set of distributed and network linked data sources, wherein evaluating comprises determining which data sources in the set of distributed and network linked data sources are capable of answering each sub-query, wherein each data source of the set of distributed and networked linked data sources dynamically determines whether it is capable of answering each sub-query;

    summarize results of the evaluation of each sub-query;

    exchange between the distributed and networked linked data sources the summarized results of the evaluation, wherein each data source of the set of distributed and networked linked data sources dynamically provides the summarized results;

    execute, in parallel by the distributed and networked linked data sources, a distributed query evaluation process to compute a plurality of combinations of query results from the distributed and networked linked data sources which provide an answer to the query;

    compute a set of distributed plans by composing one or more of the sub-queries in one or more of the distributed and networked linked data sources;

    evaluate each plan in the set of distributed plans;

    select a sub-set of plans from the set of distributed plans to be executed for responding to the query;

    execute the selected sub-set of plans, wherein executing the selected sub-set of plans comprises;

    an exchange of data between each of the distributed and networked linked data sources that are part of the selected sub-set of plans;

    executing a plurality of sub-queries in respective ones of the distributed and networked linked data sources that are part of the selected sub-set of plans; and

    forwarding results of the execution of one or more given sub-queries of the plurality sub-queries to one or more data sources of the distributed and networked linked data sources that are part of the selected sub-set of plans, and which did not perform the one or more given sub-queries, wherein the results comprise answers and partial answers to the given sub-queries; and

    return results of the query;

    wherein the implementing of the data query evaluation system at each data source is performed without;

    (i) transmission of queried data to a central repository;

    (ii) using a central federator for coordinating and merging the partial answers from the one or more data sources of the distributed and networked linked data sources that are part of the selected sub-set of plans; and

    (iii) using a global schema to evaluate the query.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×