Computer system and methods for performing data-driven coordination

Patent metadata

Field	Value
Publication number	US-10339139-B2
Application number	US-201113816382-A
Country	US
Kind code	B2
Filing date	Aug 15, 2011
Priority date	Aug 16, 2010
Publication date	Jul 2, 2019
Grant date	Jul 2, 2019

Abstract

A computer system and computer implemented method that obtains coordinated results from at least two queries by utilizing context data of each query. Specifically, the computer system and computer implemented method facilitates enhanced querying functionality by matching entangled queries to achieve coordinated results.

First claim

The invention claimed is:

1. A computer implemented method for performing data-driven coordination of a transaction, comprising the steps of:
providing at least two queries as an entangled query in extended Structured Query Language (SQL) in the form {C}H:−B, wherein B represents a body of the entangled query specifying conditions on data source relations from a WHERE clause, H represents a head of the entangled query corresponding to a SELECT INTO clause, and C represents a postcondition of the entangled query specifying conditions on answer relations from the WHERE clause;
identifying one or more disconnected and independent query sets from the entangled query, wherein each query set excludes any query whose postcondition C unifies with the head H of two or more other queries;
determining a coordination structure based on automatically matching the head and the postcondition of each query in each of the one or more query sets to obtain one or more answerable query sets;
constructing one or more sets of combined queries based on the one or more answerable query sets;
forwarding the one or more sets of combined queries to one or more data sources to obtain one or more candidate answers of the combined queries;
evaluating one or more candidate answers of the combined queries to obtain one or more result answers; and
returning the one or more result answers, wherein the one or more result answers satisfy the head and postcondition of each query of the at least two queries.

2. The computer implemented method of claim 1 , wherein said identifying and determining step further comprises the steps of:
constructing a unifiability graph based on the at least two queries;
partitioning the unifiability graph into one or more subsets, the subsets comprising connected components of the unifiability graph, wherein the unifiability graph is a multi-graph that contains a distinct node N(qi) for each query qi in the at least two queries;
processing the one or more subsets independently and in parallel; and
discovering coordination structure between the at least two queries by matching the head and postcondition of the query corresponding to each node in each of the one or more subsets to obtain the one or more answerable query sets.

3. The computer implemented method of claim 1 , wherein the one or more datasources are one or more database, computer file, and data stream.

4. The computer implemented method of claim 1 , wherein the head and postcondition are direct data as defined by a user.

5. The computer implemented method of claim 1 , wherein the head and postcondition are context data as defined by completion of the transaction.

6. The computer implemented method of claim 1 , wherein said evaluating step further comprises the step of presenting a unifiability graph that represents certain dependencies among the at least two queries.

7. The computer implemented method of claim 6 , wherein the unifiability graph contains a distinct node for each combined query within the set of combined queries.

8. A computer implemented method for coordinating data, comprising the steps of:
generating entangled queries by receiving user inputs through a user interface, wherein each of the entangled queries is an extended Structured Query Language (SQL) in the form {C}H:−B, wherein B represents a body of the entangled query specifying conditions on data source relations from a WHERE clause, H represents a head of the entangled query corresponding to a SELECT INTO clause, and C represents a postcondition of the entangled query specifying conditions on answer relations from the WHERE clause;
executing an algorithm to evaluate the entangled queries, wherein the algorithm performs the following steps:
implementing query generation and callbacks on the computer application layer;
providing a query management process including the step of enforcing a staleness policy on a computer middleware layer;
performing coordination though a coordination module, wherein the coordination module includes a data source;
identifying one or more disconnected and independent query sets from the entangled queries, wherein each query set excludes queries whose postcondition C unifies with the head H of two or more other queries;
determining a coordination structure based on automatically matching the heads H and the postconditions C of each query in each of the one or more query sets to obtain one or more answerable query sets;
constructing one or more sets of combined queries based on the one or more answerable query sets;
sending the combined query to the data source for evaluation;
computing answers to the combined query by the coordination module; and
returning one or more answers to each of the entangled queries.

9. The computer implemented method of claim 8 , wherein said providing step further comprises the step of removing a query from a list of pending queries when the query is determined stale by the staleness policy.

10. The computer implemented method of claim 8 , wherein said performing step further comprises the steps of:
receiving a stream of queries; and
constructing a unifiability graph using suitable indices over the entangled queries.

11. The computer implemented method of claim 8 , wherein the coordination module further comprises a server.

12. The computer implemented method of claim 8 , wherein the algorithm may be executed periodically in a set-at-a time fashion.

13. The computer implemented method of claim 12 , wherein the set-at-a-time fashion is specific time intervals.

14. The computer implemented method of claim 8 , wherein the algorithm may be executed incrementally.

15. A system for automatically performing data-driven coordination, comprising:
a plurality of client computers, each client computer comprising a user interface operable to receive a query;
a computer network connecting the plurality of client computers, wherein each query of each client computer is received by the computer network resulting in a set of queries;
a data source connected to the computer network;
a memory connected to the computer network, wherein the memory includes an algorithm for evaluating the set of queries, and a processor coupled to the memory that executes the algorithm to perform the steps of:
receiving the set of queries in extended Structured Query Language (SQL) in the form {C}H:−B, wherein B represents a body of the set of queries specifying conditions on data source relations from a WHERE clause, H represents a head of the set of queries corresponding to a SELECT INTO clause, and C represents a postcondition of the set of queries specifying conditions on answer relations from the WHERE clause;
implementing query generation and callbacks on a computer application layer of the computer network;
providing a query management process and enforcing a staleness policy on a computer middleware layer of the computer network;
constructing a unifiability graph using suitable indices over the set of queries;
identifying one or more disconnected and independent query sets from the set of queries, wherein each query set excludes queries whose postcondition C unifies with the head H of two or more other queries;
determining a coordination structure based on automatically matching the heads and postconditions of each query in each of the one or more query sets to obtain one or more answerable query sets;
constructing a combined query based on the one or more answerable query sets;
sending the combined query to the data source;
computing one or more answers based on the combined query; and
returning one or more answers to a

Assignees

• Gehrke Johannes
• Koch Christoph
• Kot Lucja
• Gupta Nitin
• Univ Cornell

Inventors

• Gehrke Johannes
• Koch Christoph
• Kot Lucja
• Gupta Nitin

Classifications

• G06F16/2425 Primary

  Iterative querying; Query formulation based on the results of a preceding query · CPC title

• G06F16/24554 Primary

  Unary operations; Data partitioning operations · CPC title