Re: Working with NOR gates

"Laconic2" <laconic2_at_comcast.net> wrote in message news:Yqednae-Q9LlBh7cRVn-gA_at_comcast.com...
> This topic is a spin off from Marshall's comment that he would like a
> language with <OR> built into it, but he shies away from <NOT>. It's far
> enough off topic so that I wanted to start a new topic.
>
> Some of you may be familiar with the idea that it's possible to generate
> all
> the Boolean arithmetic operators starting with just NAND. As it turns
> out,
> it's equally possible to do that, starting with NOR.
>
[snip]

> What if I have this predicate? "The employee with emp_id 123 has a first
> name that is NOT 'FRED'". In the same relation,
> I have a predicate like this, "The employee with emp_id 123 has a first
> name
> that is NOT 'BILL'". Now the assertion of these two predicates together
> is
> like asserting "The employee with emp_id 123 has a first name that is NOT
> ('FRED' OR 'BILL')".
>
> Notice how I snuck the OR in there, without having a mechanism to express
> OR
> in relations to begin with. It's easier to think about this stuff if
> there
> are only a finite number of first names.
>
> This is just thinking out loud. It's not rigorous. But maybe some of
> you
> want to play with it.
>
>
See definitions for 'conjunctive normal form' and 'disjunctive normal form'. These concepts have been rigourously addressed within the context of query decomposition and optimisation for centralized and distributed databases. In particular, query or logical expression normalization seeks to transform user queries into a canonical form as one of the first steps of query decomposition and data localization.

Since relational calculus is based on logic, we have a very firm framework for transforming *any* set of logical predicates within an expression into any canonical normal form of choice, and it gives great indepedence from heuristics. Moreover, with complex logical queries, redundancy in terms(logical subqueries) can be detected and eliminated. I haven't looked, but Googling on disjunctinve, conjunctive, query decomposition, query normalization, relation graphs, or join graphs might yield something of interest.

Regards,

Dan

• Dan