Browse Prior Art Database

Transformation of a DNF bit map to a CNF bit map

IP.com Disclosure Number: IPCOM000029681D
Original Publication Date: 2004-Jul-08
Included in the Prior Art Database: 2004-Jul-08
Document File: 2 page(s) / 45K

Publishing Venue

IBM

Abstract

A Query Optimizer will often represent an query expression in either Disjunct Normal Form (DNF) or Conjunct Normal Form (CNF). This article describes a convenient mechanism for using bit map operations to convert from one representation to the other.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 70% of the total text.

Page 1 of 2

Transformation of a DNF bit map to a CNF bit map

This article describes a technique for switching between a Disjunct Normal Form (DNF) representation of an expression and a Conjunct Normal Form (CNF) representation. In short, the DNF and CNF are held at the same time in a single truth table, with one form represented by the ON bits, and the other represented by the OFF bits. Converting from one form to the other is done by toggling all the bits in the truth table, and then reordering the result.

     The bit map representation of Disjunct Normal Form is easily transformed to Conjunct Normal Form, making the costing of some queries much faster and more accurate. This invention is best demonstrated by an example. A query expression such as: (Col1 = 'A' OR Col2 = 'B') AND (Col1 = 'C' OR Col2 = 'D') would be represented using the following DNF bit map. :

Row # | A B C D | True/False ----------------------------------------------

0 0 0 0 0 | 0

1 0 0 0 1 | 0

2 0 0 1 0 | 0

3 0 0 1 1 | 0

4 0 1 0 0 | 0

5 0 1 0 1 | 1

6 0 1 1 0 | 1

7 0 1 1 1 | 1

8 1 0 0 0 | 0

9 1 0 0 1 | 1

10 1 0 1 0 | 1

11 1 0 1 1 | 1

12 1 1 0 0 | 0

13 1 1 0 1 | 1

14 1 1 1 0 | 1

15 1 1 1 1 | 1

     The DNF bit map spells out all of the possible relationships between the predicates that lead to a true evaluation of the expression. Each of the rows marked True (1) must be processed in order to arrive at the correct cost of the expression. The definition of Disjunct Normal Form dictates that the individual predicates within each row are ANDed together, while the rows are related by ORed relationships. For example, row number six identifies one case where this expression would be true: Col1 != 'A' AND Col2 = 'B' AND Col1 = 'C' AND Col2 != 'D'.

     However, we can have an even simpler set of rows to process if we transform the original expression from DNF to CNF. Again, this transformation is done by toggling the ON/OFF bits and then reordering the results:

1

Page 2 of 2

Row # | A B C D | True/False ----------------------------------------------

0 0 0 0 0 | 0

1 0 0 0 1 | 0

2 0 0 1 0 | 0

3 0 0 1 1 | 1

4 0 1 0 0 | 0

5 0 1 0 1 | 0

6 0 1 1 0 | 0

7 0 1 1 1 | 1

8 1 0 0 0 | 0

9 1 0 0 1 | 0

10 1 0 1 0 | 0

11 1 0 1 1 | 1

12 1 1...