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

A relational database system including:

• a processor coupled to a non-transitory memory, the non-transitory memory including a relational database and the processor including instructions disposed to perform one or more functions on database queries;
• the relational database having one or more records and disposed to receive one or more database queries to be applied to the relational database, each particular database query reciting a relationship between a database record and a plurality of literals;
• the functions including a query convertor disposed to convert the database query to a plurality of clauses, each of the plurality of clauses reciting one or more literals of the plurality of literals;
• the functions including a pattern string generator disposed to determine a set of pattern strings, wherein
• the set of pattern strings includes at least one selected pattern string for each literal,
• for N literals, the at least one selected pattern string for the kth literal Xk, 0≤k≤N−1, includes:
• a first pattern string including a factor (2k) copies of a first pattern, wherein the first pattern includes a factor (2N-K-1) copies of a “1” bit followed by a factor (2N-K-1) copies of a “0” bit, or
• a second pattern string including a factor (2k) copies of a second pattern, wherein the second pattern includes a factor (2N-K-1) copies of a “0” bit followed by a factor (2N-K-1) copies of a “1” bit;
• the functions including a special type of OR operation (patternOR) disposed to join pattern strings for literals of a particular clause to represent the particular clause and repeating the joining pattern strings step for each of the plurality of clauses to obtain a plurality of binary trees corresponding to the plurality of clauses;
• the functions including a special type of AND operation (patternAND) disposed to join the plurality of binary trees to generate a result tree;
• the functions including instructions disposed to find a truth value of the result tree and select database records satisfying the truth value as a response to the database query.

A method of applying a database query to a relational database, the database having one or more records, the database query reciting a relationship between a database record and a plurality of literals, the method including steps of:

• converting the database query to a plurality of clauses, each of the plurality of clauses reciting one or more literals of the plurality of literals;
• converting the plurality of literals into a set of pattern strings, wherein
• the set of pattern strings includes at least one selected pattern string for each literal;
• for N literals, the at least one selected pattern string for the kth literal Xk, 0≤k≤N−1, includes:
• a first pattern string including a factor (2k) copies of a first pattern, wherein the first pattern includes a factor (2N-K-1) copies of a “1” bit followed by a factor (2N-K-1) copies of a “0” bit;
• or
• a second pattern string including a factor (2k) copies of a second pattern, wherein the second pattern includes a factor (2N-K-1) copies of a “0” bit followed by a factor (2N-K-1) copies of a “1” bit;
• joining pattern strings for all literals of a particular clause by a special type of OR operation (patternOR), to represent the particular clause;
• repeating the step of joining pattern strings for each of the plurality of clauses to obtain a plurality of binary trees corresponding to the plurality of clauses;
• generating a result tree by joining the plurality of binary trees by a special type of AND operation (patternAND);
• using the result tree to find a truth value of the plurality of clauses of the database query, wherein using the result tree to find a truth value includes converting the result tree into a decision tree;
• selecting database records satisfying the truth value as a response to the database query.