Efficient method for logical completion of a deductive catalogue used for general constraints treatment in the extended relational database concept

Abstract

New methods to represent variables as parts of the classical truth table lead to complete evaluation methods that generate a compiled, efficient version of logical expressions.

The new methods are suitable for use in, e.g., relational database applications in which both, efficient query times as well as logical completeness and consistency are required in the context of general constraint treatments.

Input/output operations remain linear in the length of the input character strings regardless of the complexity of the logical theory.

A new processing method of formulas is described as the basis for the efficiency increase.

In order to find a specific truth-value, pattern trees are used representing the extension of the logical theory.

Claims

1. An efficient method for the logical completion of a deductive catalog used for general constraint treatment in the extended relational database concept, characterized by the fact that variables are represented by their literals as pattern character strings which reflect patterns of truth-values in the classical truth table.

2. Method according to claim 1, consisting of pattern character strings which are merged into logical pattern trees by means of pattern-oriented OR operations.

3. Method according to claim 1, consisting of logical pattern trees being resolved by means of pattern-oriented AND operations, where the finding of the total truth-value of a clause set corresponds to the result of this resolution.

4. Method according to claim 1, consisting of a combinatorial space which is generated using the resolution which does not depend on the classical variable value-combinatory-space, but on the sequence and interaction of the truth patterns of the variables in the formula to be processed.

5. Method according to claim 1, consisting of a canonical division of the clause set into smaller clause sets carried out by means of the combinatorial space where the entire final value of the clause set solely depends on the respective truth-values of the smaller sets.

6. Method according to claim 1, consisting of lengths of pattern character strings being used to provide suitable ordering criteria for the efficient production of the combinatorial space made possible by the renaming of the variables.

7. Method according to claim 1, consisting of the combinatorial space being converted using this canonical division to a decision tree which is equivalent to the classical truth table although it does not include the entire truth table combinatorics.

8. Method according to claim 1, consisting of negative literals of a logical formula being assigned a pattern string of the form 2̂i(2̂[N−i−1](1) 2̂[N−1−i](0)) and positive literals being assigned with a pattern string of the form 2̂i(2̂[N−i−1](0) 2̂[N−1−i](1)) with i index number of the respective literal, for 1=‘true’, 0=‘false’.

9. Method according to claim 2, consisting of the OR operations not being bit-oriented but pattern-oriented, where multiplication factors of sub-character strings of the patterns are being used to perform similar operations only once and then to annotate the result with these factors, and where a pattern string which has a multiplication factor f represents the f-time concatenation with itself.

10. Method according to claim 3, consisting of AND operations not being bit-oriented but pattern-oriented, where multiplication factors of sub-character strings of the patterns are being used to perform similar operations only once and then to annotate the result with these factors, and where a pattern string which has a multiplication factor f represents the f-time concatenation with itself.

11. Method according to claim 5 consisting of a canonical division of the clause set into smaller clause sets on which the former depends, being used to create partial variable assignments which determine the nodes and paths of the tree.

12. Method according to claim 6, consisting of only search- and navigation operations being used in the decision tree in order to find the truth-value of the clause set.

13. Method according to claim 11, consisting of the navigation in the decision tree being controlled by the variable-values obtained from the input, using only search- and navigation operations.

Description

DESCRIPTION OF THE DRAWINGS

[0248] The present invention may be better understood, and its numerous features and advantages made apparent to those skilled in the art by referencing the accompanying drawings.

[0249] FIG. 1 shows the components of a real Relational Database Model (RDM) system where Tj (j=1 . . . n) stands for table names and arrows symbolize data transfer;

[0250] FIG. 2 shows the SQL-command flow;

[0251] FIG. 3 shows typical database tables (ER-diagram);

[0252] FIG. 4 shows the new method of an SQL clause processing;

[0253] FIGS. 5A-5B provide an overview and illustrate overall aspects of the invention;

[0254] FIG. 6 shows a logic pattern tree in construction for C1;

[0255] FIG. 7 illustrates a pattern tree for n=3;

[0256] FIG. 8 illustrates a pattern tree for n=4;

[0257] FIGS. 9A-9D illustrate the generation of the full logic pattern tree for C1;

[0258] FIGS. 10A-10B show the most important case differences of creating a logic pattern tree for all the clauses of a logic formula;

[0259] FIGS. 10C-10D show another two case differences of creating a logic pattern tree for all the clauses of a logic formula;

[0260] FIG. 11A shows the most common case of a logic input tree for Method 4;

[0261] FIG. 11B illustrates the theoretical expansion of the tree in FIG. 11A;

[0262] FIGS. 12A-12B illustrate the creation of decision trees for a clause set with canonical divisions;

[0263] FIGS. 12C-12D show the transition from the result- to the decision tree;

[0264] FIG. 12E provides the corresponding truth table of the result- and decision tree;