Re: does a table always need a PK?
From: Costin Cozianu <c_cozianu_at_hotmail.com>
Date: Tue, 26 Aug 2003 17:02:30 -0700
Message-ID: <bigsaa$8650c$1_at_ID-152540.news.uni-berlin.de>
>
>
> 3-valued logic does not have a higher complexity then 2-valued logic. The
> problem is that such n-valued logics make a clean and straightforward
> interpretation of NULL values impossible. For example, if you think a NULL
> means that "there should be value here but I don't know what it is" then
> the condition "X = 1 OR X <> 1" should return TRUE, even if X is unknown,
> but the 3-valued logic will probably say something like UNKOWN. As you can
> probably guess computing the truth value of propositions with AND, OR and
> NOT under the given interpration of NULL values is already NP-hard if you
> have simple equalities and becomes undecidable if you allow simple
> arithmetic.
>
> So the bottom-line is that n-valued logics make a logical and theoretically
> sound interpreation of NULL values impossible, but keep things
> computationally tractable and simple enough to be understandable for most
> users.
>
> -- Jan Hidders
Date: Tue, 26 Aug 2003 17:02:30 -0700
Message-ID: <bigsaa$8650c$1_at_ID-152540.news.uni-berlin.de>
Jan Hidders wrote:
> Heikki Tuuri wrote:
>
>>"Bob Badour" <bbadour_at_golden.net> kirjoitti viestissä >>news:ZIN2b.963$8o2.85881998_at_mantis.golden.net... >> >>>Are you aware of any sound theory purporting to deal with the problem of >>>missing information? >> >>Hmm... 3-valued logic itself is a sound theory, I guess. But I think it is >>computationally too complex and possibly undecidable. If someone at this >>newsgroup knows about the complexity theory of 3-valued logic, please help >>us.
>
>
> 3-valued logic does not have a higher complexity then 2-valued logic. The
> problem is that such n-valued logics make a clean and straightforward
> interpretation of NULL values impossible. For example, if you think a NULL
> means that "there should be value here but I don't know what it is" then
> the condition "X = 1 OR X <> 1" should return TRUE, even if X is unknown,
> but the 3-valued logic will probably say something like UNKOWN. As you can
> probably guess computing the truth value of propositions with AND, OR and
> NOT under the given interpration of NULL values is already NP-hard if you
> have simple equalities and becomes undecidable if you allow simple
> arithmetic.
>
> So the bottom-line is that n-valued logics make a logical and theoretically
> sound interpreation of NULL values impossible, but keep things
> computationally tractable and simple enough to be understandable for most
> users.
>
> -- Jan Hidders
Correct !!! Tertium non datur is for girls
The brave users of SQL logic will get the acquired taste of doing math constructively. That's quite a noble cause to serve.
Best,
Costin
Received on Wed Aug 27 2003 - 02:02:30 CEST