Computer data system data source refreshing using an update propagation graph
First Claim
Patent Images
1. A system for updating a plurality of data objects using an update propagation graph, the system comprising:
- one or more hardware processors coupled to a nontransitory computer readable medium having stored thereon software instructions that, when executed by the one or more processors, cause the one or more processors to perform operations including;
receiving, at a remote query processor, a first query from a client, the first query referencing the plurality of data objects including one or more data sources;
determining dependencies between the plurality of data objects in the first query;
converting first code into in-memory data structures configured to hold a directed acyclic graph (DAG) structure in memory;
updating connectivity within the DAG based on execution of second code;
generating the update propagation graph (UPG) in a context of the remote query processor based on the first query and the DAG, the UPG having a plurality of nodes each corresponding to one of the plurality of data objects, the UPG having a structure representing the dependencies between the plurality of data objects in the first query, wherein a sequence in which the UPG is generated is recorded;
updating the structure of the UPG in response to a second query being executed by the remote query processor, wherein the sequence in which the UPG is updated is recorded; and
after the updating, processing one or more changes according to an order determined by the updated UPG, wherein the sequence determines the order in which the plurality of nodes in the UPG are processed,wherein the DAG is comprised of one or more of a dynamic node, a static node, or an internal node,wherein each of the dynamic node, the static node, or the internal node has one or more of input dynamic nodes, input static nodes or input internal nodes as inputs,wherein the dynamic node includes a node of the DAG that updates as previously presented data corresponding to the dynamic node is received,wherein the dynamic node includes a timer that triggers an event based on time intervals,wherein the static node includes a node of the DAG that does not update,wherein the internal node includes a listener node with associated listener monitoring code that places additional events into a priority queue of the DAG, andwherein a priority of the event in the priority queue is based on a position of the DAG, andwherein the internal node includes an interior node of the DAG.
3 Assignments
0 Petitions
Accused Products
Abstract
Described are methods, systems and computer readable media for data source refreshing.
520 Citations
16 Claims
-
1. A system for updating a plurality of data objects using an update propagation graph, the system comprising:
-
one or more hardware processors coupled to a nontransitory computer readable medium having stored thereon software instructions that, when executed by the one or more processors, cause the one or more processors to perform operations including; receiving, at a remote query processor, a first query from a client, the first query referencing the plurality of data objects including one or more data sources; determining dependencies between the plurality of data objects in the first query; converting first code into in-memory data structures configured to hold a directed acyclic graph (DAG) structure in memory; updating connectivity within the DAG based on execution of second code; generating the update propagation graph (UPG) in a context of the remote query processor based on the first query and the DAG, the UPG having a plurality of nodes each corresponding to one of the plurality of data objects, the UPG having a structure representing the dependencies between the plurality of data objects in the first query, wherein a sequence in which the UPG is generated is recorded; updating the structure of the UPG in response to a second query being executed by the remote query processor, wherein the sequence in which the UPG is updated is recorded; and after the updating, processing one or more changes according to an order determined by the updated UPG, wherein the sequence determines the order in which the plurality of nodes in the UPG are processed, wherein the DAG is comprised of one or more of a dynamic node, a static node, or an internal node, wherein each of the dynamic node, the static node, or the internal node has one or more of input dynamic nodes, input static nodes or input internal nodes as inputs, wherein the dynamic node includes a node of the DAG that updates as previously presented data corresponding to the dynamic node is received, wherein the dynamic node includes a timer that triggers an event based on time intervals, wherein the static node includes a node of the DAG that does not update, wherein the internal node includes a listener node with associated listener monitoring code that places additional events into a priority queue of the DAG, and wherein a priority of the event in the priority queue is based on a position of the DAG, and wherein the internal node includes an interior node of the DAG. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method for updating one or more data objects using an update propagation graph, the method comprising:
-
receiving, at a remote query processor, a first query from a client, the first query referencing the one or more data objects including one or more data sources; determining dependencies between the one or more data objects in the first query; converting first code into in-memory data structures configured to hold a directed acyclic graph (DAG) structure in memory; updating connectivity within the DAG based on execution of second code; generating an update propagation graph (UPG) in a context of the remote query processor based on the first query and the DAG, the UPG having a plurality of nodes each corresponding to one of the one or more data objects, the UPG having a structure representing the dependencies between the one or more data objects in the first query, wherein a sequence in which the UPG is generated is recorded; updating the structure of the UPG in response to a second query being executed by the remote query processor, wherein the sequence in which the UPG is updated is recorded; and after the updating, processing one or more changes according to an order determined by the updated UPG, wherein the one or more changes include one or more of addition to, modification of, deletion from or re-indexing of at least part of the one or more data objects, wherein the DAG is comprised of one or more of a dynamic node, a static node, or an internal node, wherein each of the dynamic node, the static node, or the internal node has one or more of input dynamic nodes, input static nodes or input internal nodes as inputs, wherein the dynamic node includes a node of the DAG that updates as previously presented data corresponding to the dynamic node is received, wherein the dynamic node includes a timer that triggers an event based on time intervals, wherein the static node includes a node of the DAG that does not update, wherein the internal node includes a listener node with associated listener monitoring code that places additional events into a priority queue of the DAG, and wherein a priority of the event in the priority queue is based on a position of the DAG, and wherein the internal node includes an interior node of the DAG. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A nontransitory computer readable medium having stored thereon software instructions that, when executed by one or more processors, cause the one or more processors to perform operations including:
-
receiving, at a remote query processor, a first query from a client, the first query referencing one or more data objects including one or more data sources; determining dependencies between the one or more data objects in the first query; converting first code into in-memory data structures configured to hold a directed acyclic graph (DAG) structure in memory; updating connectivity within the DAG based on execution of second code; generating an update propagation graph (UPG) in a context of the remote query processor based on the first query and the DAG, the UPG having a plurality of nodes each corresponding to one of the one or more data objects, the UPG having a structure representing the dependencies between the one or more data objects in the first query, wherein a sequence in which the UPG is generated is recorded; updating the structure of the UPG in response to a second query being executed by the remote query processor, wherein the sequence in which the UPG is updated is recorded; and after the updating, processing one or more changes according to an order determined by the updated UPG, wherein the sequence determines the order in which the plurality of nodes in the UPG are processed, and wherein the one or more changes include one or more of addition to, modification of, deletion from or re-indexing of at least part of the one or more data objects, and wherein information about the addition, the deletion, and the modification from an upstream node is used to compute changes to downstream nodes, wherein the DAG is comprised of one or more of a dynamic node, a static node, or an internal node, wherein each of the dynamic node, the static node, or the internal node has one or more of input dynamic nodes, input static nodes or input internal nodes as inputs, wherein the dynamic node includes a node of the DAG that updates as previously presented data corresponding to the dynamic node is received, wherein the dynamic node includes a timer that triggers an event based on time intervals, wherein the static node includes a node of the DAG that does not update, wherein the internal node includes a listener node with associated listener monitoring code that places additional events into a priority queue of the DAG, and wherein a priority of the event in the priority queue is based on a position of the DAG, and wherein the internal node includes an interior node of the DAG. - View Dependent Claims (14, 15, 16)
-
Specification