Granted Patent B2

US 10,762,062 · App. 15/089,858 · Granted Sep 1, 2020

Inventors: Nikolaos Lagos (Grenoble, FR); Jean-Yves Vion-Dury (Biviers, FR)

Assignee: XEROX CORPORATION

G06F16/21

Abstract

Claims (40)

1. A method for propagating a change in a dependency graph and outputting information based on the propagation, the method comprising:

providing a dependency graph as an instantiation of a linked resource model (lrm) in which a plurality of lrm:resources are linked by a plurality of lrm: dependencies, the lrm: resources including lrm:concrete resources, each of the lrm:concrete resources representing a physical object or a digital object, the lrm: resources including at least one source lrm: resource and at least one target lrm: resource, each of the lrm:dependencies specifying preconditions on at least one of the at least one source lrm: resource for the lrm:dependency to be activated and an impact on at least one of the at least one target lrm: resources when the lrm:dependency is activated, each of the lrm:dependencies being assigned to a defined class of lrm: dependencies, at least one of the lrm: dependencies being assigned to a class of lrm: dependencies selected from the group consisting of a lrm:conjunctive dependency class and a lrm:disjunctive dependency class, wherein the dependency graph is implemented as a Resource Description Framework (RDF) graph or a triple store,

wherein for a lrm:conjunctive dependency which is assigned to the lrm: conjunctive dependency class, if any of the source lrm:resources related to that lrm:dependency is changed then the lrm:dependency is activated, and wherein for a lrm:disjunctive dependency which is assigned to the lrm:disjunctive dependency class, the lrm:dependency is activated only if all source lrm:resources related to that lrm:dependency are changed,

wherein in the dependency graph, the lrm:resources and the lrm: dependencies are represented by nodes,

wherein the linked resource model permits a first of the lrm: dependencies to be linked to a second of the lrm:dependencies in the dependency graph, without an intervening lrm:resource node, by a dependency connector node that propagates change information; and

with a processor, propagating a change to one of the plurality of lrm:resources to at least one other of the plurality of lrm:resources in the graph, using the dependency connector to propagate change information from a first of the lrm:dependencies to a linked second of the lrm:dependencies in the dependency graph; and

outputting information based on the propagation, the output information including a request to modify at least one external resource which is represented in the graph, the at least one external resource including a physical object or a digital object; and

implementing a change to the at least one of the external resources.

2. The method of claim 1 , wherein the plurality of lrm:resources includes lrm:abstract resources, each of the lrm:abstract resources representing an abstract part of an entity or a process.

3. The method of claim 1 , wherein the linked resource model permits the first of the lrm:dependencies to be of a different class of lrm:dependencies from the second of the lrm:dependencies.

4. The method of claim 1 , wherein in the dependency graph, the nodes are linked by directed edges which indicate properties of relationships between linked nodes.

5. The method of claim 1 , wherein the propagating comprises applying at least one of a forward chaining mechanism and a backward chaining mechanism to propagate changes through the dependency graph.

6. The method of claim 5 , wherein the forward chaining mechanism comprises, for a source lrm:resource from the plurality of lrm:resources, and for at least one of the lrm:dependencies in the dependency graph which links the source lrm:resource to a target lrm:resource from the plurality of lrm:resources and for which an intention descriptor of the lrm:dependency is compatible with the preconditions for the lrm:dependency to be activated and is compatible with the impact on the target lrm:resource, propagating the change in the source lrm:resource to the target lrm:resource via the lrm:dependency.

7. The method of claim 6 , further comprising, for at least one iteration, repeating the forward chaining mechanism using a different lrm:resource from the plurality of lrm:resources as the source lrm:resource.

8. The method of claim 7 , wherein the forward chaining mechanism comprises:

checking that the source lrm:resource is not yet in a set of already considered source lrm:resources and if so, then adding the source lrm:resource to the set;

for each lrm:dependency that has a RDF triple in a triple store with a from property with respect to the source lrm:resource, and where the lrm:dependency is compatible with the intention, determining if the precondition and impact of the lrm:dependency satisfy the intention and if so, propagating the change in r to all target lrm:resources that are linked to the source lrm:resource by that lrm:dependency, according to the definition of the impact.

9. The method of claim 5 , wherein the backward chaining mechanism comprises, for a target lrm:resource from the plurality of lrm:resources for which a change is not detected, and for at least one of the lrm:dependencies in the dependency graph which links the target lrm:resource to a changed source lrm:resource from the plurality of lrm:resources and for which an intention descriptor of the lrm:dependency is compatible with a chaining intention to be activated and is compatible with an impact on the target lrm:resource, propagating the change in the source lrm:resource to the target lrm:resource via the lrm:dependency, according to the definition of the impact.

10. The method of claim 9 , further comprising repeating the backward chaining mechanism for another target lrm:resource from the plurality of lrm:resources.

11. The method of claim 5 , wherein the propagating comprises applying both of the forward chaining mechanism and the backward chaining mechanism.

12. The method of claim 1 , wherein the output information further comprises:

a modified dependency graph.

13. The method of claim 1 , wherein each of the lrm:dependencies specifies an intent which describes the usage of objects involved in the lrm:dependency.

14. A system for propagating a change in a dependency graph and outputting information based on the propagation, the system comprising:

memory which stores a dependency graph as an instantiation of a linked resource model (lrm) in which a plurality of lrm:resources are linked by at least one lrm:dependency, the dependency graph being implemented as a Resource Description Framework (RDF) graph or a triple store, the lrm:resources including lrm:concrete resources, each of the lrm:concrete resources representing a physical object or a digital object, the lrm:resources including at least one source lrm:resource and at least one target lrm:resource, each of the at least one lrm:dependency specifying preconditions on at least one of the at least one source lrm:resource for the lrm:dependency to be activated and an impact on at least one of the at least one target lrm:resources when the lrm:dependency is activated, each of the lrm:dependencies being assigned to a defined class of lrm:dependencies, at least one of the lrm:dependencies being assigned to a class of lrm:dependencies selected from the group consisting of an lrm:conjunctive dependency class and an lrm:disjunctive dependency class,

wherein for an lrm:conjunctive dependency assigned to the lrm:conjunctive dependency class, if any of the source lrm:resources related to that lrm:dependency is changed then the lrm:dependency is activated, and wherein for an lrm:disjunctive dependency assigned to the lrm:disjunctive dependency class, the lrm:dependency is activated only if all source lrm:resources related to that lrm:dependency are changed,

wherein in the dependency graph, the lrm:resources and the lrm:dependencies are represented by nodes,

wherein the linked resource model permits a first of the lrm:dependencies to be linked to a second of the lrm:dependencies in the dependency graph, without an intervening lrm:resource node, by a dependency connector node that propagates change information;

a propagation component which propagates a change to one of the plurality of lrm:resources to at least one other of the plurality of lrm:resources in the dependency graph, using the dependency connector to propagate change information from a first of the lrm:dependencies to a linked second of the lrm:dependencies in the dependency graph;

an output component which provides for outputting information based on the propagation, the output information including a request to modify at least one external resource which is represented in the graph, the at least one external resource including a physical object or a digital object;

an implementation component which implements a change to one of the external resources; and

a processor which implements the propagation component and the output component.

15. A method for propagating a change in a dependency graph and implementing a change to a physical object based on the propagation, the method comprising:

generating a dependency graph as an instantiation of a linked resource model (lrm) in which a plurality of lrm:resources are linked by at least one lrm: dependency, the lrm: resources including lrm:concrete resources, each of the lrm:concrete resources representing a physical object or a digital object, the lrm: resources and the at least one lrm:dependency being represented by nodes, at least some of the lrm:resource nodes being linked to the at least one lrm:dependency node by directed edges which indicate properties of relationships between linked nodes, the lrm: resources including at least one source lrm: resource and at least one target lrm: resource, each of the at least one lrm:dependency specifying preconditions on at least one of the at least one source lrm: resource for the lrm:dependency to be activated and an impact on at least one of the at least one target lrm:resources when the lrm:dependency is activated and an intention of the lrm: dependency, at least one of the lrm:dependencies being assigned to a class of lrm:dependencies selected from the group consisting of an lrm:conjunctive dependency class and an lrm:disjunctive dependency class,

wherein for an lrm:conjunctive dependency which is assigned to the lrm: conjunctive dependency class, if any of the source lrm:resources related to that lrm:dependency is changed then the lrm:dependency is activated, and wherein for a lrm:disjunctive dependency which is assigned to the lrm:disjunctive dependency class, the lrm:dependency is activated only if all source lrm:resources related to that lrm:dependency are changed; and

with a processor, propagating a change to one of the plurality of lrm:resources to at least one other of the plurality of lrm:resources in the graph the propagating including applying at least one of:

a forward chaining mechanism configured for propagating a change from a source lrm:resource to a target lrm:resource linked to the source lrm:resource by a lrm:dependency to satisfy a given intention, and

a backward chaining mechanism configured for propagating a change from a target lrm:resource to a source lrm:resource linked to the target lrm:resource by an lrm:dependency to satisfy a given intention; and

implementing a change to a physical object represented by one of the lrm:concrete resources, according to a change policy, the physical object being selected from telephone systems, computers, and printers.

16. The method of claim 15 wherein the processor is configured for propagating a change from a source one of the plurality of lrm:resources to a target one of the lrm:resources with the forward chaining mechanism and configured for propagating a change from a target one of the plurality of lrm:resources to a source one of the lrm:resources with the backward chaining mechanism.

Assignments (10)

Continuity (1)