tag:blogger.com,1999:blog-3346090548501966296.post8670182916233932554..comments2024-03-26T05:03:04.875-07:00Comments on Perspectives on LedgerSMB: Math and SQL Part 6: The Problem with NULLsChris Travershttp://www.blogger.com/profile/06211762965865744803noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3346090548501966296.post-20902488531519794222014-09-15T01:05:36.557-07:002014-09-15T01:05:36.557-07:00As to my truth table, the fact it doesn't outp...As to my truth table, the fact it doesn't output "unknown", that is just the = and <> operators. In contrast, AND/OR/NOT etc are free to output "unknown" if the user wishes it. Likewise XNOR and XOR, the boolean-specific analogies to = and <>, are free to output "unknown" as well.<br /><br />But since JOIN etc are based on = by default (assuming an equi-join), they would treat "unknown" as equaling "unknown".<br /><br />That being said, Postgres has a feature where you can use a comparison operator of your choice other than "=" to determine when things match in a JOIN, and if the default behavior is as I say, users can tell a DBMS with that feature to use their differently-named general-equality-op-that-treats-unknown-unequal-to-unknown instead, so to get 3VL-based JOIN behavior.<br /><br />Note that what I envision, if users create multiple operators with overlapping signatures, such that either could potentially be called by the system when a user invokes some 'foo' with the same 2 inputs, it is expected both operators would return the same answer for any overlap, and if they don't, that is considered an error (if not caught by the system then a bug in the user's logic).<br /><br />Does that answer your questions?Darren Duncanhttps://www.blogger.com/profile/14457831481137852460noreply@blogger.comtag:blogger.com,1999:blog-3346090548501966296.post-18563936864120584842014-09-15T01:04:40.766-07:002014-09-15T01:04:40.766-07:00The automatically system-provided "=" op...The automatically system-provided "=" operator that I envision would have a signature of (any,any) and thus for all intents and purposes users can not overload it with some other meaning. The system-provided "=" would be very strict and only return true when both inputs are exactly the same value, and false otherwise. This "=" definition would also determine the behaviour of operations like JOIN or UNION or IN etc. For "=" to return true, the inputs must already be of a common type without conversion or coercion, and the same value as that type determines. Using "=" between values of 2 different types returns false, including examples like this: 0=0.0, 0='0', 0=false, etc.<br /><br />The automatically system-provided "<>" or "!=" operator also has the signature (any,any), not user-overridable, and is always the logical 'not' of the result of "=".<br /><br />Other system-provided operators like "<",">" etc are defined separately per type and only between those types, so eg (integer,integer) and (text,text) exist but not (integer,text) or (integer,unknown) etc, however these are ones users can define.<br /><br />The system only defines boolean logical operators like AND,OR,NOT etc which have signatures (boolean,boolean), however users can define others like (boolean,unknown) to add the N-valued logic semantics.<br /><br />What I envision is that if some operator signature is system-defined, users can not overload it, and so code that only uses system-defined types won't change behaviour if users define more stuff; however, users can define signatures for operator base names that don't exist yet, thus extending the system.<br /><br />Actually, speaking to Muldis D, it actually has an extra feature where the previous paragraph doesn't have to be true. In the language, user code lives in one or more packages, and the system built-ins are exposed in the form of one or more other packages, in the same format as those of users. Normally a user package would "use" the standard system-defined one that declares the built-ins like "=" and such which have the behavior I describe. However, they may instead "use" some substitute package which is arbitrarily different from the standard built-ins one, that is free to define "=" differently for example, eg a package that decides to fully emulate SQL semantics. That difference of "=" only affects that user package, and other packages using the regular built-in don't have their behavior changing on them even if used in the same program, eg we cut on action at a distance. So you effectively can override almost anything, but those changes tend to be package local, for safety. This feature is particularly savvy for, say, different parts of a program wanting to use different versions of a common dependency or language version, say, that are mutually incompatible, and package names are fully qualified with authority and version number.<br />Darren Duncanhttps://www.blogger.com/profile/14457831481137852460noreply@blogger.comtag:blogger.com,1999:blog-3346090548501966296.post-18644749691824330302014-09-15T00:59:59.681-07:002014-09-15T00:59:59.681-07:00Yes, I am assuming a strictly typed language, wher...Yes, I am assuming a strictly typed language, where also there are no automatic coercions that change a value into another value.<br /><br />The paradigm I envision is that conceptually at least a type is a set of values and said sets may overlap arbitrarily; there is a universal type, we'll call it "any" here, and all other types are subsets of it; each value may belong to more than one such type.<br /><br />Two "values" are considered the same value only if one can be substituted for the other in any possible situation without changing the program behaviour. What we normally think of as distinct types in the absence of any subtyping are then disjoint subsets of "any". Types created with CREATE TYPE in Postgres are disjoint from any others previously defined.<br /><br />A subtype-by-constraint (eg a SQL DOMAIN) are subsets of their parent type; the same operators that work for the "parent" work unchanged for the "child" because each child is-a parent.<br /><br />A subtype-by-extension (eg that adds attributes) is actually a disjoint set of values from its "parent", however any operators/etc defined for the parent typically also exist with corresponding signatures for the "child"; if necessary a separate union type can exist between the 2 for when one wants to have a variable/parameter/attribute/etc of both types. Suffice it to say I consider subtype-by-extension to be a more complicated affair than subtype-by-constraint. Alternately, the "parent" and said union type can be one and the same if it is defined as, for example, "must have at least these attributes" rather than "must have only these attributes"; the latter is what is typically instantiated so the former tends more to be a virtual type in a manner of speaking.<br />Darren Duncanhttps://www.blogger.com/profile/14457831481137852460noreply@blogger.comtag:blogger.com,1999:blog-3346090548501966296.post-1497506403342225962014-09-14T22:40:57.988-07:002014-09-14T22:40:57.988-07:00I am assuming of course a strictly typed language ...I am assuming of course a strictly typed language here, and assuming that the = operator also only makes sense between comparable types.Chris Travershttps://www.blogger.com/profile/06211762965865744803noreply@blogger.comtag:blogger.com,1999:blog-3346090548501966296.post-33645422522739559142014-09-14T22:39:51.538-07:002014-09-14T22:39:51.538-07:00I think once you are treating unknown as a bool fo...I think once you are treating unknown as a bool for comparison purposes, it makes perfect sense to treat it as a possible output. If you want to go with strict two-valued logic, I think you have to say that you only start with true and false as boolean inputs (and so if someone wants to have unknowns, they have to decide how to do the comparisons).<br /><br />Otherwise it makes no sense to me to treat unknown as a valid boolean into your truth table but not a valid output.Chris Travershttps://www.blogger.com/profile/06211762965865744803noreply@blogger.comtag:blogger.com,1999:blog-3346090548501966296.post-58757063013319078222014-09-14T20:35:51.597-07:002014-09-14T20:35:51.597-07:00Example truth table:
= | true | false | unknown
-...Example truth table:<br /><br />= | true | false | unknown<br />----------------------------<br />true | true | false | false<br />false | false | true | false<br />unknown | false | false | true<br /><br />My proposal works like that. We may have "unknown", but since comparing it with itself results in true, and with others results in false, it is still 2-valued logic.Darren Duncanhttps://www.blogger.com/profile/14457831481137852460noreply@blogger.comtag:blogger.com,1999:blog-3346090548501966296.post-29016235632332190952014-09-14T20:30:19.909-07:002014-09-14T20:30:19.909-07:00Second point ...
With your example, the operator ...Second point ...<br /><br />With your example, the operator "<" defined for (unknown-in-range,integer) would have a result data type consisting of at least 3 values, two of which are true/false, and the others being whatever the operator could infer otherwise, or unknown in the simplest case.<br /><br />This is still 2-valued logic, just the result type of the operator isn't just a boolean.<br /><br />And more importantly, the standard "<" operators provided by the system for say (integer,integer) do only return true/false.<br /><br />Keep in mind that your "<" example is not a normal less-than operator, but rather some operator that isn't less-than which shares its base name.<br /><br />A normal less-than operator is only defined for a type with a total order and only results in true/false.<br /><br />If one thinks of "<" as being the basis the system uses for being able to ORDER BY an arbitrary set of values, that is, ORDER BY is not an error only if all of the values in the column are in a common matrix bridged by one or more (consistent) true/false returning "<" definitions, then an overload of "<" that may return something else would produce an error if used here, so in practice your operator might be best with a different base name, or else you don't use ORDER BY etc on unknown-in-range.<br /><br />Third point ...<br /><br />I want to emphasize that in my proposal, "unknown" is nothing special, it is "just another value", same as a number or string are. Semantics are only ascribed to it by users. Calling your third possible return value of your unknown-in-range operator "unknown" doesn't magically turn things into 3-valued logic, it is still 2-valued logic, just as an operator that might return either a number or a string is still 2-valued logic.<br /><br />Likewise, if we assume the "=" equality/identity operator (also the basis for JOIN etc matching or not) is automatically system-defined for all types, as I think should be the way of things (especially in a system supporting union types), then the not special "unknown" is always equal to itself. This is in contrast to SQL where you can't "=" 2 values of a type without explicitly defining that operator for it. If you want to have semantics where this value doesn't equal itself, then define some operator and give it a name other than "=" when that is what you want. Similar to if you want to be able to compare a number and a string and have them compare 'same' if the string looks like a number, which normally isn't default, you declare a not "=" for that.<br /><br />Have I answered your question?<br />Darren Duncanhttps://www.blogger.com/profile/14457831481137852460noreply@blogger.comtag:blogger.com,1999:blog-3346090548501966296.post-27890258121391762672014-09-14T20:29:21.271-07:002014-09-14T20:29:21.271-07:00I have a few points to address this.
First point ...I have a few points to address this.<br /><br />First point ...<br /><br />The key of my proposal is that the system is natively 2-valued logic, and that if a user wants conceptually 3-valued logic, they have to define it explicitly as a layer over top (this can be reused in the form of an extension or library), and in terms of 2-valued logic. So you still actually have 2-valued logic, but your logical expressions are more complicated when you want to deal with unknowns.<br /><br />So, in the likely majority of cases where users only want to deal with knowns, they just use the base system and don't define/use extensions for add-ons. The system-defined boolean operators will only take or return true/false and trying to give anything else to them is an error (no such routine matching that signature).<br /><br />Users see complexity where there actually is complexity, and don't where there isn't. Two-valued logic is less complex than N-valued logic, and if users want the latter for some reason, they write more complex code, and it is easy to see when reading the code that it is supporting concepts of unknowns, or that it isn't.<br /><br />This is the opposite of SQL. In SQL, 3-valued logic is baked in at the lowest level, and users get that extra complicated behavior without it being obvious, it is hidden. In SQL, if users want to just have 2-valued logic, which usually is the case, they have to write much more verbose and error-prone code to deal with all the possible sources. My proposal is to turn this on its head, only have unknowns and their complexity when desired, and by default we don't and we have better error checking.<br /><br />Without unknowns at the fundamental level, the DBMS has a much easier time optimizing code that users write. With SQL, the DBMS often can't do many optimizations because that might change the result in the face of unknowns, even though the vast majority of the time the user doesn't want the unknowns. So the optimizing is much harder and less effective. When unknowns are booted to the user space, and used there optionally, the DBMS can have a much easier time optimizing and error-checking.<br />Darren Duncanhttps://www.blogger.com/profile/14457831481137852460noreply@blogger.comtag:blogger.com,1999:blog-3346090548501966296.post-62284608262896315692014-09-13T20:08:34.644-07:002014-09-13T20:08:34.644-07:00This is an interestng point. Polymorphism could t...This is an interestng point. Polymorphism could take you fairly far, but still not sure how to get rid of three valued logic.<br /><br />Consider the following:<br /><br />10 < n < 100<br /><br />n is unknown within that range.<br /><br />but if we are asked, is n + 10 > 15, we can say "yes it is." This could be done by treating an unknown-in-range as a type along your proposal as I understand it.<br /><br />But what if instead we have n + 10 > 35? Here we really don't know. We can't say for sure that it is true or that it is false, so it seems ot me we have to return an UNKNOWN BOOL which brings us back to three valued logic.<br /><br />How does your proposal work with a case like this?Chris Travershttps://www.blogger.com/profile/06211762965865744803noreply@blogger.comtag:blogger.com,1999:blog-3346090548501966296.post-68696749900709625582014-09-13T13:15:51.521-07:002014-09-13T13:15:51.521-07:00Chris, maybe you missed my point. My proposal is ...Chris, maybe you missed my point. My proposal is that the type system is natively strict 2-valued logic, but that it also natively supports union types and polymorphic routines.<br /><br />In this context, all the complexity related to special values is boosted out of the core and into the user-definable realm. So the same mechanisms that let you, say, declare that a table field may contain either an integer or a text say, you can declare that a field may contain either a numeric or one or more special values that are not numeric, but not say text or dates.<br /><br />Then operators can be declared overloaded, so say "function `>` (numeric, unknown)" if that exists then the system calls it when appropriate, and if it doesn't exist then trying to call that is a no-such-function error.<br /><br />Another great use for this feature particularly with numbers is you can have core numeric types without any special values but you can then represent IEEE stuff like underflow, infinity, NaN, etc as such special values, so you can use those special values when you want to and not when you don't.<br /><br />So the core DBMS system is much easier to optimize and reason about due to the 2-valued logic, and further complexity only exists when users want it, and since that faux-n-valued-logic is still defined in terms of 2-valued logic, your optimizers or reasoning still works.<br /><br />This in contrast with 3-valued logic being baked in at the lowest level, which is what I oppose.<br />Darren Duncanhttps://www.blogger.com/profile/14457831481137852460noreply@blogger.comtag:blogger.com,1999:blog-3346090548501966296.post-88024322914467629642014-09-13T07:48:43.371-07:002014-09-13T07:48:43.371-07:00Three value logic certainly leads to a lot of case...Three value logic certainly leads to a lot of cases where we can logically prove a proposition where three value logic gets in the way. But I am not sure about cases where a value really is unknown.<br /><br />Obviously suppose we have a domain where the value must be greater than 0. In such a case, logically, UNKNOWN > 0 is true, and trivially so. Three-valued logic is a mess.<br /><br />But here's the problem which I see in general (which has to do with strictly typed languages): when it comes to some language types, there is no natural value for many of these special values. So when we have numeric data, we can't just pick a number and treat it as unknown. The type system has to be able to handle special values, and once you go there, I am not sure you can get away from three or four valued logic..Chris Travershttps://www.blogger.com/profile/06211762965865744803noreply@blogger.comtag:blogger.com,1999:blog-3346090548501966296.post-28315953426253030272014-09-13T00:16:20.990-07:002014-09-13T00:16:20.990-07:00Further to that point, my Set::Relation Perl modul...Further to that point, my Set::Relation Perl module (which works now) is strictly 2-valued logic as well. Perl's undef is treated as being equal to itself, so eg if you do a join on 2 relation objects, a Perl undef WILL match itself. And Perl already has union types besides. The outer-join methods included come in several versions, one filling unmatched tuples with undefs, another letting you specify what to fill with on unmatched rows, and more options.Darren Duncanhttps://www.blogger.com/profile/14457831481137852460noreply@blogger.comtag:blogger.com,1999:blog-3346090548501966296.post-48139877546039313002014-09-13T00:11:56.291-07:002014-09-13T00:11:56.291-07:00I think the fundamentally best solution is to elim...I think the fundamentally best solution is to eliminate the 3-valued logic entirely and have only strict 2-valued logic in the database system.<br /><br />Then, in that context, we can have a series of user-definable singleton types to declare whatever reasons there are for regular values to not be present. (I heard once there was a thought of giving SQL 17-valued logic, but that didn't happen.) Then, in that context, rather than declaring a database field as nullable, you instead declare that the type of that field is a union type which ranges over the regular type plus whatever of the singletons you want to allow as alternatives when a regular type value isn't present.<br /><br />This is how my Muldis D language works, strictly 2-valued logic but supporting user-defined types and union types plus other features, so users have a lot of choice as to how they want to deal with the matter of unknown or not applicable or etc data on a context-specific basis. Likewise, there can be a user-definable singleton to emulate the SQL concept of a null, and user-definable operators for what to do when one is encountered, when emulating SQL behaviour is desired. Choice for users is good.<br /><br />I also strongly agree with your idea of having separate 'reason' fields which explain more specifically as to why a field doesn't have a regular value. (This idea is good enough that its been independently proposed before.)<br />Darren Duncanhttps://www.blogger.com/profile/14457831481137852460noreply@blogger.com