Three-Valued Logic | Hacker News Reader

Three-Valued Logic

modern-sql.com

138 pointsokket72 comments

It's noteworthy that SQL's 3VL follows Kleene's K3 logic (or, equivalently, Łukasiewicz' Ł3 logic) and not Priest's P3 logic. That is, in K3 and Ł3, an unknown (or indeterminate/null) value resolves to neither true nor false; whereas in K3, an unknown (or indeterminate/null) value resolves to both true and false.

There are some interesting ramifications of these properties, including a lack of tautologies in K3 and Ł3.

*whereas in P3?

Oops, my mistake :x

K3 has no tautologies, but Ł3 does have tautologies, e.g. P->P.

True. I should've mentioned that I was barring implication (as the context was SQL).

IEEE 1164, used for VHDL (VHSIC Hardware Description Language) has 9 distinct logic levels:

'U' uninitialized

'X' strong drive, unknown logic value

'0' strong drive, logic zero

'1' strong drive, logic one

'Z' high impedance

'W' weak drive, unknown logic value

'L' weak drive, logic zero

'H' weak drive, logic one

'-' don't care

What does it mean by "drive", if you don't mind?

Weak drive means there’s a pull-up resistor and the port will drain itself. Strong drive means you’re going direct and the port won’t.

Drive levels aside, this is called tri-state in electronics: https://en.m.wikipedia.org/wiki/Three-state_logic

The strength of the signal, basically. You can implement default or fail-safe values by having a weak state and then overriding it with a strong drive.

In this case "drive" is short for "driver current," how much current is being used to direct the voltage in a particular way. For instance, in classic RTL you have fairly big resistors between power and all your outputs driving them weakly up. But you have NFET transistors that may or may not strongly drive your outputs down. So you've always got a 'H' leading into the outputs but sometimes also a '0'.

From the article: "The SQL null value basically means “could be anything”."

I wouldn't call the NULL an unknown or as a "could be anything". It's tempting to think it's the Schrodinger's Cat phenomenon, but I choose to interpret the NULL in a less sexy way: Unknown means that the state DOES NOT EXIST. It's as simple as that. Remember in relational modeling (cardinality & ordinality) the thinking is always: zero, 1 or more than 1. The NULL is simply the zero here ( which means the state does NOT exist). Interpret it as "irrelevant".

Interpreting it as either true or false (because it is unknown) is over explaining.

> but I choose to interpret the NULL is a less sexy way: Unknown means that the state DOES NOT EXIST

That's wrong.

Why is it wrong?

Because it represents (and behaves) as unknown and not as absent.

Practical example is `1 not in (null)`

Just my 2c from SQL standards perspective:

> “Every [SQL] data type includes a special value, called the null value,” “that is used to indicate the absence of any data value”.

(http://modern-sql.com/concept/null)

For the Boolean type, null = unknown:

> Note that the truth value unknown is indistinguishable from the null for the Boolean type. Otherwise, the Boolean type would have four logical values.

(http://modern-sql.com/concept/three-valued-logic)

Although they are very closely related, I believe the general `null` value (for any data type) and three-valued logic (null for Boolean) should be separated (that's why I have two articles).

> Because it represents (and behaves) as unknown and not as absent.

It can represent both. For example, in a table of biographical data, a NULL value for DateOfDeath could represent N/A for someone still living, unknown for a dead person whose date of death is not known, and total uncertainty for a missing person who could be alive or dead.

I've seen this design in the wild quite often. It's most often attributed to the abuse of an intended original design. The original designer most likely intended the value populated in the "DateofDeath" column to imply death. The intention didn't account for someone down the system's evolution to imply "ALLOW NULL" to be interpreted as optional.

If your table is expected to answer "how many dead people whose date of death is unknown" then you'll most certainly also need an "IsDead" (true/false) NOT NULL column. (Best separate the table into "Death" with NOT NULL DateofDeath.)

Operational concerns might push you otherwise, but I think in terms of correctly representing the world what makes the most sense is a separate table of deaths with a primary key that's also a foreign key into the table of people, and which has a nullable date of death. That lets you represent all three of "they are living", "they are dead but we don't know when they died", and "they are dead and we know when they died".

I agree with the first part of your statement:

"Because it represents (and behaves) as unknown".

But I'm also inclined to think of the unknown BECAUSE of (or as a consequence of) absence of data. And most importantly, this absence of data (non-existence) is useful too.

I have a problem with the logic that intends to over fit absence/unknown to mean "it could be true or it could be false" ... or worse ... "it could be both".

If you are doing this in SQL WHERE predicates:

    (T-SQL)

    WHERE IsNull(IsHivPositive, 0) = 1

I would strongly argue to reimagine the use of that "boolean" column.

However you interpret a NULL (as "value existent but unknown", "value not existent", or "no information, i.e., value might exist or not"), you will have a hard time matching your interpretation with SQL's behaviour, no matter what the standard says. In fact, interpreting NULLs as "value existent but unknown" is the most troublesome of the three interpretations, both because of SQL's rules (for instance, select * from T where A=A is empty if A is NULL, but an existent value should be certainly equal to itself even if you don't know what it is) and due to the intrinsic computational complexity of related problems (basically, related to the intractability of recognising tautologies).

The closest to a sensible semantics that I have seen is a 2012's paper titled "On the Logic of SQL Nulls", which argues that the "correct" interpretation of NULL is "value not existent". It is a quite theoretical paper, though, and it covers only a subset of SQL.

If you want to use NULLs meaning "value exists but is unknown" I recommend that you the papers written by Hans-Joachim Klein, mostly in the '90s. His "switching semantics" provides some very interesting rules for writing queries with NULLs, which are at least guaranteed to output a subset of the correct answers wrt some reasonable definition of "correctness" (some of his results were rediscovered recently by Libkin btw).

Why would NULL equal itself? You're basically asking for SQL to special-case the Boolean logic so that if a null value is compared to itself it returns true. Who needs that?

If you assume that NULL is a placeholder for a value that exists, you must require the basic property that A=A be true, even when A is NULL, because any value equals itself. This does not mean that NULL=NULL should always be true. So, this is just to point out one of the many examples of SQL being incompatible with a "value existent, but unknown" semantics. NULLs in SQL are quite a mess.

It represents something that is there that you don't know the value of. So when you use it as part of an expression even as a counterpart to a term that you know the value of, it "corrupts/interacts" so that the return value of the expression is unknown whereever the expression's return value is dependent on the value that we had chosen to represent with NULL.

This is different semantics from say, taking the AND with a term that is not present, which in most conventions would have us substitute the identity value (i.e. TRUE), so that the return value is TRUE if and only if the known value is TRUE; instead, we have that the return value in SQL is NULL.

NULLs are built into the algebraic and arithmetic machinery of SQL. You can see how the equality operator (=) acts in the face of NULLs.

    = | F | T | N
   ---+---+---+---
    F | 1 | 0 |
   ---+---+---+---
    T | 0 | 1 |
   ---+---+---+---
    N |   |   |

Using the SELECT 1=NULL; syntax of SQLite we can see that SQLite does not even attempt to provide an answer. What would we say of something that cannot be determined? We say that it is _indeterminate_.

So we can find out how NULLs behave by seeing what our database does (or reading the SQL spec.) But how we _interpret_ NULL is context and application specific. It's completely valid to interpret NULL as "data-is-missing" or "does-not-exist" if you so wish. Maybe the more reasonable interpretation is "unknown" as the article urges.

However you have urged us to regard it (not the result of its operations which is another thing) as – at one and the same time – "the state does-not-exist", "zero", "irrelevant" which is unreasonable. Treating NULLs as unknowns and the results of operations on NULLs as indeterminate is a better recommendation I think even though ultimately the interpretation is application and context specific.

I like to think of it as 'outside the current set'. Saying it doesn't exist is like saying sqrt(-1) doesn't exist, yet it does, it's just 'outside' the set of real numbers.

In a strongly typed language with a boolean type, a comparison to null would require a type change. It's 'outside' the set of the boolean type.

> I like to think of it as 'outside the current set'.

Yes, if it exists (as an element of some set), then it is definitely outside the declared set of values. The main question is how we can formalize it, particularly, by defining the set NULL is a member of. For example, the following general approaches are possible:

o Extend (any or some) set of values with a special element (NULL)

o NULL = 0 (empty set)

o NULL = <> (empty tuple)

o Treat NULL as non-existence which entails having no-op if it is met, for example, 2 + NULL + 3 = 5 (just delete NULL which means skip it).

There are 16 possible dyadic operators for two-valued logic (two inputs, each with one of two possible values, mapping to a result with two possible values = 2^(2^2)). If you have either NAND or NOR as a primitive, you can construct the others from it.

There are 19,683 possible dyadic operators for three-valued logic (3^(3^2)). I don't know if there's an equivalent minimal set of primitives from which you can construct those.

The answer is yes; either NAND or NOR will work. You're just mapping a finite list of input configurations to a finite number of outputs. Any Turing complete system will be able to emulate it just by enumerating all of the possibilities.

Surely there are minimal subsets of functionally complete operators, in general different ones for different three-valued logics. E.g., for Łukasiewicz's logic (L3), ∧ (conjunction) and ⟶ (implication) will do (implication is not definable using other operators).

I doubt that you could define, L3's operators just with NAND (or NOR). In L3, "N implies N" is T, and "not N" is N (where N is the third truth value). So, in one case, a formula whose components are all evaluated with N has truth value T, and in the other has truth value N. This is not a proof, of course, but I'd like to see such a definition of NAND :)

Interestingly enough, with F571 SQL's propositional fragment is functionally complete: any three-valued truth table can be defined. For instance, Łukasiewicz's P ⟶ Q can be expressed with

    (not P or Q) or (P is unknown and Q is unknown)

and the Słupecki operator, which is needed to obtain a functional complete system from L3, can be expressed with:

    (P or unknown) and unknown

> You're just mapping a finite list of input configurations to a finite number of outputs. Any Turing complete system will be able to emulate it just by enumerating all of the possibilities.

I don't follow. How does that bear on what minimal set of operators have to exist as givens in order to construct all the operators necessary to provide such a mapping?

How many of those 20k operators are useful though?

I remember reading about this in Stephen Wolfram’s pretty awful A New Kind Of Science. He attacked exactly this problem (and similar ones) by sampling brute-forced spaces. Not very sophisticated, and written extraordinarily badly.

Your comment on dyadic enumeration was really interesting.

I hadn't considered it before but it's amazing how fast the space of available "logic gates" blows out from just a simple transition of binary to trinary.

Working on a database-driven application. I'm pretty ok with how SQL treats NULL, except for one thing: the empty sum being NULL instead of 0.

I'm also curious as to why this is the case [?]. A quick search yielded a discussion on StackOverflow [1], where people were similarly surprised, but at least pointed out that this is spelled out in the SQL 92 spec [2] (page 126). The relevant part:

    b) If AVG, MAX, MIN, or SUM is specified, then
      Case:
        i) If TXA is empty, then the result is the null value.

[1] https://stackoverflow.com/questions/12730457/why-does-sum-on...

[2] http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt

[?] As in, the design decision behind it. By comparison, the NULL + 10 = NULL concept seems obvious.

It seems that way you get more information from a sibggle operation.

Indeed. The cardinality of the empty set is zero, right? - and would there not be all sorts of problems in the formalization of number theory if this were not the case?

Now you have me wondering if, for any given database containing nulls, there is an equivalent normalized schema that represents the same information without nulls - for example, if you have a Student table with a Date of Graduation attribute that might be null, use instead an additional table of Graduated Students. It looks to me like there might be some tricky corner cases in defining 'equivalent' (you cannot query the second database for students with null graduation dates, but you can query for those without graduation dates.)

If so, then the follow-up question is whether there is a three-valued logic that always gives the same result as a particular null-free representation (my guess is yes and no, respectively.)

Another difference is that the latter schema would allow students to have multiple graduations. Which could be totally valid, but in that sense it's not equivalent to the former schema.

For the purposes my question, it would be a complication, but resolvable by using a unique identifier. Perhaps I should have limited my speculation to databases that are in at least first normal form.

I'm not sure how the 1NF limitation helps the question. One-to-many relations can certainly exist in 1NF. If the question is amended to specify that the table that represents the nullable column must have its primary key also be its foreign key to the main table, then I agree that the answer is "yes".

I thought 1NF was a solution to a follow-on problem with handling repeating groups, that, on reflection, I see does not exist.

True, False, and https://thedailywtf.com/articles/What_Is_Truth_0x3f_

Drupal 8 access check system uses 3VL as well: Allowed, Forbidden, Neutral. What I found interesting is the only difference between AND / OR is the Allowed - Neutral case: OR resolves that as Allowed while AND resolves that as Neutral. Otherwise, X AND/OR X is obviously X and F AND/OR X is F. Sounds quite logical but the truth table does look weird with so little difference.

In other words, at the end of the day, when making a decision to deny or grant access using a bunch of these 3VL checkers, you use two rules: 1. If anyone forbid, then it's a deny. 2. If no one forbid, if running OR then you need at least one Allowed when running AND then you need to have all of them saying Allowed.

Interesting that NULL = NULL is Unknown. I'm not a fan of random values trashing my equivalence relations (looking at you, javascript NaN), but I'm sure there are practical reasons.

It's exactly what NULL is about: the NULL value signifies "unknown", and as soon as you have an unknown value on either side of a relational operator, the result must also be unknown.

Just because you aren't aware of the value A or the value B, that doesn't mean that A is the same as B.

Having done SQL development for a long time I think while that is technically correct in practice it causes too many issues and is a mistake.

Many values in a database are approximate especially if representing real world values, but in our logic we treat them as equal even if they really aren't exactly equal, because that's practical. At least GROUP BY / aggreagates treats null equal, this was done for practicality and is a special exception which drives home the point.

In the end x == y OR (x IS NULL AND y IS NULL) simply wastes my time and adds no value to me along with the other issues that come with not simply allowing x == y checks like every normal programming language I use.

Without a doubt. The root of many difficulties is SQL-X using NULL as a Not Set State instead of as a Value.

However, Value representations have their own issues, which can be seen in vulnerabilities that have occurred in non-SQL where the corresponding checks had not been performed.

In response to this is error based exceptions. Tradeoffs that we all live with.

You can use `A IS NOT DISTINCT FROM B` to compare if you want to treat NULLs as equal instead of unknown.

Unfortunately it is poorly supported.

See http://modern-sql.com/feature/is-distinct-from

looking at you, javascript NaN

That's not a JavaScript thing, it's an IEEE 754 floating point standard thing and is the same in every programming language that implements that standard (which is basically all of them). But for some reason only JavaScript developers seem to be bothered by this.

Furthermore IEEE 754 floating point numbers don't have many properties that you'd expect from 'real' numbers. For example addition is not always associative and the distributive law does not always hold.

it's because javascript is unityped.

var x; 0+x => NaN is the gateway to frustration.

I understand the motivation but I disagree that NaN should not equal NaN. The es docs even explicily mention that "to ECMAScript code, all NaN values are indistinguishable from each other."

I'm writing javascript and I don't want to need to care about IEEE 754 floating point (all I know about is `Number` anyway).

If you compare two NaNs in C that happen to have the same binary representation, they are equal. Which means that a typical javascript runtime will need to check for that case, no? So if they have to make the decision between making all NaNs equal or unequal, and there's going to be a runtime check either way, why not make NaN == NaN and save us a headache?

E. F. Codd believed in having (at least) two special values in a relational model: one to signify an inapplicable column, and another to represent an unknown value.

For example, if you had a "person" table, the "name" column could be INAPPLICABLE if the person does not have a name, and UNKNOWN if the person's name is not known.

I was hoping this would be about three-way decisions[0].

[0]: http://www2.cs.uregina.ca/~twd/

http://thoughts.davisjeff.com/2009/08/02/what-is-the-deal-wi...

A lot of people make the mistake of trying to understand SQL NULL, like it's some kind of intelligent system with an underlying model behind it. It's not. It's a collection of various special-case behaviors that "make sense" in some contexts and cause confusion in many others.

Tony Hoare, who introduced null in Algol in 1965, calls it his $1b mistake https://www.infoq.com/presentations/Null-References-The-Bill....

Yes, because it is a null reference.

SQL's null is a value. The difference is that processing null values does not cause exceptions in SQL.

It doesn't cause early terminations but it certainly does cause errors.

*Edit: exceptions :)

The problem with nulls in c++ etc. is that every reference type is forced to be nullable. There is no opt out of that semantics. You get passed in an object of type O and it is really a sum type of O + Nothing. It means you need to do runtime checks everywhere and reason across call boundaries. You need to look at he code inside that method! That so un-OO!

In Db land you can make a column not nullable. Bit the SQL languages like PLSQL TSQL etc have the same issue.

C++ references are non-nullable by design. They are sane in that regard. Pointers are nullable, of course, but at least they are syntactically conspicuous and anyway pretty rare in modern C++.

I would add: the reason it is a issue in C++ is because the algebra around pointers doesn’t support the NULLs explicitly:

  - the results of any operations over nulls run as if the pointer were not null
  - while anyhing you do in SQL with NULL would explicitly have a mapping to either a correct value or another NULL

This is all said knowing that it’s quite easy to understand why is that the case.

> SQL's null is a value.

It is known to be one of the major controversies because originally NULL means the absence of a value which entails that it is not a value. Hence, if there are no values, then we cannot do any operations. Yet, for whatever reason (avoiding exceptions etc.) expressions with NULL need to be evaluated and hence NULL is treated as a value. So we get a problem: NULL is not a value AND NULL is a value. There are different views on this problem and the solution implemented in SQL (and three-valued logic) is probably not the best one.

This is a controversy outside of SQL.

SQL is pretty clear what null is:

> “Every [SQL] data type includes a special value, called the null value,”[0] “that is used to indicate the absence of any data value”[1]

(http://modern-sql.com/concept/null)

[0] SQL:2011-1: §4.4.2 [1] SQL:2011-1: §3.1.1.12

Which is worse. Null references are at least relatively fail-fast. SQL null propagates and so you get the error a long way away from the original source, like with Javascript's "foo is not a property of undefined".

Exactly. I've wondered why no SQL implementation (that I know of) has optional assertions like "join exactly 1 some_table" or "select assert-not-null(some_column)". I don't see any reason why this would be a performance killer; in fact, it might even be possible to prove and then cache with the query plan.

I'd guess that propagation is by design, such as for use in outer joins.

Algol's null and SQL's null are unrelated. In SQL it allows many operations to pass through an out of scope value without exceptions, like the Maybe monad. In Algol, it serves as a broken reference causing exceptions on any use.

(As the other comments already said:) null references are not the same as null values.

A database sometimes needs to model this case: the value is unknown: maybe the paper file you digitized was corrupted or destroyed, or other valid reasons this value is not known.

Whereas null references can be avoided, like in rust etc.

You sometimes need to model absence of a reference as well - that's why rust etc. have option/maybe types. Making every reference in the language possibly null was a terrible design mistake for algol, and making every value in the language possibly null was a terrible design mistake for SQL.

I disagree. It is not at all a design mistake in sql. You can have or forbid null values in tables. And you need that for many things. It is properly designed.

Rust or functional languages show you do not generally need null references, you have options instead. It is completely different.

Null in C or C++ is much more a very costly misstake. Missing data is just reality.

Data may be incomplete, the values unknown. SQL is designed for that. It is designed to handle reality. Whereas null references are not, they cause problems you do not need...

Data != reference

you can avoid the issue of allowing invalid references everywhere

you can not avoid incomplete data.

Reply on news.ycombinator.com