PARALLEL MATERIALISATION OF A SET OF LOGICAL RULES ON A LOGICAL DATABASE

• US 20160259796A1
• Filed: 10/30/2014
• Published: 09/08/2016
• Est. Priority Date: 10/31/2013
• Status: Active Grant

• Current Assignee: Oxford University Innovation Limited (University of Oxford)
• Original Assignee: Isis Innovation Limited
• Inventors: Nenov, Yavor, Horricks, Ian, Motik, Boris
• Granted Patent: US 10,817,467 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/122 using management policies backup systems G06F11/1446; file migration policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/24569 Query processing with adaptation to specific hardware, e.g. adapted for using GPUs or SSDs
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

A computer-implemented method of providing a materialisation of a set of logical rules on a logical database comprising a set of logical facts. Each of a plurality of parallel processing threads performs the following steps. A logical fact that has not previously been received by any thread is received by the thread. By applying any of the logical rules to the received logical fact and/or any of the logical facts received by any thread prior to the received logical fact, the thread determines whether a new logical fact is implied, and if so the new logical fact is added to the set of logical facts. The thread then repeats the above steps on any further logical facts in the set of logical facts that have not previously been received by any thread. When all threads are waiting for a new logical fact, the method has completed.

Claims

1. A computer-implemented method of providing a materialisation of a set of logical rules on a logical database comprising a set of logical facts, wherein each of a plurality of parallel processing threads performs the following steps:

1) receiving a logical fact from the set of logical facts, wherein the received logical fact has not previously been received by any thread;

2) determining if a new logical fact is implied, by applying any of the logical rules to the received logical fact and/or any of the logical facts received by any thread prior to the received logical fact;

3) in the case that a new logical fact is implied, adding the new logical fact to the set of logical facts;

4) determining if there are further logical facts in the set of logical facts that have not previously been received by any thread; and

4a) in the case that there are further logical facts, repeating steps 1 to 4 of the method;

4b) in the case that there are no further logical facts, waiting until a new logical fact is added to the set of logical facts, and when a new logical fact is added, repeating steps 1 to 4 of the method;

wherein when all threads are waiting for a new logical fact to be added, the set of logical facts is provided as the materialisation of the set of logical rules on the logical database.

40. A method as claimed in claim 1, wherein in step 3, each thread provides notification to any waiting threads that a new logical fact has been added.

41. A method as claimed in claim 1, wherein in step 1 the new logical fact is received from an iterator which selects the new logical fact from among the logical facts in the set of logical facts that have not previously been selected by the iterator.

42. A method as claimed in claim 1, further comprising the step, prior to performing any steps in the threads, of pre-processing the set of logical rules to determine a join ordering.

43. A method as claimed in claim 1, wherein the set of logical facts includes at least one logical fact incorporating an equality predicate indicating that two constants are equal, a mapping of constants to representative constants is maintained, and the method includes the steps of:

selecting a representative constant from the two constants;

updating the mapping to map the other constant to the representative constant;

rewriting logical facts in the set of logical facts using the mapping to replace occurrences of the other constant with the representative constant.

44. A method as claimed in claim 43, wherein when the representative constant is selected the other constant is added to a queue of constants, and wherein the logical facts are rewritten by replacing occurrences they contain of the constants in the queue of constants with their representative constants.

45. A method as claimed in claim 43, further comprising the step of rewriting the logical rules in the set of logical rules using the mapping to replace occurrences of other constants with their representative constants.

46. A method as claimed in claim 43, further comprising the steps of:

determining if a logical rule from the set of logical rules contains any constants that are mapped by the mapping to representative constants; and

in the case that a logical rule contains constants that are mapped, adding the logical rule to a queue of logical rules and wherein the logical rules that are rewritten are the logical rules in the queue of logical rules.

47. A method as claimed in claim 43, further comprising the steps of:

determining if a logical fact from the set of logical facts contains any constants that are mapped by the mapping to representative constants; and

in the case that a logical fact contains constants that are mapped, adding a marker to the logical fact.

48. A method as claimed in claim 47, wherein in step 1) a logical fact is received from the set of logical facts only if a marker has not been added to the logical fact.

56. A computer-implemented method of answering a query over a set of logical facts obtained using the method of claim 43, comprising the steps of:

rewriting the query using the mapping to replace occurrences of other constants with their representative constants;

determining answers to the rewritten query on the set of logical facts; and

expanding the answers by replacing representative constants in the answers with other constants that map to them.

57. A method as claimed in claim 56, further comprising the step of duplicating an answer in the case that another answer to the query is a constant that is a representative of a set of equal constants.

58. A method as claimed in claim 56, wherein the step of determining answers to the rewritten query comprises the substeps of:

determining the answers without evaluating any built-in functions;

expanding the answers by replacing representative constants in the answers with other constants that map to them; and

evaluating any built-in functions.

2-39. -39. (canceled)

49. A computer-implemented method of storing data in computer memory for a logical database comprising a set of logical facts, wherein the computer memory comprises a table of logical facts, each logical fact in the set of logical facts is stored as an entry in the table of logical facts, and wherein each entry in the table of logical facts further comprises at least one pointer for each logical fact to a second logical fact in the table of logical facts sharing one or more properties with the first logical fact.

50. A method as claimed in claim 49, wherein the computer memory further comprises at least one index for locating a logical fact in the table of logical facts from one or more properties of the logical fact.

51. A method as claimed in claim 49, wherein the at least one index is a hash table.

52. A method as claimed in claim 51, wherein when the number of filled buckets in the hash table exceeds a pre-determined threshold, the hash table is resized.

53. A method as claimed in claim 52, wherein the resizing is performed by each thread that attempts to access the index while it is being resized.

54. A method as claimed in claim 49, wherein each entry in the table of logical facts comprises a status flag indicating whether the logical fact in the entry has been added to the at least one index.

55. A method as claimed in claim 49, wherein each thread has associated with it a reserved area of the table of logical facts, and each thread adds logical facts only to its associated reserved area.