6 ms·

I am by no means a researcher, but, as a programmer who writes said CRUD apps for a living, I can guarantee that I derive most of my understanding of a complex

I am by no means a researcher, but, as a programmer who writes said CRUD apps for a living, I can guarantee that I derive most of my understanding of a complex business domain from the structure of the relational database backing it. And what is a relational database? A (time-evolving) subcategory of the category of finite sets! Primitive types (as sets of values) and tables (as sets of primary key values) are objects. Fields (as functions of primary keys) are morphisms. Chained foreign key traversal is morphism composition. I find this way of reasoning incredibly powerful, because it tells me quickly what kind of transactions make sense in a business domain. Of course, this is contingent on the database being well designed. It is exactly the same as with Haskell types - if you can leverage the (type system) schema to encode interesting logical properties of your (problem) business domain, then (type checking) checking a query against the schema in itself becomes a lightweight form of formal verification. One thing that must be remarked, however, is that, sadly, SQL lacks analogues of sum and product types, that is, tables whose cardinality (number of rows) is the sum or product of the cardinalities of other tables. This addition would make SQL even more powerful, but it would require a move to a more category-theory-based foundation for databases. (The relational model is based on first-order logic.)

spion 11y ago
Isn't a join of two tables essentially the product of the two tables? That said it does appear that sums are missing. Infact it seems like every mainstream language manages to fail to add sum types for some strange reason and you have to recreate them from scratch.
- catnaroek 11y ago
  An unconstrained `join` is indeed the product of two queries, and a `union all` can be used to get their sum as well. This is in the query language. But what I need is sums and products in the table language. There is a functor from the category of tables to the category of queries, which maps every table `foo` to the query `select * from foo`, however, a table isn't the same thing as a query: table fields may contain user-entered data, whereas query fields are always computed from table fields. To give a concrete example, consider a database with two primitive tables, `male` and `female`. A primitive table is “independent” in the sense that you can add or remove rows from it at will. In other words, a primitive table behaves just like a normal SQL table. Now define the derived table `person` as the sum of `male` and `female`. Because `person` is derived, you don't explicitly add or remove rows from it. Instead, every time you add or remove a `male` or `female`, a corresponding `person` also gets added or removed. What I want is the ability to add the field `name` to the `person` table directly, without it existing in either `male` or `female`. You can't do this in SQL. The situation is similar for products.
  - spion 11y ago
    I still don't understand. What you call derived tables seem like views to me. They always need to be composed of primitive tables. So there will be a primitive `name` table and the person view will be `name * (male + female)`... Admittedly everything will be in 6NF but it still seems doable. Is there a limitation that I'm missing?
    - catnaroek 11y ago
      Sorry for the delay. I wasn't really thinking of making a primitive table just for names - what would its primary key be anyway? The limitation you're missing is that SQL doesn't let you readily associate a user-entered `name` with each `person`. The best you can do is put a `name` field in the `male` table, then another `name` field in the `female` table, and use both `name`s when defining a `person` view. In my opinion, this is inelegant. What I'm thinking about can be illustated with the following gist: https://gist.github.com/eduardoleon/1e8ad9174ec5ae0386dd https://gist.github.com/eduardoleon/1e8ad9174ec5ae0386dd
      - spion 11y ago
        Created a fork with a solution.
        catnaroek 11y ago
        It isn't apparent from my identifiers, but, in my `existing.sql`, `person`'s real primary key isn't just `person_id`, but rather `(gender, person_id)`. The way you've handled it, now you have an invariant to maintain that `male_id`s and `female_id`s don't collide. If you want to define arbitrarily many sum tables in your database, this can be really hard to enforce. My `proposed.sql` doesn't have such a problem.
        spion 11y ago
        Right, which is why I initially said that sum types (disjoint unions) are missing :)
mjw 11y ago
Eh... SELECT a.*, b.* FROM a CROSS JOIN b; (SELECT 'a' AS tag, * FROM a) UNION (SELECT 'b' AS tag, * FROM b);
- catnaroek 11y ago
  As I mentioned in my comment below: https://news.ycombinator.com/item?id=10529838 https://news.ycombinator.com/item?id=10529838 , the category of SQL queries has coproducts and products, but the category of SQL tables does not. Coproduct and product tables are very useful in their own right.
  - mjw 11y ago
    Ah OK, fair enough. Not sure what definition you're using for the category of tables, but I don't think the distinction between table and query is really that significant, at least from a theory point of view. You can declare views and materialized views. In some SQL dialects you can even define triggers which allow you to 'update' them, not that I would have thought mutability would be particularly nice to reason about in a category-theoretic framework. If you really want to do theory on this stuff, just use the relational algebra, or better yet just plain first-order logic. Much nicer, you have all the products and coproducts you want, and the results can probably be re-applied to SQL with a bit of cludge-work :)
    - catnaroek 11y ago
      Triggers are an imperative hack. This is like using a C struct with an enum and a union, and claiming that C has "sum types".
      - mjw 11y ago
        Agreed that SQL is ugly as hell, but if you want to talk about its theoretical properties that's a separate debate. Theory doesn't care whether something's aesthetically pleasing, just whether it's possible.
tome 11y ago
How does SQL lack product tables? The product of the column spec (foo int, bar bool) with the column spec (baz text, quux date) is the column spec (foo int, bar bool, baz text, quux date).
- catnaroek 11y ago
  A column specification isn't a table. A table contains user-editable fields. If you have two SQL tables and compute their Cartesian product, the result is a query, not a table.
  - tome 11y ago
    Could you describe precisely the category that you are talking about and explain why it doesn't have sums and products?
    - catnaroek 11y ago
      The category I'm talking about has tables as objects, and chained foreign key traversals as morphims. In SQL, this category is freely generated ( https://en.wikipedia.org/wiki/Free_category https://en.wikipedia.org/wiki/Free_category ) from a quiver ( https://en.wikipedia.org/wiki/Quiver_%28mathematics%29 https://en.wikipedia.org/wiki/Quiver_%28mathematics%29 ) whose nodes and edges are SQL tables and foreign keys, respectively. In my proposal ( https://gist.github.com/eduardoleon/1e8ad9174ec5ae0386dd https://gist.github.com/eduardoleon/1e8ad9174ec5ae0386dd ), the category is still freely generated, but from something that has more structure than a quiver - some nodes may be designated as coproducts or products of other nodes. In either case, the category can't possibly have all coproducts and products, and that's okay with me - a database can only have finitely many tables, after all. My beef with SQL is that it doesn't allow this category to have any coproducts and products at all.
      - tome 11y ago
        What do you mean by "SQL tables"? Presumably not the type of a table (you rejected that notion when I proposed it under the name "column specification") but rather a table with all its data?

spion 11y ago

Isn't a join of two tables essentially the product of the two tables? That said it does appear that sums are missing. Infact it seems like every mainstream language manages to fail to add sum types for some strange reason and you have to recreate them from scratch.

catnaroek 11y ago
An unconstrained `join` is indeed the product of two queries, and a `union all` can be used to get their sum as well. This is in the query language. But what I need is sums and products in the table language. There is a functor from the category of tables to the category of queries, which maps every table `foo` to the query `select * from foo`, however, a table isn't the same thing as a query: table fields may contain user-entered data, whereas query fields are always computed from table fields. To give a concrete example, consider a database with two primitive tables, `male` and `female`. A primitive table is “independent” in the sense that you can add or remove rows from it at will. In other words, a primitive table behaves just like a normal SQL table. Now define the derived table `person` as the sum of `male` and `female`. Because `person` is derived, you don't explicitly add or remove rows from it. Instead, every time you add or remove a `male` or `female`, a corresponding `person` also gets added or removed. What I want is the ability to add the field `name` to the `person` table directly, without it existing in either `male` or `female`. You can't do this in SQL. The situation is similar for products.
- spion 11y ago
  I still don't understand. What you call derived tables seem like views to me. They always need to be composed of primitive tables. So there will be a primitive `name` table and the person view will be `name * (male + female)`... Admittedly everything will be in 6NF but it still seems doable. Is there a limitation that I'm missing?
  - catnaroek 11y ago
    Sorry for the delay. I wasn't really thinking of making a primitive table just for names - what would its primary key be anyway? The limitation you're missing is that SQL doesn't let you readily associate a user-entered `name` with each `person`. The best you can do is put a `name` field in the `male` table, then another `name` field in the `female` table, and use both `name`s when defining a `person` view. In my opinion, this is inelegant. What I'm thinking about can be illustated with the following gist: https://gist.github.com/eduardoleon/1e8ad9174ec5ae0386dd https://gist.github.com/eduardoleon/1e8ad9174ec5ae0386dd
    - spion 11y ago
      Created a fork with a solution.
      - catnaroek 11y ago
        It isn't apparent from my identifiers, but, in my `existing.sql`, `person`'s real primary key isn't just `person_id`, but rather `(gender, person_id)`. The way you've handled it, now you have an invariant to maintain that `male_id`s and `female_id`s don't collide. If you want to define arbitrarily many sum tables in your database, this can be really hard to enforce. My `proposed.sql` doesn't have such a problem.
        spion 11y ago
        Right, which is why I initially said that sum types (disjoint unions) are missing :)

mjw 11y ago

Eh... SELECT a.*, b.* FROM a CROSS JOIN b; (SELECT 'a' AS tag, * FROM a) UNION (SELECT 'b' AS tag, * FROM b);

catnaroek 11y ago
As I mentioned in my comment below: https://news.ycombinator.com/item?id=10529838 https://news.ycombinator.com/item?id=10529838 , the category of SQL queries has coproducts and products, but the category of SQL tables does not. Coproduct and product tables are very useful in their own right.
- mjw 11y ago
  Ah OK, fair enough. Not sure what definition you're using for the category of tables, but I don't think the distinction between table and query is really that significant, at least from a theory point of view. You can declare views and materialized views. In some SQL dialects you can even define triggers which allow you to 'update' them, not that I would have thought mutability would be particularly nice to reason about in a category-theoretic framework. If you really want to do theory on this stuff, just use the relational algebra, or better yet just plain first-order logic. Much nicer, you have all the products and coproducts you want, and the results can probably be re-applied to SQL with a bit of cludge-work :)
  - catnaroek 11y ago
    Triggers are an imperative hack. This is like using a C struct with an enum and a union, and claiming that C has "sum types".
    - mjw 11y ago
      Agreed that SQL is ugly as hell, but if you want to talk about its theoretical properties that's a separate debate. Theory doesn't care whether something's aesthetically pleasing, just whether it's possible.

tome 11y ago

How does SQL lack product tables? The product of the column spec (foo int, bar bool) with the column spec (baz text, quux date) is the column spec (foo int, bar bool, baz text, quux date).

catnaroek 11y ago
A column specification isn't a table. A table contains user-editable fields. If you have two SQL tables and compute their Cartesian product, the result is a query, not a table.
- tome 11y ago
  Could you describe precisely the category that you are talking about and explain why it doesn't have sums and products?
  - catnaroek 11y ago
    The category I'm talking about has tables as objects, and chained foreign key traversals as morphims. In SQL, this category is freely generated ( https://en.wikipedia.org/wiki/Free_category https://en.wikipedia.org/wiki/Free_category ) from a quiver ( https://en.wikipedia.org/wiki/Quiver_%28mathematics%29 https://en.wikipedia.org/wiki/Quiver_%28mathematics%29 ) whose nodes and edges are SQL tables and foreign keys, respectively. In my proposal ( https://gist.github.com/eduardoleon/1e8ad9174ec5ae0386dd https://gist.github.com/eduardoleon/1e8ad9174ec5ae0386dd ), the category is still freely generated, but from something that has more structure than a quiver - some nodes may be designated as coproducts or products of other nodes. In either case, the category can't possibly have all coproducts and products, and that's okay with me - a database can only have finitely many tables, after all. My beef with SQL is that it doesn't allow this category to have any coproducts and products at all.
    - tome 11y ago
      What do you mean by "SQL tables"? Presumably not the type of a table (you rejected that notion when I proposed it under the name "column specification") but rather a table with all its data?