Hacker News Reader

"So the complaint amounts to SQLs failure to fully ‘close’ such that the result of any query would automatically be an indexed relation exactly equivalent in capability to a table. Which I guess is something every SQL user has run into from time to time, and is a source of annoyance, but doesn’t seem to have prevented people from actually using SQL to… manage… relational data."

Load up the debate in your mind about the importance of generics and how important Optional is and how important sum types are, regardless of your personal feelings about them.

Now. Once upon a time, people wrote programs with nothing but global variables and GOTO statements. They didn't even have subroutines. They wrote code nevertheless. It was just bad code, for a much greater effort than they would need to write similar code today.

The fact that people solve problems doesn't prove they're doing it optimally and that there can't be any improvement.

The good news is, this problem continues to get better and better. I've been doing some Postgres work lately, and the good news is that, unlike when I tried this several years ago, you pretty much can now switch freely between something being a table, or an array of arrays, or a select statement, etc.

The bad news, is every single path way was added ad-hoc, so they all have different names and even different naming schemes ("unnest" to turn arrays into a table, ARRAY to turn a table into an array), aren't coherently linked together, and the documentation is still fuzzy on the types of these things so it takes some experimentation to work out the correct "spelling" of all these conversions. Optimization behavior is even more opaque. I'm sure that will also get better over time. But it's a work in progress, not a completed job.

> It was just bad code,

To the point of this thread, it wasn't "bad" then, any more than Newton's ideas about satellites were bad. It was state of the art, and had room for improvement over time.

Fair point; that was some clumsy phrasing on my part. By the same standard even our best code is bad today in some way, I'm sure. (If only for being more verbose and overspecified than "CodeAI, write an optimized routine to losslessly compress video".)

The result of a query isn't a set but a multiset/bag (sets that allow for multiple instances of the same element). One popular take on this is that this "breaks" the relational algebra which is certainly true if sets are the thing you want to base everything on like a lot of mathematics today. However multisets are in of themself a very interesting structure that has interesting properties which could be helpful in understanding distributed systems and general relativity.

Things like sum types and the option monad would be powerful additions to a RDBMS but I wish that people would not be so quick to dismiss anything because it is not a set. Sets can be extremely difficult to work with, just simple things like adding numbers together as described in peano-arithmetic is bunkers compared with multisets. Everyone knows how the 19 century dream of Hilbert of grounding mathematics in logic/set theory failed but somehow everyone keeps wanting to use them for everything. In my mind this is a shame and I don't think that removing them from the one place where they have a use in society at large is a good idea.

I imagine if we were writing a new RBDMS that wasn't worried about backwards compatibility we could reduce the number of types flying around internally. I think there's a lot of historical accident in which exact variants of set are available at which point. A refinement of relational logic based on a base data structure that is a bit more pragmatic (because Codd's logic is close to pragmatic, but does still have a bit of ivory towerism in it; no criticism inteded, it was a huge advance, but I think we could tweak it a bit in modern times, and in his defense I think there were bits in Codd's work that failed to come out to the pragmatic systems for a long time, to their detriment) would probably also be helpful.

But in the meantime, back here on the ground, it is nice to at least be working in an RDBMS that can convert back and forth between these things, even if it's still klunky. I remember when I just plain couldn't, and the circumlocutions to do what I wanted to do were bigger than the business logic I needed.

The reason sets are important is that they correspond to (Boolean-valued) properties. To each set, there corresponds the property of belonging to that set. To each property, there corresponds the set of all things with that property. I think this is the key reason why the relational algebra is a good foundation for a query language. When I'm writing a query, I'm thinking of some property P, such that I want the results of the query to be all records with property P. By utilizing the correspondence between properties and sets I can translate that property fairly directly into an expression in the relational algebra, and then the magic of a relational query language is that that expression is all I need to write to carry out the query. That's the sense in which relational query languages are declarative. I just write down the property of the results I want, and I get those results automatically without having to specify how to collect those results.

Having queries return multisets rather than sets "breaks" the relational algebra in the sense that it breaks this correspondence. Results of queries no longer correspond one-to-one to properties, since properties have no multiplicity. To be fair, you can identify the property being true or the element belonging to the set with having multiplicity > 0, and the property being false or the element not belonging to the set with having multiplicity 0, and by doing this you can think of SQL queries as corresponding to sets/properties most of the time. But if you're going to think of them that way, you might as well just have them be sets in the first place. The multisets are just a needless complication. Thinking about SQL queries in terms of multisets seems to only be compatible with a more imperative, non-relational approach to the language, where you still have to think algorithmically about how to assemble the collection of results that you want, rather than just directly characterizing the results in terms of a property.

in the relational model the construct that corresponds to optional is a second table that is missing some rows

for example, every foo here has a bar, but not every foo has a baz

you can think of this as baz being an optional attribute of whatever entities the foo values identify. if the second relation is not unique on foo (maybe its primary key is both columns!) you could think of it as being a set-valued relationship, associating any number of bazzes with each foo rather than just 0 or 1

from darwen and date's perspective, having null is an error-prone construct analogous to global variables and goto statements

as a historical note, subroutines predate goto statements by about ten years; subroutines predate not only high-level languages but even symbolic assembler. it is true that many people have written programs with global variables and goto statements and no subroutines, but that wasn't because subroutines hadn't been invented yet, or even publicized; wilkes explained how to use subroutines in his 01951 book "The Preparation of Programs for an Electronic Digital Computer" https://archive.org/details/programsforelect00wilk but they were presumably invented somewhat earlier, possibly by david wheeler

the whole array construct in postgres seems like it was probably a huge mistake

"subroutines predate goto statements by about ten years;"

In academia, perhaps. Subroutines were 'expensive' in the real world for a long time. Many things we take for granted today are too expensive when 16KB is a lot of RAM. I was referring to common practice rather than academia.

"the whole array construct in postgres seems like it was probably a huge mistake"

In a cousin comment where I talk about how we might do things differently if we were starting from scratch, this is one of the biggest things I had in mind. As a column type it's plausible enough, as a generic sequence type you can wrap around any other type. Seems a basic enough primitive that we should have it around. But probably everywhere else I'm using it, I really want a more native "table" type. But I can't really have that. I can kind of see it forming, I think, as the versions march on. But at least as of the version I've been using lately, it's not quite here yet.

In general SQL struggles with type recursion. While it's not hard to see why from a performance perspective you want an engine that doesn't have to deal with arbitrarily-sized values, it gets more and more limiting every year. I've gotten a distressing amount of mileage out of using the JSON types the major engines have been forced to incorporate to stay competitive just as "Look, I just need a little tree here... I can promise it'll stay bounded in size, but I don't want to encode that as a crapton of rows" or "hey, honestly, I've got a modestly complicated structure here that my clients will decode and breaking it out the Official SQL Way is just crazy". This is the thing that really gives me that 1970s Tech feel when I'm working with SQL, and while I appreciate the slow and steady lifting of the restrictions I would definitely like to use a tech that lifted them in a thoughtful, principled manner instead of a multi-decade drunkard's walk across the design landscape.

using subroutines was common practice when 16 kibibytes was a lot of core, it was common practice before fortran existed, it was common practice before people used assemblers, and it wasn't just common practice in academia but also in places like ibm, cdc, hp, burroughs, and librascope general precision

(it's true, though, that they were expensive)

from my point of view the problem with arrays, json, etc., is not the performance but the failures of orthogonality which require you to memorize a zillion special cases, which i think is what you're saying about 'a thoughtful, principled manner'

some of my own thoughts on what that might look like are at http://canonical.org/~kragen/binary-relations

I'm glad to see Chris Date in the paper.

Chris Date has been railing about no RDBMS being an RDBMS for decades.

They aren't "complaining" about Codd, anymore than Einstein "complained" about Newton. They are making valid academic criticisms, discussing solutions, and lamenting that in the past 50 years those solutions have not been implemented in practice.

It does read kind of like a complaint to me.

The question the paper poses is ‘why’ are there no relational DBMS’s. And it places a bunch of the blame, it seems, at the fact that Codd left some things ambiguous and the people behind SQL resolved that ambiguity in a way that weakened the ‘relationality’ of the result.

But you’re right, it’s possible to read this more as ‘blameless post-mortem’ five-whying.

Why aren’t there any RDBMSs?

- Because SQL won, and SQL is not relational

Why isn’t SQL relational?

- because it’s creators misunderstood Codd’s paper in these ways

Why was Codd’s paper open to misinterpretation?

- because Codd didn’t think of these particular complexities…

Which I guess is one way to follow the ‘why’ thread.

But it does slightly ignore the important ‘why did SQL win?’ Branch…

sql won, as i understand the story, because ibm thought cobol programmers were too dumb to handle the relational algebra

i have to admit that i find sql a lot easier to read than the relational algebra, even though the latter is more aesthetically appealing

sql is kind of like golang, it makes your code a bit long-winded and tedious compared to a more crystalline minimal design, but this helps you avoid the temptation of being too clever and thus writing code you will have to debug

Which points to the blame for SQL not implementing Codd’s ideas right not lying at the feet of Codd’s being insufficiently precise, as claimed in the linked paper, but rather as a deliberate choice to simplify the relational model.

i would rather say to make the relational model more complex

SQL tables are multisets (sets allowing duplicates) rather than sets as defined by the relational model. This was likely a deliberate decision in order to make implementations simpler and faster, since it avoids some uniqueness checks. For example it is much simpler to implement UNION if you don't have to check for duplicates. But arguably this push some complexity to the user, since duplicates lead to all kinds of problems.

On the other hand three-valued logic is obviously more complex than regular boolean logic. But I don't agree with the author that three-valued is in conflict with the relational model.

As far as I know, SQL won because it was used by the first commercially successful relational database systems, and then other systems entering the marked needed to support it.

It is a bit like JavaScript. Everyone knows it has its flaws and it is easy to imagine a better alternative, but it is "good enough".

SQL is the perfect example of "worse is better". SQL was an amazing invention for its time, but it has not grown and developed the way other languages have. There is basically no industry velocity in upgrading SQL the way there was with procedural languages.

SQL and C were both invented in the '70s. While C may not have grown as much as SQL has, new major languages that handle similar tasks to C have come into their own, willing to throw out old syntax or ideas where needed.

Now, one could argue that SQLite is the Javascript of SQLs, and that T-Sql is the C# of SQL, and that PL/SQL is the COBOL of Sql, and that Postgres is the Java of SQL... but in all cases those C-derived languages were far more willing to experiment and break out of the narrow bounds set by their antecedents than SQL variants were.

Obviously there are small and interesting experiments in the DB space, but none of those are the kind of industry-standardized improvements to the formula we see in the space of C-derived languages.

> Why did they invent NULL and introduce that third truth value, UNKNOWN?

I fundamentally don't understand how you can have all of the kinds of JOINs SQL has without a NULL.

You can by using “narrow” tables (key value and key key). Download the slide notes from this presentation of how Relational.ai is doing it: https://www.slideshare.net/maxdemarzi/developer-intro-deckpo...

It seems like narrow tables solve having NULLs in the tables you store, but they do nothing about NULLs in the tables you create using, say, a LEFT JOIN. Like, if you create a database with Name, Postnomials, and Prenomials, some people don't have Postnomials or Prenomials, so even if you create three narrow tables, when you JOIN them all to form the full polite addresses, you'll end up with NULLs in the result of that JOIN.

It works a little different in “Rel” (the query language Relational.ai uses). You would create multiple definitions of what a “full polite address” is for each “case” of valid arguments/empty columns and use that going forward. A bit like a UNION without the same column width requirements.

That seems clumsy.

I would think the right approach to "SQL without LEFT JOIN" would be just to focus on making pulling down multiple related tables as distinct resultsets in a single query easier and have the client code work with a graph instead of hammering everything into a single tabular layout. Or leave the concept of "connect these two tables together and make them NULL where not applicable" as an exercise for the client.

Quite the opposite. The idea is to move as much of the business logic into the database. “Rel” definitions are meant to be written once and reused everywhere. Instead of letting the client decide different business logic every time, you capture and control it in one place.

thank you so much. Was starting to read through it and not understanding what the core problem was.

I'm pretty sure you can load a query result into an [1] in memory table and query that including generated indexes.

[1] https://dev.mysql.com/doc/refman/8.0/en/memory-storage-engin...