Methods and apparatus for identifying related nodes in a directed graph having named arcs

• US 6,954,749 B2
• Filed: 10/07/2003
• Issued: 10/11/2005
• Est. Priority Date: 10/07/2002
• Status: Active Grant

• Current Assignee: Objectstore Incorporated
• Original Assignee: Metatomix, Inc. (ESW Capital, LLC)
• Inventors: Bigwood, David A., Britton, Colin P., Greenblatt, Howard, Greenblatt, Alan
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): EHICHIOYA, FRED I
• Application Number:
  US10/680,049
• Publication Number:
  US 20040073545A1
• Time in Patent Office: 735 Days
• Field of Search: 707/1, 707/3, 707/4, 707/5, 707/100, 707/103.R, 707/104.1, 707/200, 707/2, 707/103.Y, 370/10, 709/219, 709/224, 709/158, 706/60
• US Class Current: 707/778
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

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.

Claims

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