# US 2021/0240780 A1 · Query processing using matrix and reduced predicate statements > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0240780 A1 - Document ID: US20210240780A1 - Status: Published application - Kind: A1 - Application number: 16/777,405 - Filed: 2020-01-30 - Published: 2021-08-05 - Earliest claimed: 2020-01-30 - Assignees: Adobe Inc. - Applicants: Adobe Inc. - Inventors: Sandeep Nawathe - Web page: https://patentgrep.com/patent/US20210240780A1 ## CPC - G06F 16/90335: {Query processing} - G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} - G06F 16/9027: {Trees} - G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} - G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound - G06N 20/00: Machine learning - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract A query processing system applies transforms to convert a collection of predicate statements to two parts, a matrix and a set of reduced predicate statements, and evaluates the matrix and reduced predicate statements when querying data. The query processing system applies the transforms to extract conjunctive predicates or disjunctive predicates from the predicate statements to provide the set of reduced predicate statements and generates the matrix using the extracted conjunctive predicates or disjunctive predicates. When data is received for querying, the query processing system evaluates the matrix and reduced predicate statements for the data to provide search results. The query processing system may first identify candidate predicate statements that may be satisfied for the data from the matrix and then evaluates the reduced predicate statements for those candidate predicate statements. ## Claims ### Claim 1 One or more computer storage media storing computer-useable instructions that, when used by a computing device, cause the computing device to perform operations, the operations comprising: accessing a collection of predicate statements to be evaluated for querying data; for each of at least a portion of the predicate statements, extracting one or more conjunctive predicates or one or more disjunctive predicates to provide a reduced predicate statement; generating a matrix that includes, for each of the at least a portion of the predicate statements, the one or more conjunctive predicates or the one or more disjunctive predicates extracted from the predicate statement; and storing the reduced predicate statements and matrix on one or more storage devices to evaluate the predicate statements for input data. ### Claim 2 (depends on 1) The one or more computer storage media of claim 1, wherein the operations further comprise performing one or more preprocessing operations on one or more predicate statements from the collection of predicate statements. ### Claim 3 (depends on 2) The one or more computer storage media of claim 2, wherein the one or more preprocessing operations comprise: converting the one or more predicate statements to conjunctive normal form or disjunctive normal form. ### Claim 4 (depends on 2) The one or more computer storage media of claim 2, wherein the one or more preprocessing operations comprise: generating a tree expression for each predicate statement. ### Claim 5 (depends on 1) The one or more computer storage media of claim 1, wherein the reduced predicate statements and matrix are generated by: applying one or more transforms to at least a portion of the predicate statements. ### Claim 6 (depends on 5) The one or more computer storage media of claim 5, wherein applying the one or more transforms comprises: identifying a first predicate statement that includes multiple disjunctions for a first variable; and consolidating the multiple disjunctions as a single predicate and removing the multiple disjunctions from the first predicate statement. ### Claim 7 (depends on 5) The one or more computer storage media of claim 5, wherein applying the one or more transforms comprises: identifying a first predicate statement that includes multiple predicates for a first variable that include an inequality operator; and consolidating the multiple predicates as a single predicate with an inequality operator. ### Claim 8 (depends on 5) The one or more computer storage media of claim 5, wherein applying the one or more transforms comprises: identifying a first predicate statement that does not have a conjunctive predicate for a first variable; and augmenting the first predicate statement with a conjunctive predicate for the first variable that includes an equality operator and a phantom value. ### Claim 9 (depends on 1) The one or more computer storage media of claim 1, wherein generating the matrix comprises: adding, for each predicate statement, a true value to the matrix for any variable not having a conjunctive predicate or a disjunctive predicate in the predicate statement. ### Claim 10 (depends on 1) The one or more computer storage media of claim 1, wherein the matrix comprises a table in which each row corresponds with a predicate statement from the collection of predicate statements and each column corresponds with a variable from a plurality of variables included in the collection of predicate statements. ### Claim 11 (depends on 1) The one or more computer storage media of claim 1, wherein the operations further comprise: receiving input data comprising a value for each of one or more variables; evaluating the collection of predicate statements for the input data using the matrix and reduced predicate statements. ### Claim 12 (depends on 11) The one or more computer storage media of claim 11, wherein evaluating the collection of predicate statements for the input data comprises: identifying one or more candidate predicate statements that can be satisfied for the input data using the matrix; and evaluating the reduced predicate statement for the input data for each of the one or more candidate predicate statements. ### Claim 13 A computerized method for querying input data, the method comprising: applying one or more transforms to a collection of predicate statements to generate a matrix and a set of reduced predicate statements, the matrix including one or more conjunctive predicates or one or more disjunctive predicates from each of one or more predicate statements from the collection of predicate statements, the set of reduced predicate statements including a reduced predicate statement generated for each of the one or more predicate statements by removing the one or more conjunctive predicates or one or more disjunctive predicates; receiving input data comprising a value for each of one or more variables; evaluating the collection of predicate statements for the input data using the matrix and the set of reduced predicate statements. ### Claim 14 (depends on 13) The computerized method of claim 13, wherein the method further comprises converting each of at least a portion of the predicate statements to conjunctive normal form or disjunctive normal form. ### Claim 15 (depends on 13) The computerized method of claim 13, wherein applying the one or more transforms comprises: identifying a first predicate statement that includes multiple disjunctions for a first variable; and consolidating the multiple disjunctions as a single predicate and removing the multiple disjunctions from the first predicate statement. ### Claim 16 (depends on 13) The computerized method of claim 13, applying the one or more transforms comprises: identifying a first predicate statement that includes multiple predicates for a first variable that include an inequality operator; and consolidating the multiple predicates as a single predicate with an inequality operator. ### Claim 17 (depends on 13) The computerized method of claim 13, wherein applying the one or more transforms comprises: identifying a first predicate statement that does not have a conjunctive predicate for a first variable; and augmenting the first predicate statement with a conjunctive predicate for the first variable that includes an equality operator and a phantom value. ### Claim 18 (depends on 13) The computerized method of claim 13, wherein generating the matrix comprises: adding, for each predicate statement, a true value to the matrix for any variable not having a conjunctive predicate or a disjunctive predicate in the predicate statement. ### Claim 19 (depends on 13) The computerized method of claim 13, wherein evaluating the collection of predicate statements for the input data comprises: identifying one or more candidate predicate statements that can be satisfied for the input data using the matrix; and evaluating the reduced predicate statement for the input data for each of the one or more candidate predicate statements. ### Claim 20 A computer system comprising: means for applying one or more transforms to a collection of predicate statements to generate a matrix and a set of reduced predicate statements; and means for evaluating the collection of predicate statements for input data using the matrix and the set of reduced predicate statements.