Archive for the ‘CodeTheory’ Category

NULL’s a Bitch

No Comments »

Anyone that wrote any non trivial SQL query with an outer join, will know: NULL‘s a bitch. By the time you learn to write:

SELECT * FROM T  -- contains bitches.
    WHERE IFNULL(A = B, FALSE) OR (A IS NULL AND B IS NULL);

your hair has turned gray, if you did not pull it all, that is. When the ω—the symbol for ‘unknown’—was introduced by Codd, I guess he basically tried to support ternary logic. Later, he must have realized that ω, in non boolean columns, can stand for many different problem specific meta-values. In version 2 of The Relational Model for Database Management (Chapter 8), he tried to remedy the problem by splitting NULL (ω in SQL) into A-mark (applicable-value mark) and I-mark (inapplicable-value mark). But first, this sinned against Bruce MacLennan’s zero, one, or infinity principle and second, almost nobody adopted it. Hence different SQL implementations handle non trilogic usage of NULL differently. For example the expression 'A' || NULL || 'C' has different values in different SQL implementations. The same goes for aggregates, COUNT(*), NULL / 0, and indexing. Also a whole host of NULL related functions were invented like COALESCE(). Since any usage of NULL can be mimicked by adding a boolean column and some careful code, I am of the opinion that the introduction of NULL was a huge mistake, and the current standard and implementations aggravate the problem by implementing a lot of undefined or implicit behavior. Other solutions that would have been better are (user-definable) meta- or default-values. Anything but NULL.


P ⊆ NP

No Comments »

Turing Machine

Turing Machine

In computational complexity theory, P […] is one of the most fundamental complexity classes. It contains all […] problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. [P-complexity] The complexity class NP is the set of decision problems that can be solved by a non-deterministic Turing machine in polynomial time. [Turing machine] “So P = NP means that for every problem that has an efficiently verifiable solution, we can find that solution efficiently as well.” (Lance Fortnow) [The Status of the P Versus NP Problem]
C’mon, don’t tell me you know all about the P v.s. NP stuff, including NP-complete, NP-hard, Pseudo-polynomial time, NP-easy, NP-equivalent, and the whole Complexity Zoo.