# US 2008/0189233 A1 · Reduction of Ternary Rules with Common Priority and Actions

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

- Number: US 2008/0189233 A1
- Document ID: US20080189233A1
- Status: Published application
- Kind: A1
- Application number: 11/466,472
- Filed: 2006-08-23
- Published: 2008-08-07
- Earliest claimed: 2003-01-30
- Assignees: International Business Machines Corporation
- Inventors: Everett A. Corl; Clark D. Jeffries; Brooks Johnston; Plyush C. Patel; Jan Van Lunteren
- Web page: https://patentgrep.com/patent/US20080189233A1

## CPC

- G06F 16/21: Design, administration or maintenance of databases
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system for reducing the size of a database includes a memory in which the database configured in a ternary matrix array structure is stored. A processor executing at least one reduction algorithm scans the database tagging superfluous entries that are subsequently deleted. The tagging and deleting are done in such a way that the logical contents of the original database is unchanged, even though the size of the database is reduced.

## Claims

### Claim 1

A method to reduce the size of a database comprising the acts of:
(a) providing the database in a memory said database including a listing of N rules, N>=2, with indices 0, 1, 2 . . . N and characters 0, 1 and * (wild card or don't care);
(b) tagging each rule with a valid bit having a first value;
(c) processing the N rules with a redundancy test algorithm that identifies rules included in other rules; and
(d) tagging rules identified in (c) with a value bit having a second value.

### Claim 2 (depends on 1)

The method of claim 1 further including the acts of processing only rules tagged with the first indicia with a Reduction Algorithm thus to determine Rules that are identical to other rules in all bit positions except one.

### Claim 3 (depends on 2)

The method of claim 2 further including the act of tagging selected ones of the rules processed with the second indicia.

### Claim 4 (depends on 3)

The method of claim 3 wherein the first indicia includes a 1 and the second indicia a 0.

### Claim 5 (depends on 4)

The method of claim 4 further including the act of deleting from said database entries rules marked with 0.

### Claim 6 (depends on 1)

The method of claim 1 wherein act (c) further includes the act of applying to the database the redundancy step algorithm as a program with the folloiwng steps of:
step 1 letting an index i initially be 0;
step 2 letting an index j initially be 0;
step 3 if rule Rj has valid bit=0, then go to step 6;
step 4 if j=i, then go to step 6;
step 5 if
no 0 entry in Ri corresponds to a 1 entry in Rj
AND no 1 entry in Ri corresponds to a 0 entry in Rj
AND every * entry in Ri corresponds to a * entry in Rj then go to step 7;
step 6 if j<N−1, then increment j by 1 so j:=j+1 and go to step 3;
step 7 if i<N−1, then increment i by 1 so i:=i+1 and go to step 2;
step 8 END.

### Claim 7 (depends on 2)

The method of claim 2 wherein processing rules with the Reduction Algorithm further includes the act of applying to the database a program with the steps of:
step 1 letting an index i initially be 0;
step 2 letting an index j initially be 0;
step 3 if rule Rj has valid bit=0, then go to step 6;
step 4 if j=i, then go to step 6;
step 5 if Ri and Rj are identical in every position except exactly one entry, then write * in that entry in Rj, reset the valid bit Ri to 0, and go to step 7;
step 6 if j<N−1, then increment j by 1 so j:=j+1 and go to step 3;
step 7 if i<N−1, then increment i by 1 so i:=i+1 and go to step 2;
step 8 END.

### Claim 8 (depends on 1)

The method of claim 1 wherein the rules represent a description of policies including security policies to be enforced regarding traffic at an edge device flowing in either direction.
