CNF vs DNF

From: "Taral" <taral(at)mail(dot)utexas(dot)edu>
To: <pgsql-general(at)hub(dot)org>
Subject: CNF vs DNF
Date: 1998-10-01 17:55:39
Message-ID: 000001bded64$b34b2200$3b291f0a@taral
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-general

> select * from aa where (bb = 2 and ff = 3) or (bb = 4 and ff = 5);

I've been told that the system restructures these in CNF (conjunctive normal
form)... i.e. the above query turns into:

select * from aa where (bb = 2 or bb = 4) and (ff = 3 or bb = 4) and (bb = 2
or ff = 5) and (ff = 3 or ff = 5);

Much longer and much less efficient, AFAICT. Isn't it more efficient to do a
union of many queries (DNF) than an intersection of many subqueries (CNF)?
Certainly remembering the subqueries takes less memory... Also, queries
already in DNF are probably more common than queries in CNF, requiring less
rewrite.

Can someone clarify this?

Taral

In response to

Browse pgsql-general by date

  From Date Subject
Next Message Anand Surelia 1998-10-01 22:34:10 Help SPI
Previous Message Jackson, DeJuan 1998-10-01 16:59:31 RE: [GENERAL] IN/NOT IN operators