SYSTEMS AND METHODS FOR USING GRAPHS FOR APPLICATION UPDATES

• US 20160274898A1
• Filed: 05/31/2016
• Published: 09/22/2016
• Est. Priority Date: 07/03/2012
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Rychikhin, Yuri
• Granted Patent: US 10,732,953 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57
• CPC Class Codes: G06F 8/71 Version control security arrangements therefor G06F21/57; Configuration management

Abstract

A sequence of update steps from a currently installed version an application on a remote client device to a new version of the application to be installed on the client device is determined. A representation of updates from the currently installed version to the new version of the client application is built. The representation is stored in at least one memory device. A shortest path between the currently installed version of the client application and the new version of the client application is determined. An update is determined from a combination of the sequence of update steps unique to the shortest path between the currently installed version of the application and the new version of the application. An update package is built to update the currently installed version of the client application to the new version of the client application.

Claims

1. A method comprising:

determining, with one or more processors that are part of a server system, a sequence of update steps from a currently installed version of a client application on a remote client device having one or more processors and a user interface to a new version of the client application to be installed on the client device;

building a representation of updates from the currently installed version of the client application to the new version of the client application with the one or more processors that are part of the server system;

storing the representation in at least one memory device coupled with the one or more processors that are part of the server system;

determining, with the one or more processors that are part of the server system, a shortest path between the currently installed version of the client application and the new version of the client application;

determining, with the one or more processors that are part of the server system, an update from a combination of the sequence of update steps unique to the shortest path between the currently installed version of the client application and the new version of the client application; and

building, with the one or more processors that are part of the server system, an update package to update the currently installed version of the client application to the new version of the client application.

2. The method of claim 1, wherein the update path from the currently installed version of the client application to the new version of the client application includes at least a change to a structure of a schema.

3. The method of claim 1, wherein the update path from the currently installed version of the client application to the new version of the client application includes at least a change to a structure of a table.

4. The method of claim 1 wherein the client device comprises a smart phone.

5. The method of claim 1, the server system further provides an on-demand multi-tenant database environment.

6. The method of claim 1, wherein the building the representation comprises creating a directed acyclic graph (DAG) of the update steps and the determining the series of update steps to apply are based on the directed acyclic graph.

7. The method of claim 6, 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 reached.

8. The method of claim 7, 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.

9. The method of claim 1, further comprising analyzing the available update steps to determine at least whether the step includes a format change.

10. 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.

11. A non-transitory computer-readable medium having stored thereon instructions that, when executed by one or more processors, cause the one or more processors to:

determine a sequence of update steps from a currently installed version of a client application on a remote client device having one or more processors and a user interface to a new version of the client application to be installed on the client device;

build a representation of updates from the currently installed version of the client application to the new version of the client application;

store the representation in at least one memory device coupled with the one or more processors;

determine a shortest path between the currently installed version of the client application and the new version of the client application;

determine an update from a combination of the sequence of update steps unique to the shortest path between the currently installed version of the client application and the new version of the client application; and

build an update package to update the currently installed version of the client application to the new version of the client application.

12. The non-transitory computer-readable medium of claim 11, wherein the update path from the currently installed version of the client application to the new version of the client application includes at least a change to a structure of a schema.

13. The non-transitory computer-readable medium of claim 11, wherein the update path from the currently installed version of the client application to the new version of the client application includes at least a change to a structure of a table.

14. The non-transitory computer-readable medium of claim 11 wherein the client device comprises a smart phone.

15. The non-transitory computer-readable medium of claim 11, wherein the building the representation comprises creating a directed acyclic graph (DAG) of the update steps and the determining the series of update steps to apply are based on the directed acyclic graph.

16. The non-transitory computer-readable medium of claim 15, 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 reached.

17. The non-transitory computer-readable medium of claim 16, further comprising instruction that, when executed by the one or more processors, cause the one or more processors to:

compute 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;

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

repeat 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

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

18. The non-transitory computer-readable medium of claim 11, further comprising instructions that, when executed by the one or more processors, cause the one or more processors to analyze the available update steps to determine at least whether the step includes a format change.

19. The non-transitory computer-readable medium of claim 11, further comprising instruction that, when executed by the one or more processors, cause the one or more processors to:

determine the currently installed version;

determine the new version being installed;

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

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

sort version vertices of the graph in ascending order;

determine whether the graph is missing vertices;

determine whether the graph is missing connections;

complete the graph, if vertices or connections are missing;

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

perform the update along the shortest path of the graph.