Forward inferencing of facts in parallel

摘要

A method and system for inferring facts in parallel in a multiprocessor computing environment is provided. An inference system infers facts by applying rules to a collection of existing facts. For each existing fact, the inference system schedules a thread to apply the rules to that existing fact. As a thread infers a new fact (i.e., one that is not already in the collection of facts), the thread adds that inferred fact to the collection of facts. When a thread adds a new fact to the collection, the thread also applies the rules to that new fact. After the threads complete execution, the inference system may apply the rules to the facts of the collection, including the newly inferred facts, by again launching a thread for each fact to apply the rules to that fact. The inference system performs this processing iteratively until a termination condition is satisfied.

主权项

1. A method in a computing system for inferring triples from rules, the method comprising:
providing a collection of triples; providing rules for inferring triples, the rules including single condition rules and multiple condition rules; for each triple in the collection, scheduling a thread to infer triples based on that triple by applying the single condition rules to that triple, adding any inferred triples not already in the collection to the collection, and applying the single condition rules to each inferred triple that is added to the collection; and after completion of the threads that apply the single condition rules, performing iterations of the following until a termination condition is satisfied:
for each triple in the collection, scheduling a thread to infer triples by applying the multiple condition rules to that triple, adding any inferred triples not already in the collection to the collection, and applying the single condition rules to each inferred triple that is added to the collection.