7 ms·
Three-Valued Logic
- abraae 9y agoTony Hoare, who introduced null in Algol in 1965, calls it his $1b mistake https://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Tony-Hoare https://www.infoq.com/presentations/Null-References-The-Bill....
- MarkusWinand 9y agoYes, 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.
- rixed 9y agoIt doesn't cause early terminations but it certainly does cause errors.
- MarkusWinand 9y ago*Edit: exceptions :)
- hjjiehebebe 9y agoThe 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.
- Sharlin 9y agoC++ 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++.
- heavenlyblue 9y agoI 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.
- techno_modus 9y ago> 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.
- MarkusWinand 9y agoThis 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 http://modern-sql.com/concept/null) [0] SQL:2011-1: §4.4.2 [1] SQL:2011-1: §3.1.1.12
- lmm 9y agoWhich 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".
- default-kramer 9y agoExactly. 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.
- abiox 9y agoI'd guess that propagation is by design, such as for use in outer joins.
- ghusbands 9y agoAlgol'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.
- zkomp 9y ago(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.
- lmm 9y agoYou 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.
- zkomp 9y agoI 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.
- schindlabua 9y agoInteresting 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.
- Sharlin 9y agoIt'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.
- IncRnd 9y agoJust because you aren't aware of the value A or the value B, that doesn't mean that A is the same as B.
- SigmundA 9y agoHaving 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.
- IncRnd 9y agoWithout 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.
- nalllar 9y ago
- ak39 9y agoFrom 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.
- _pmf_ 9y ago> but I choose to interpret the NULL is a less sexy way: Unknown means that the state DOES NOT EXIST That's wrong.
- ak39 9y agoWhy is it wrong?
- the_mitsuhiko 9y agoBecause it represents (and behaves) as unknown and not as absent. Practical example is `1 not in (null)`
- MarkusWinand 9y agoJust 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 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 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).
- dvt 9y agoIt'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.
- akx 9y ago*whereas in P3?
- dvt 9y agoOops, my mistake :x
- lifepillar 9y agoK3 has no tautologies, but Ł3 does have tautologies, e.g. P->P.
- dvt 9y agoTrue. I should've mentioned that I was barring implication (as the context was SQL).
- dghf 9y agoThere 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.
- Simon_says 9y agoThe 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.
- lifepillar 9y agoSurely 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
- dghf 9y ago> 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?
- andreareina 9y agoWorking 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.
- danielbarla 9y agoI'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-an-empty-recordset-return-null-instead-of-0 https://stackoverflow.com/questions/12730457/why-does-sum-on... [2] http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt 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.
- heavenlyblue 9y agoIt seems that way you get more information from a sibggle operation.
- mannykannot 9y agoIndeed. 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.)
- kurtisc 9y agoIEEE 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
- masklinn 9y agoWhat does it mean by "drive", if you don't mind?
- rbalsdon 9y agoWeak 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 https://en.m.wikipedia.org/wiki/Three-state_logic
- dsr_ 9y agoThe 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.
- Symmetry 9y agoIn 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'.
- chx 9y agoDrupal 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.
- jeffdavis 9y agohttp://thoughts.davisjeff.com/2009/08/02/what-is-the-deal-with-nulls/ 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.
- deleted 9y ago[deleted]
- jjgreen 9y agoTrue, False, and https://thedailywtf.com/articles/What_Is_Truth_0x3f_ https://thedailywtf.com/articles/What_Is_Truth_0x3f_
- kuwze 9y agoI was hoping this would be about three-way decisions[0]. [0]: http://www2.cs.uregina.ca/~twd/ http://www2.cs.uregina.ca/~twd/
- oftenwrong 9y agoE. 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.