6 ms·

On the subject of types, I’ve often wondered why relational databases don’t have sum types. Lots of real-world data models have these kinds of relationships, an

On the subject of types, I’ve often wondered why relational databases don’t have sum types. Lots of real-world data models have these kinds of relationships, and certainly “modeling data” is well-within the purview of a database. I know that ORMs exist, but they tend to be very bad and there’s no compelling reason to have to break off part of the database responsibility, implement it terribly (it’s divorced from the query planner, so even the best ORMs are subpar) for each application language, and put it on the client side. Yes, I understand that sum types affect the way the data is arranged, but the same approaches that are used by programming languages to model sum types in memory can be used by databases to model sum types on disk and in memory (it’s all just byte vectors at the end of the day).

zaphar 5y ago
I suspect part of the problem is that true sum types are poorly represented in many of the languages that use these databases. In a sense because of the layer these sit in the stacks they have to appeal to a lowest common denominator. If they supported tables where the rows were true sum types and polymorphic as a result many languages would find it quite difficult to interact with that database.
- throwaway894345 5y ago
  I don't understand why that would be a problem--programming languages interact with databases at runtime via SQL. I regularly use Go which lacks sum types, but there's nothing technically difficult about generating SQL that leverages sum types--except that SQL doesn't support sum types :).
  - zaphar 5y ago
    In Go returning a list of items that are one of a set of different types would be poorly handled. It's possible but very awkward. You would probably drop down to just a slice of interface{} and then have to use reflection to figure out what each item was. Dynamic languages like Python or Ruby would probably be fine but there are more languages than those out there to worry about.
    - throwaway894345 5y ago
      There are ways of modeling sum types in Go (a struct with a few fields and a tag, an interface that's only implemented by the relevant types, etc), but that's unrelated to the database/client interface.
blacktriangle 5y ago
Not a part of the SQL standard, but would PostgreSQL enumerated types be what you're thinking of? https://www.postgresql.org/docs/current/datatype-enum.html https://www.postgresql.org/docs/current/datatype-enum.html Although I guess the question is are you thinking sum types at the attribute level or sum types at the relation level? At the relation level I'm not familiar with an answer, but I can see where that would be a nice database-level solution for polymorphic associations.
- throwaway894345 5y ago
  Postgres enum types are like C enums--a bounded set of identifiers. Sum types requires a bounded set of arbitrarily complex types (not just identifiers). For example: type Event enum { KeyPress(rune) MouseClick{ x int64, y int64 } }
Joker_vD 5y ago
The relational model is a logical model; that it's backed up by a B-tree or something else should bear no consequence except in query/update performance. And you kinda can simulate the sum types, you just can't express it in the first-order way: instead of CREATE TYPE Color (Red, Green, Blue) CREATE TABLE MyTable(x Color, ...) you do CREATE TABLE MyTableRed(...) CREATE TABLE MyTableGreen(...) CREATE TABLE MyTableBlue(...) There is just no syntax to group these three tables together in all relevant queries/updates, and such skolemization is really quite painful to maintain manually.
- alexvoda 5y ago
  In what situation do you believe your solution would be better than to create a table Colors, insert the desired list of colors and have a FK from MyTable to Colors? The way I see it a single atribute relation is a sum type. Implemented in current imperfect systems as a single column table (maybe two column table if you insist on using surogate keys for various reasons)
  - Joker_vD 5y ago
    Probably in the situation where the sum types have actual payloads, instead of being simple enums. For example, if it was type SHAPE = NONE | SQUARE(w, h INTEGER) | CIRCLE(r INTEGER) | TRIANGLE(a, b, c INTEGER) | BLOB(e SVG_STRING) In my solution it entails having TABLE WithShapeNone(...) TABLE WithShapeSquare(..., w, h INTEGER) TABLE WithShapeCircle(..., r INTEGER) TABLE WithShapeTriangle(..., a, b, c INTEGER) TABLE WithShapeBlob(..., e SVG_STRING) It seems I can't easily generalize your solution, so I won't strawman it. Then again, I think the proper solution would just be adding the sum types into the system. We could have "+" implemented as a 3-column table too, but why would we? Your notice of "only values can be parametrized. Identifiers can not" in the sibling comment is exactly what I was trying to express in these threads: the relational model is first-order, not second-order, so while you can theoretically model everything with it (logician have done it), it's ugly and impractical without some extensions. Better types for "ground" values is one such extension.
    - 5y ago
mamcx 5y ago
I'm making a relational lang (https://tablam.org https://tablam.org) and this was one of the question marks for me. The #1 reason sum types was not presented is because "nobody" thought (seriously) about that for long time. See how much "null" have been with us and still you find defenders of it! The second and more broad problem, is that the relational model was NOT implemented by the RDBMS makers, not in full. To make sum types work, you NEED to support embed relations inside relations: rel Invoice rel DetailInvoice Invoice[invoice_id:1 customer:123 lines: DetailInvoice[ [invoice_id:1 line_id:1 price:10 qty: 1], [invoice_id:1 line_id:2 price:10 qty: 2] ] Then with this, do sum types comes from free: type Option Some ? None [customer_id:1 phone: [tag:Some 123-23456]] [customer_id:2 phone: [tag:None]] This will make things like storing Logs, metrics and event sourcing so much nicer! How store that is another matter, but I think is not that complicated, just none of the major rdbms have put effort on this. This is one of my dreams: Making a rdbms with this and other stuff that push the DBs to the modern way of make apps...
- cmrdporcupine 5y ago
  Frankly, understanding of what the relational model actually is has been missing from the industry even among many people who have made data management their primary focus. IMHO a lot of the penetration of the NoSQL stuff in the last decade was based on misunderstandings of the capabilities and potentials of the relational model. I think the early history of SQL was too influenced by ISAM-type stores and COBOL flatfiles and the like. Hence the vocabulary around "tables" and "columns" instead of the relations, relvars, tuples, etc. described by the actual relational algebraic model. To many of those with an OO fetish, "relational model" became synonymous with "tabular model", and the industry's early 2000's obsession with object polymorphism, OORMs middleware, etc continued the stall in relational database innovation. I feel like there is now renewed interest in this stuff, though. Your project looks really neat, for example.
  - mamcx 5y ago
    I think you analysis is correct. I also add that is related too to the languages, you point with Cobol, and I also add C, Pascal, Java, etc. When they have nulls and limited to zero queries, relationships and data modeling capabilities is not hard to see that how they are is reflected in how the DBs are too. I honestly not know about sum types until a few years ago, neither have a clue how much useful they are, so surely even today many are in the same blind spots...
lolski 5y ago
You might want to check TypeDB, which is a database with a strongly-typed query language: https://github.com/vaticle/typedb https://github.com/vaticle/typedb. It doesn't do union types yet, but it's got type inheritance, type inference, type-safe joins (with its "relation" feature). It's quite cool what you can do with it when you can express complex domain with the language. Disclaimer: I work there.
goto11 5y ago
Probably because the same can already be expressed using relations and foreign keys.
- throwaway894345 5y ago
  I don't think it can. I don't believe SQL allows you to create a fkey column that points into many different tables. You can create your own pseudo fkey column that the database doesn't know is a pointer into other tables ("type erasure") but then you have to recreate referential integrity and so on yourself, and you still run into issues querying against the table that has that fkey column in a useful way.
  - goto11 5y ago
    You don't need a FK to point to multiple tables. You would have the reference in the other direction, from multiple different tables to one table.
    - ithkuil 5y ago
      How do you ensure that only one row of only one table references the row of that one table?
      - alexvoda 5y ago
        Theoretically, this could also be achived by allowing FKs to Views. But I know of no system that allows this.
      - goto11 5y ago
        Most databases have weak support for cross-table constraints. I believe in SQL Server you can define an indexed view on the union of the tables and then apply a unique constraint on the foreign key.
tome 5y ago
> I’ve often wondered why relational databases don’t have sum types. It seems unlikely that relational databases would make the effort to add sum types whilst mainstream imperative languages don't have sum types. In turn that is probably because of a mistaken belief that subclassing was a sufficient means to achieve the same end. All is not lost, however. It's easy to simulate sum types using a field for the tag and multiple fields for the payload. The syntax for that in raw SQL doesn't look nice but in a higher level query DSL it can look lovely! https://hackage.haskell.org/package/opaleye-0.7.1.0/docs/Opaleye-MaybeFields.html https://hackage.haskell.org/package/opaleye-0.7.1.0/docs/Opa... https://hackage.haskell.org/package/rel8-1.0.0.0/docs/Rel8.html#g:11 https://hackage.haskell.org/package/rel8-1.0.0.0/docs/Rel8.h... (Disclaimer: I'm the author of Opaleye)

zaphar 5y ago

I suspect part of the problem is that true sum types are poorly represented in many of the languages that use these databases. In a sense because of the layer these sit in the stacks they have to appeal to a lowest common denominator. If they supported tables where the rows were true sum types and polymorphic as a result many languages would find it quite difficult to interact with that database.

throwaway894345 5y ago
I don't understand why that would be a problem--programming languages interact with databases at runtime via SQL. I regularly use Go which lacks sum types, but there's nothing technically difficult about generating SQL that leverages sum types--except that SQL doesn't support sum types :).
- zaphar 5y ago
  In Go returning a list of items that are one of a set of different types would be poorly handled. It's possible but very awkward. You would probably drop down to just a slice of interface{} and then have to use reflection to figure out what each item was. Dynamic languages like Python or Ruby would probably be fine but there are more languages than those out there to worry about.
  - throwaway894345 5y ago
    There are ways of modeling sum types in Go (a struct with a few fields and a tag, an interface that's only implemented by the relevant types, etc), but that's unrelated to the database/client interface.

blacktriangle 5y ago

Not a part of the SQL standard, but would PostgreSQL enumerated types be what you're thinking of? https://www.postgresql.org/docs/current/datatype-enum.html https://www.postgresql.org/docs/current/datatype-enum.html Although I guess the question is are you thinking sum types at the attribute level or sum types at the relation level? At the relation level I'm not familiar with an answer, but I can see where that would be a nice database-level solution for polymorphic associations.

throwaway894345 5y ago
Postgres enum types are like C enums--a bounded set of identifiers. Sum types requires a bounded set of arbitrarily complex types (not just identifiers). For example: type Event enum { KeyPress(rune) MouseClick{ x int64, y int64 } }

Joker_vD 5y ago

The relational model is a logical model; that it's backed up by a B-tree or something else should bear no consequence except in query/update performance. And you kinda can simulate the sum types, you just can't express it in the first-order way: instead of CREATE TYPE Color (Red, Green, Blue) CREATE TABLE MyTable(x Color, ...) you do CREATE TABLE MyTableRed(...) CREATE TABLE MyTableGreen(...) CREATE TABLE MyTableBlue(...) There is just no syntax to group these three tables together in all relevant queries/updates, and such skolemization is really quite painful to maintain manually.

alexvoda 5y ago
In what situation do you believe your solution would be better than to create a table Colors, insert the desired list of colors and have a FK from MyTable to Colors? The way I see it a single atribute relation is a sum type. Implemented in current imperfect systems as a single column table (maybe two column table if you insist on using surogate keys for various reasons)
- Joker_vD 5y ago
  Probably in the situation where the sum types have actual payloads, instead of being simple enums. For example, if it was type SHAPE = NONE | SQUARE(w, h INTEGER) | CIRCLE(r INTEGER) | TRIANGLE(a, b, c INTEGER) | BLOB(e SVG_STRING) In my solution it entails having TABLE WithShapeNone(...) TABLE WithShapeSquare(..., w, h INTEGER) TABLE WithShapeCircle(..., r INTEGER) TABLE WithShapeTriangle(..., a, b, c INTEGER) TABLE WithShapeBlob(..., e SVG_STRING) It seems I can't easily generalize your solution, so I won't strawman it. Then again, I think the proper solution would just be adding the sum types into the system. We could have "+" implemented as a 3-column table too, but why would we? Your notice of "only values can be parametrized. Identifiers can not" in the sibling comment is exactly what I was trying to express in these threads: the relational model is first-order, not second-order, so while you can theoretically model everything with it (logician have done it), it's ugly and impractical without some extensions. Better types for "ground" values is one such extension.
  - 5y ago

mamcx 5y ago

I'm making a relational lang (https://tablam.org https://tablam.org) and this was one of the question marks for me. The #1 reason sum types was not presented is because "nobody" thought (seriously) about that for long time. See how much "null" have been with us and still you find defenders of it! The second and more broad problem, is that the relational model was NOT implemented by the RDBMS makers, not in full. To make sum types work, you NEED to support embed relations inside relations: rel Invoice rel DetailInvoice Invoice[invoice_id:1 customer:123 lines: DetailInvoice[ [invoice_id:1 line_id:1 price:10 qty: 1], [invoice_id:1 line_id:2 price:10 qty: 2] ] Then with this, do sum types comes from free: type Option Some ? None [customer_id:1 phone: [tag:Some 123-23456]] [customer_id:2 phone: [tag:None]] This will make things like storing Logs, metrics and event sourcing so much nicer! How store that is another matter, but I think is not that complicated, just none of the major rdbms have put effort on this. This is one of my dreams: Making a rdbms with this and other stuff that push the DBs to the modern way of make apps...

cmrdporcupine 5y ago
Frankly, understanding of what the relational model actually is has been missing from the industry even among many people who have made data management their primary focus. IMHO a lot of the penetration of the NoSQL stuff in the last decade was based on misunderstandings of the capabilities and potentials of the relational model. I think the early history of SQL was too influenced by ISAM-type stores and COBOL flatfiles and the like. Hence the vocabulary around "tables" and "columns" instead of the relations, relvars, tuples, etc. described by the actual relational algebraic model. To many of those with an OO fetish, "relational model" became synonymous with "tabular model", and the industry's early 2000's obsession with object polymorphism, OORMs middleware, etc continued the stall in relational database innovation. I feel like there is now renewed interest in this stuff, though. Your project looks really neat, for example.
- mamcx 5y ago
  I think you analysis is correct. I also add that is related too to the languages, you point with Cobol, and I also add C, Pascal, Java, etc. When they have nulls and limited to zero queries, relationships and data modeling capabilities is not hard to see that how they are is reflected in how the DBs are too. I honestly not know about sum types until a few years ago, neither have a clue how much useful they are, so surely even today many are in the same blind spots...

lolski 5y ago

You might want to check TypeDB, which is a database with a strongly-typed query language: https://github.com/vaticle/typedb https://github.com/vaticle/typedb. It doesn't do union types yet, but it's got type inheritance, type inference, type-safe joins (with its "relation" feature). It's quite cool what you can do with it when you can express complex domain with the language. Disclaimer: I work there.

goto11 5y ago

Probably because the same can already be expressed using relations and foreign keys.

throwaway894345 5y ago
I don't think it can. I don't believe SQL allows you to create a fkey column that points into many different tables. You can create your own pseudo fkey column that the database doesn't know is a pointer into other tables ("type erasure") but then you have to recreate referential integrity and so on yourself, and you still run into issues querying against the table that has that fkey column in a useful way.
- goto11 5y ago
  You don't need a FK to point to multiple tables. You would have the reference in the other direction, from multiple different tables to one table.
  - ithkuil 5y ago
    How do you ensure that only one row of only one table references the row of that one table?
    - alexvoda 5y ago
      Theoretically, this could also be achived by allowing FKs to Views. But I know of no system that allows this.
    - goto11 5y ago
      Most databases have weak support for cross-table constraints. I believe in SQL Server you can define an indexed view on the union of the tables and then apply a unique constraint on the foreign key.

tome 5y ago

> I’ve often wondered why relational databases don’t have sum types. It seems unlikely that relational databases would make the effort to add sum types whilst mainstream imperative languages don't have sum types. In turn that is probably because of a mistaken belief that subclassing was a sufficient means to achieve the same end. All is not lost, however. It's easy to simulate sum types using a field for the tag and multiple fields for the payload. The syntax for that in raw SQL doesn't look nice but in a higher level query DSL it can look lovely! https://hackage.haskell.org/package/opaleye-0.7.1.0/docs/Opaleye-MaybeFields.html https://hackage.haskell.org/package/opaleye-0.7.1.0/docs/Opa... https://hackage.haskell.org/package/rel8-1.0.0.0/docs/Rel8.html#g:11 https://hackage.haskell.org/package/rel8-1.0.0.0/docs/Rel8.h... (Disclaimer: I'm the author of Opaleye)