System and method for using directed acyclic graph (DAG) for application updates

1. A method comprising:

determining, by a host system including at least a machine having a processor system including at least one processor and a memory system communicatively coupled to the processor system, a sequence of update steps from a currently installed version of an application to a new version of the application to be being installed;

automatically building a graph of updates from the currently installed version to the new version comprising at least determining update steps that do not require a format change, and computing a shortest path between the currently installed version and the new version based, at least in part, on the determined steps that do not require a format change, wherein a format change causes a change to an underlying schema and manner in which data is stored, and wherein the computing includes running a breadth-first-search algorithm of the graph of updates;

combining, by the processor system, the sequence of update steps that do not require a format change into one update step;

determining, by the processor, one or more update steps that require a format change;

building, by the host system, an update from a combination of the sequence of update steps that do not require a format change and one or more update steps that require a format change; and

sending from the host from the host system to the user system, the built update.

2. The method of claim 1 , the format change being a change to a structure of a schema.

3. The method of claim 1 , the format change being a change to a structure of a table.

4. The method of claim 1 , the application being an application for running on a smart phone.

5. The method of claim 1 , the application including one or more machine instructions, which when implemented cause the application connect, via a network, to a database stored on the host machine, the application being an interface for accessing the database.

6. The method of claim 1 , the host system being an on-demand multi-tenant relational database.

7. The method of claim 1 , wherein the determining includes creating a directed acyclic graph (DAG) s of the update steps and the determining the series of update steps to apply are based on the directed acyclic graph.

8. The method of claim 1 , wherein the determining a sequence of update steps includes:

computing the shortest path from the currently installed version to the version being installed.

9. The method of claim 1 , wherein the sequence of update steps is computed by

starting with a first node, representing the currently installed version, inspecting each neighboring nodes and determining properties of each update step needed to arrive at neighboring nodes;

repeating the inspecting and determining of properties of each new neighbor of each prior neighbor, if the new neighbor was not yet inspected; and

repeating the inspecting and determining of properties of each new neighbor of each prior neighbor until the node corresponding to the new version is arrived at.

10. The method of claim 1 , further comprising:

determining the currently installed version;

determining the new version being installed; and

basing the building of the update on the currently installed version and the new version to be installed.

11. The method of claim 1 , further comprising:

analyzing the available update steps to determine at least whether the step includes a format change.

12. The method of claim 1 , further comprising:

building an initial version of a graph of the update steps; and

sorting version vertices of the graph in ascending order.

13. The method of claim 1 , further comprising:

determining whether the graph is missing vertices;

determining whether the graph is missing connections; and

completing the graph, if vertices or connections are missing.

14. The method of claim 1 , further comprising:

computing the shortest path from the installed version to the version to update to by starting with a first node, representing the currently installed version, inspecting each neighboring nodes and determining properties of each update step needed to arrive at neighboring nodes;

repeating the inspecting and determining of properties of each new neighbor of each prior neighbor, if the new neighbor was not yet inspected; and

repeating the inspecting and determining of properties of each new neighbor of each prior neighbor until the node corresponding to the new version is arrived at; and

performing the update along the shortest path of the graph found between the current version and the new version.

15. The method of claim 1 , further comprising:

determining whether one update undoes format changes of the other update;

if one update undoes format changes of the other update, skipping both updates.

16. The method of claim 1 , further comprising:

receiving a request for an update, the request including an indication of the currently installed version of the application and an indication of the new version of the application that is desired to be installed.

17. The method of claim 1 , further comprising:

determining the currently installed version;

determining the new version being installed;

analyzing the available update steps to determine at least whether the step includes a format change;

building an initial version of a graph of the update steps;

sorting version vertices of the graph in ascending order;

determining whether the graph is missing vertices;

determining whether the graph is missing connections;

completing the graph, if vertices or connections are missing;

computing the shortest path from the installed version to the version to update to by running a breadth-first search (BFS) on the graph; and

performing the update along the shortest path of the graph.

18. A non-transitory machine-readable medium carrying one or more sequences of instructions for using directed acyclic graph (DAG) for application updates in a multi-tenant database system, which instructions, when executed by one or more processors, cause the one or more processors to:

determine, by a host system including at least a machine having a processor system including at least one processor and a memory system communicatively coupled to the processor system, a sequence of update steps from a currently installed version of an application to a new version of the application to be installed;

automatically build a graph of updates from the currently installed version to the new version comprising at least determining update steps that do not require a format change, and computing a shortest path between the currently installed version and the new version based, at least in part, on the determined steps that do not require a format change, wherein a format change causes a change to an underlying schema and/or manner in which data is stored, and wherein the computing includes running a breadth-first-search algorithm of the graph of updates;

combine, by the host system, the sequence of update steps that do not require a format change;

determine, by the host system, one or more update steps that require a format change;

build, by the host system, an update from a combination of the sequence of update steps that do not require a format change and one or more update steps that require a format change; and

perform, by the host system, the resulting update steps.