# US 2022/0035811 A1 · Optimal Index Selection in Polynomial Time

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0035811 A1
- Document ID: US20220035811A1
- Status: Published application
- Kind: A1
- Application number: 17/473,815
- Filed: 2021-09-13
- Published: 2022-02-03
- Earliest claimed: 2015-12-04
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Bernhard F. Scholz; Pavle Subotic
- Web page: https://patentgrep.com/patent/US20220035811A1

## CPC

- G06F 16/24537: {of operators}
- G06F 16/24534: {Query rewriting; Transformation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method may use a minimal set of indices for an input query including identifying the input query including primitive searches that are accelerated using indices, and computing a minimal set of indices for the input query using a polynomial-time algorithm by constructing a bi-partite graph comprising a first and a second vertex set. The first and the second vertex set may be a set of searches in both partitions of the bi-partite graph. Each edge of the edge set may connect a vertex in the first vertex set and a vertex in the second vertex set. The method may further include identifying an edge set as a strict subset relation between at least two searches of the set of searches showing up in the first and second vertex set of the bi-partite graph, and performing relational data analysis using the minimal set of indices for input queries.

## Claims

### Claim 1

A method for performing analysis using a minimal set of indices for an input query comprising:
identifying the input query comprising a plurality of primitive searches that are accelerated using indices;
computing a minimal set of indices for the input query using a polynomial-time algorithm by constructing a bi-partite graph comprising a first and a second vertex set, wherein the first and the second vertex set are a set of searches in both partitions of the bi-partite graph;
identifying an edge set as a strict subset relation between at least two searches of the set of searches showing up in the first and second vertex set of the bi-partite graph, wherein each edge of the edge set connects a vertex in the first vertex set and a vertex in the second vertex set; and
performing relational data analysis using the minimal set of indices for input queries.

### Claim 2 (depends on 1)

The method of claim 1, wherein computing the minimal set of indices for the input query further comprises:
computing a matching set comprising at most one edge in a matching set for each vertex within the bi-partite graph; and
traversing the matching set to find one or more chains and convert the one or more chains to lexicographical orders.

### Claim 3 (depends on 1)

The method of claim 1, wherein the plurality of primitive searches comprises, as a search predicate, a conjunction of equalities over attributes.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
constructing value queries and equi-joins using the plurality of primitive searches.

### Claim 5 (depends on 1)

The method of claim 1, wherein the relational data analysis is performed on an in-memory Datalog machine.

### Claim 6

A system for performing analysis using a minimal set of indices for an input query comprising:
a data repository storing software code;
a computer processor communicatively connected to the data repository and configured to execute instructions to:
identify the input query comprising a plurality of primitive searches that are accelerated using indices;
compute a minimal set of indices for the input query using a polynomial-time algorithm by constructing a bi-partite graph comprising a first and a second vertex set, wherein the first and the second vertex set are a set of searches in both partitions of the bi-partite graph;
identify an edge set as a strict subset relation between at least two searches of the set of searches showing up in the first and second vertex set of the bi-partite graph, wherein each edge of the edge set connects a vertex in the first vertex set and a vertex in the second vertex set;
perform relational data analysis using the minimal set of indices for input queries.

### Claim 7 (depends on 6)

The system of claim 6, wherein the processor is further configured to execute instructions to compute the minimal set of indices for the input query by:
computing a matching set comprising at most one edge in a matching set for each vertex within the bi-partite graph; and
traversing the matching set to find one or more chains and convert the one or more chains to lexicographical orders.

### Claim 8 (depends on 6)

The system of claim 6, wherein the plurality of primitive searches comprises, as a search predicate, a conjunction of equalities over attributes.

### Claim 9 (depends on 6)

The system of claim 6, wherein the processor is further configured to execute instructions to construct value queries and equi-joins using the plurality of primitive searches.

### Claim 10 (depends on 6)

The system of claim 6, further comprising:
an in-memory Datalog machine to perform the relational data analysis.

### Claim 11

A non-transitory computer readable medium comprising instructions that, when executed by a computer processor, perform a method for performing analysis using a minimal set of indices for an input query comprising:
identifying the input query comprising a plurality of primitive searches that are accelerated using indices;
computing a minimal set of indices for the input query using a polynomial-time algorithm by constructing a bi-partite graph comprising a first and a second vertex set, wherein the first and the second vertex set are a set of searches in both partitions of the bi-partite graph;
identifying an edge set as a strict subset relation between at least two searches of the set of searches showing up in the first and second vertex set of the bi-partite graph, wherein each edge of the edge set connects a vertex in the first vertex set and a vertex in the second vertex set; and
performing relational data analysis using the minimal set of indices for input queries.

### Claim 12 (depends on 11)

The non-transitory computer readable memory of claim 11, wherein the computer processor is further configured to execute instructions to compute the minimal set of indices for the input query by:
computing a matching set comprising at most one edge in a matching set for each vertex within the bi-partite graph; and
traversing the matching set to find one or more chains and convert the one or more chains to lexicographical orders.

### Claim 13 (depends on 11)

The non-transitory computer readable medium of claim 11, wherein the plurality of primitive searches comprises, as a search predicate, a conjunction of equalities over attributes.

### Claim 14 (depends on 11)

The non-transitory computer readable medium of claim 11, further comprising instructions that, when executed by a computer processor, perform the method for performing analysis using a minimal set of indices for an input query comprising:
constructing value queries and equi-joins using the plurality of primitive searches.

### Claim 15 (depends on 11)

The non-transitory computer readable medium of claim 11, wherein the relational data analysis is performed on an in-memory Datalog machine.
