Query processing algorithm for vertically partitioned federated database systems

In a computing environment, a computer physical readable medium comprising computer executable instructions that when executed by one or more processors perform the following:

• accessing a first search predicate, the first search predicate constructed with one or more nested logical AND, OR, or NOT operands;
• normalizing the first search predicate to a normalized search predicate that is logically equivalent to the first search predicate, and wherein the normalized search predicate includes at least three and up to four levels, wherein all top or first level operands are logically ORed, wherein all second level operands below the top level operands are logically ANDed, wherein at the third level, all third level operands below the second level operands are at least one of parameters or logical NOTs, and at the fourth or bottom level any fourth level operands below a third level logical NOT operand at the third level are parameters;
• and
• using the normalized search predicate, searching a plurality of data stores in a federation of data stores for information by searching different data stores for at least two or more of the top level operands.

In a computing environment, a computing system comprising:

• one or more processors;
• and
• one or more physical computer readable media coupled to the one or more processors, wherein the one or more physical computer readable media comprise computer executable instructions that when executed by the one or more processors perform the following:
• accessing a first search predicate, the first search predicate constructed with one or more nested logical AND, OR, or NOT operands;
• normalizing the first search predicate to a normalized search predicate that is logically equivalent to the first search predicate, and wherein the normalized search predicate includes at least three and up to four levels, wherein all top or first level operands are logically ORed, wherein all second level operands below the top level operands are logically ANDed, wherein at the third level, all third level operands below the second level operands are at least one of parameters or logical NOTs, and at the fourth or bottom level any fourth level operands below a third level logical NOT operand at the third level are parameters;
• and
• using the normalized search predicate, searching a plurality of data stores in a federation of data stores for information by searching different data stores for at least two or more of the top level operands, comprising searching for a first component filter and a second component filter and merging the results and by searching with one or more sub-filters to obtain one or lists and applying one or more other sub-filters to the one or more lists.