Methods and apparatus for identifying related nodes in a directed graph having named arcs
The invention provides methods for identifying related data in a directed graph (e.g., an RDF data set). A “first” step—though the steps are not necessarily executed in sequential order—includes identifying (or marking) as related data expressly satisfying the criteria. A “second” step includes identifying as related ancestors of any data identified as related, e.g., in the first step, unless that ancestor conflicts with the criteria. A “third” step of the method is identifying descendents of any data identified, e.g., in the prior steps, unless that descendent conflicts with the criteria or has a certain relationship with the ancestor from which it descends. The methods generates, e.g., as output, an indication of each of the nodes identified as related in the three steps.
1. A computer implemented method for identifying related triples in a resource description framework (RDF) data set, comprising:
A. executing the sub-steps of
(i) identifying as related a triple substantially matching a criteria;
(ii) identifying as related a triple that is a direct ancestor of a triple identified in any of sub-steps in step A, and that is not in substantial conflict with the criteria;
where, for purposes hereof, a triple whose object is the subject of another triple is deemed a direct ancestor of that other triple, and, conversely, where a triple whose subject is the object of another triple is deemed a direct descendent of that other triple;
(iii) identifying as related a triple (hereinafter “identified descendent”) that is a direct descendent”) of a triple (hereinafter “identified ancestor”) identified as related in any of sub-steps in step A, and which identified descendent
(a) is not associated with the identified ancestor via a predicate substantially matching a predicate named in the criteria, if any, and
(b) is not in substantial conflict with the criteria;
(c) is not associated with the identified ancestor via a predicate matching a predicate by which the identified ancestor is associated with a triple, if any, as a result of which the identified ancestor was identified during execution of sub-step (ii),
B. generating an indication of triples identified as related in step (A).
2. The method of claim 1 , comprising executing any of the sub-steps of step (A) any of serially, in parallel, or recursively.
3. The method of claim 1 , further comprising executing any of the sub-steps of step (A) using a rule-based engine.
4. The method of claim 3 , wherein the rule-based engine uses a Rete algorithm to effect execution of one or more of the sub-steps of step (A).
5. The method of claim 1 , wherein the resource description framework comprises of a data flow.
6. The method of claim 5 , wherein the data flow comprises any of transactional information and enterprise-related information.
7. The method of claim 1 , comprising
executing step (A) with respect to a first data set representing a first portion of the directed graph, and
executing step (A) separately with respect to a second data set representing a second portion of to directed graph.
8. A method of claim 7 , wherein the second data set comprises an update to the first data set.
9. A computer implemented method for identifying related triples in a resource description framework (RDF) data set, comprising:
A. executing the sub-steps of
(i) identifying as related a triple that is a direct ancestor of a triple identified in any of sub-steps of step A, and that is not in substantial conflict with the criteria;
where, for purposes hereof, a triple whose object is the subject of another triple is deemed a direct ancestor of that other triple, and, conversely, where a triple whose subject is the object of another triple is deemed a direct descendent of that other triple;
(ii) identifying as related a triple (hereinafter “identified descendent”) that is a direct descendent of a triple (hereinafter “identified ancestor”) identified as related in any of sub-steps in step A, and which identified descendent
(a) is not associated with the identified ancestor via a predicate substantially matching a predicate named in the criteria, if any, and
(b) is not in substantial conflict with the criteria;
(c) is not associated with the identified ancestor via a predicate matching a predicate by which the identified ancestor is associated with a triple, if any, as a result of which the identified ancestor was identified during execution of sub-step (ii),
B. generating an indication of triples identified as related in step (A).