24 ms·

Databases, Types, and the Relational Model: The Third Manifesto [pdf]

178 points by fipar 5y ago

vlada_dvia 5y ago
Interesting read!
jrochkind1 5y ago
> What makes this book different? We feel there are two key features that make it stand out: its strong focus on the relational model, and its thorough treatment of type theory (and together, of course, the relational model and type theory are precisely the foundations referred to in the previous paragraph). To amplify: > * The relational model: We must stress that what we are not doing is proposing some kind of “new” or “extended” relational model. Rather, we are concerned with what might be called the “classical” version of that model; we have tried to provide as careful and accurate a description of that classical model as we possibly can. It is true that we have taken the opportunity to dot a few i’s and cross a few t’s (i.e., to perform a few minor tidying activities here and there); however, the model as we describe it departs in no essential respects from Codd’s original vision as documented in references [20-22]. (Indeed, we even toyed at one point with the idea of calling the book A Relational Model of Data for Large Shared Data Banks.) > * Type theory: Relations in the relational model have attributes, and those attributes in turn have types (also called domains). Thus, the relational model certainly assumes that types exist. However, it nowhere says just what those types must be, nor does it have much to say about what properties those types must have; in other words, the relational model and type theory are almost completely independent of each other (they are orthogonal, to use the jargon). In this book, we present a detailed theory of types that complements the relational model, and we explore some of its implications. In particular, we show that our type theory serves as a basis for a comprehensive model of type inheritance.
- deleted 5y ago
  [deleted]
- hikerclimber1 5y ago
  Everything is subjective. Especially laws.
- throwaway894345 5y ago
  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.
andrewingram 5y ago
Ah yes, the database textbook from my old uni. I think I managed to get a good grade on databases without ever buying it. But I remember the lecture content based on it being quite interesting.
- mpalfrey 5y ago
  Another ex Warwick person here!
  - benjiweber 5y ago
    I'm sure this article will attract the attention those of us who were taught by Hugh Darwen.
    - struct 5y ago
      I have a Darden-signed copy - one of my proudest possessions!
titovodka 5y ago
Im 2 years into my career. Is there a benefit in reading a database book cover to cover? Book in question is Database Systems by Garcia-Molina. I’ve found the material so far interesting. But I’m not sure how much value and how much information there is for me to possibly retain.
- ryanchants 5y ago
  I would suggest something more directly applicable. Textbooks are useful, but if you're looking for something to get the most out of today: SQL Performance Explained Art of SQL Database Design for Mere Mortals
  - RheingoldRiver 5y ago
    Huge +1 to Database Design for Mere Mortals. This was the second database book I read (the first was SQL Antipatterns, not a bad book but also not a good first book) and far and away the most helpful. It took me 3 days to read, I had a miserable flu after flying home from a vacation (pre-COVID), and I was still able to follow the author without any issue. I highly suggest a physical copy & writing in the margins, underlining etc, though that's something I do in general so YMMV if you don't get anything out of that. As far as "technical" books go, it's very nontechnical, and if you're already very experienced & good at normalizing it maybe won't help you THAT much, but for someone who's at all junior, I can't recommend it enough. The biggest takeaway (beyond, "what's a normalized database look like") is to keep questioning the real-life system you're working in & to ask questions of stakeholders who understand it better than you, but me saying that isn't at all doing it enough justice compared to how well the author elaborates on the point. (btw, Data And Reality is also good for this, though a lot more theoretical in approach) If you're really new to databases you'll want to supplement this with something that does normalization more formally, I don't have a great single suggestion for that. I read two of C.J. Date's books, honestly I found them mind-numbingly tedious to get through but I can't say I didn't learn from them. But...I also can't really recommend them because I was so bored by them that it made me stop reading altogether for like 4 months because I was just putting off finishing these books (LPT: always be in the middle of 2 books at the same time, unfortunately for me, both of my books were these lol). I did also read Art of SQL, it was both enjoyable & interesting, but maybe not what you're looking for if you want something super structured that will take you from point A to point B.
garmaine 5y ago
I really wish Date had any understanding of modern type theory, since that's the basis of his desired reform of SQL. His typing model is 50 years out of date.
- garethrowlands 5y ago
  Can you give examples of things this misses?
- blacktriangle 5y ago
  Heck I wish he even had any understanding of the use of NULL in real-world databases. He spends books arguing, very compellingly I might add, against the use of NULL in SQL dbs, but when asked to come up with an altenrative to NULL, he's suggestions are sentinel values and splitting out every nullable attribute into its own table. Both of these solutions are trivially rejectable.
  - Joker_vD 5y ago
    Splitting every nullable attribute is not "trivially rejectable", you absolutely can do this to represent sum types (and it doesn't mean that those should actually be stored separately: the relational model is logical model, it doesn't matter if a table is implemented with one or with two B-trees or somehow else entirely). The main problem is that you have to manually type JOINs for all of such sum-typed properties to do any useful queries/updates — and there really is no other way than write it every time anew by hand because the relational theory is just the intuitionistic first-order predicate calculus. You'd really want some second-order tools, to group those tables together... but then you essentially end with tables with sum-typed columns, and since the main idea of the relational model was to never step out of the first-order predicate calculus, the reasonable solution is probably to just introduce sum-types as actual types.
    - blacktriangle 5y ago
      Maybe trivial was the wrong word, but your second paragraph is exactly why I reject the approach to splitting out all nullable values into their own relation. Yes from a data modeling theoretical perspective it works, but from a pragmatic perspective having to join everything back together again is a worse situation than just thinking through the behavior of null in that situation. But even then things are awful. What do I do when I want to include the value of the nullable table in my result, but I want all of my records, not just the ones with non-null. So even though you've purged null from your data model you're still bringing them back with an outer join.
rwhaling 5y ago
Always an interesting read. A ton of insights, but I always find it a bit hard to make sense of, and it feels so disconnected from a modern distributed systems context. In retrospect, I think a lot of the Spark SQL Dataframe workflow comes pretty close to what D/Tutorial D aspire to - static typing, functions on relations, imperative style but fundamentally unordered, etc.; however, it's only a processing system, not a storage system. I have kept my distance from the "data lake" buzzword circles, but maybe a transactional, Spark-based data lake does approximate what Darwen/Date are going for? The only thing really missing might be nested relations?
- darksaints 5y ago
  I haven't read it but I understand where you're coming from here. Does this doc talk about the problems with nullability / ternary logic? What about algebraic sum types? Those have always been some of the most difficult aspects of relational data modeling, at least with respect to SQL.
- overkalix 5y ago
  Again, what's the difference between a data warehouse and a data lake? Honest question.
  - cdcarter 5y ago
    In my experience, a data warehouse usually has an ETL process at the beginning. Data comes in from disparate sources and on a regular basis, it is ETLd into a shape that is ready to use by the business. On the other hand, a data lake slurps in all the data as soon as it is available, in whatever form it is in. You have to process it into the business-consumable form when you query/egress it, but you don't have to know your dream schema up front.
    - lunatuna 5y ago
      My experience is similar: extract process -> raw data -> clean/merge -> model Normally you extract from source, then load to destination. There is no business logic in this process. From raw you do all of your transforms to get clean up and merge and then get it into a usable model. With big data sets I've done wtih Hadoop and then moved the clean/merged data to a standard or MPP DB for analysts. For normal sets this can all be done in a standard DB. The other part is all the data is available from raw and clean/merge for analysts to use and is kept. With the thinking the storage cost are extremely low and heading to zero. Whereas in traditional DW analysts used only the modeled sets and depending on the data earlier sets are deleted as they are for operational purposes only. Storage is considered expensive and limiting. The move to ELT and using a declarative dataops tool has been mind bending and has been a multiplier in terms of speed to get to something usable. I don't want to see another DW again.
binkHN 5y ago
Might be worthwhile to note this is copyright 2014 in the title.
emmelaich 5y ago
(2014) - according to the copyright notice.
jeff-davis 5y ago
This purely about database language semantics, not other aspects of database systems. In other words, it's a manifesto about languages for databases, and a criticism of SQL in particular. The challenges of a database language are different than those of a general purpose language. Queries live a long time, spread over all kinds of applications (and different versions) and reports and scripts. And the data is always growing and changing. Constraints and declarative queries help bridge the concerns of the readers and writers of the data. I read quite a few books by Date & Darwen, in particular, Temporal Databases and the Relational Model. Out of that came my work on Exclusion Constraints and Range Types for PostgreSQL, which allow you to deal with ranges of time (with beginning and end) much more effectively. So I believe the authors have good insights. But they are definitely in an ivory tower. They make strong claims about superiority of one approach over another without connecting with practice. You can feel their frustration that their ideas aren't put into practice, but they underestimate the difficulty of doing so. And I suspect that to bridge that gap enough to see a net benefit over SQL would require some revisions and amendments to their theories. I believe haskell has some really nice answers to problems in database languages, and that database queries would be a great application area for a haskell-like language. It's too bad traditional PL theory people and DB people don't mix a little more.
- jkhdigital 5y ago
  > It's too bad traditional PL theory people and DB people don't mix a little more. The only ones who do mix seem to be the ones who work with type theory or category theory! I predict that we’ll see an absolute revolution in about 20 years, after successive cohorts of undergrads are exposed to this stuff and slowly carry it out into academia and industry.
- tome 5y ago
  Hello, author of a Haskell library for Postgres[1] here! I agree with you. Darwen and Date have some very weird requirements, notably: 1. Requirement that "relations" should be sets not bags. Having one means you automatically have the other[2]. There's no point going out of one's way to forbid bags. 2. Requirement that the contents of "relations" should be "tuples". The contents of a "relation" should be allowed to be any data type, whether compound or not. 3. Completely ignoring sum types. 4. Forbidding NULLs even though there's an easy way to permit them sensibly: have nullability be part of the type. Overall, Darwen and Date's language design is poor from both the point of compatibility with real-world implementations and with current practice in programming language theory. I think my package Opaleye is a good candidate for what Darwen and Date's proposed "D" language should have been. [1] https://hackage.haskell.org/package/opaleye https://hackage.haskell.org/package/opaleye [2] http://h2.jaguarpaw.co.uk/posts/set-bag-irrelevance/ http://h2.jaguarpaw.co.uk/posts/set-bag-irrelevance/

178 points by fipar 5y ago

Interesting read!

> What makes this book different? We feel there are two key features that make it stand out: its strong focus on the relational model, and its thorough treatment of type theory (and together, of course, the relational model and type theory are precisely the foundations referred to in the previous paragraph). To amplify: > * The relational model: We must stress that what we are not doing is proposing some kind of “new” or “extended” relational model. Rather, we are concerned with what might be called the “classical” version of that model; we have tried to provide as careful and accurate a description of that classical model as we possibly can. It is true that we have taken the opportunity to dot a few i’s and cross a few t’s (i.e., to perform a few minor tidying activities here and there); however, the model as we describe it departs in no essential respects from Codd’s original vision as documented in references [20-22]. (Indeed, we even toyed at one point with the idea of calling the book A Relational Model of Data for Large Shared Data Banks.) > * Type theory: Relations in the relational model have attributes, and those attributes in turn have types (also called domains). Thus, the relational model certainly assumes that types exist. However, it nowhere says just what those types must be, nor does it have much to say about what properties those types must have; in other words, the relational model and type theory are almost completely independent of each other (they are orthogonal, to use the jargon). In this book, we present a detailed theory of types that complements the relational model, and we explore some of its implications. In particular, we show that our type theory serves as a basis for a comprehensive model of type inheritance.

deleted 5y ago
[deleted]
hikerclimber1 5y ago
Everything is subjective. Especially laws.
throwaway894345 5y ago
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.

andrewingram 5y ago

Ah yes, the database textbook from my old uni. I think I managed to get a good grade on databases without ever buying it. But I remember the lecture content based on it being quite interesting.

mpalfrey 5y ago
Another ex Warwick person here!
- benjiweber 5y ago
  I'm sure this article will attract the attention those of us who were taught by Hugh Darwen.
  - struct 5y ago
    I have a Darden-signed copy - one of my proudest possessions!

titovodka 5y ago

Im 2 years into my career. Is there a benefit in reading a database book cover to cover? Book in question is Database Systems by Garcia-Molina. I’ve found the material so far interesting. But I’m not sure how much value and how much information there is for me to possibly retain.

ryanchants 5y ago
I would suggest something more directly applicable. Textbooks are useful, but if you're looking for something to get the most out of today: SQL Performance Explained Art of SQL Database Design for Mere Mortals
- RheingoldRiver 5y ago
  Huge +1 to Database Design for Mere Mortals. This was the second database book I read (the first was SQL Antipatterns, not a bad book but also not a good first book) and far and away the most helpful. It took me 3 days to read, I had a miserable flu after flying home from a vacation (pre-COVID), and I was still able to follow the author without any issue. I highly suggest a physical copy & writing in the margins, underlining etc, though that's something I do in general so YMMV if you don't get anything out of that. As far as "technical" books go, it's very nontechnical, and if you're already very experienced & good at normalizing it maybe won't help you THAT much, but for someone who's at all junior, I can't recommend it enough. The biggest takeaway (beyond, "what's a normalized database look like") is to keep questioning the real-life system you're working in & to ask questions of stakeholders who understand it better than you, but me saying that isn't at all doing it enough justice compared to how well the author elaborates on the point. (btw, Data And Reality is also good for this, though a lot more theoretical in approach) If you're really new to databases you'll want to supplement this with something that does normalization more formally, I don't have a great single suggestion for that. I read two of C.J. Date's books, honestly I found them mind-numbingly tedious to get through but I can't say I didn't learn from them. But...I also can't really recommend them because I was so bored by them that it made me stop reading altogether for like 4 months because I was just putting off finishing these books (LPT: always be in the middle of 2 books at the same time, unfortunately for me, both of my books were these lol). I did also read Art of SQL, it was both enjoyable & interesting, but maybe not what you're looking for if you want something super structured that will take you from point A to point B.

garmaine 5y ago

I really wish Date had any understanding of modern type theory, since that's the basis of his desired reform of SQL. His typing model is 50 years out of date.

garethrowlands 5y ago
Can you give examples of things this misses?
blacktriangle 5y ago
Heck I wish he even had any understanding of the use of NULL in real-world databases. He spends books arguing, very compellingly I might add, against the use of NULL in SQL dbs, but when asked to come up with an altenrative to NULL, he's suggestions are sentinel values and splitting out every nullable attribute into its own table. Both of these solutions are trivially rejectable.
- Joker_vD 5y ago
  Splitting every nullable attribute is not "trivially rejectable", you absolutely can do this to represent sum types (and it doesn't mean that those should actually be stored separately: the relational model is logical model, it doesn't matter if a table is implemented with one or with two B-trees or somehow else entirely). The main problem is that you have to manually type JOINs for all of such sum-typed properties to do any useful queries/updates — and there really is no other way than write it every time anew by hand because the relational theory is just the intuitionistic first-order predicate calculus. You'd really want some second-order tools, to group those tables together... but then you essentially end with tables with sum-typed columns, and since the main idea of the relational model was to never step out of the first-order predicate calculus, the reasonable solution is probably to just introduce sum-types as actual types.
  - blacktriangle 5y ago
    Maybe trivial was the wrong word, but your second paragraph is exactly why I reject the approach to splitting out all nullable values into their own relation. Yes from a data modeling theoretical perspective it works, but from a pragmatic perspective having to join everything back together again is a worse situation than just thinking through the behavior of null in that situation. But even then things are awful. What do I do when I want to include the value of the nullable table in my result, but I want all of my records, not just the ones with non-null. So even though you've purged null from your data model you're still bringing them back with an outer join.

rwhaling 5y ago

Always an interesting read. A ton of insights, but I always find it a bit hard to make sense of, and it feels so disconnected from a modern distributed systems context. In retrospect, I think a lot of the Spark SQL Dataframe workflow comes pretty close to what D/Tutorial D aspire to - static typing, functions on relations, imperative style but fundamentally unordered, etc.; however, it's only a processing system, not a storage system. I have kept my distance from the "data lake" buzzword circles, but maybe a transactional, Spark-based data lake does approximate what Darwen/Date are going for? The only thing really missing might be nested relations?

darksaints 5y ago
I haven't read it but I understand where you're coming from here. Does this doc talk about the problems with nullability / ternary logic? What about algebraic sum types? Those have always been some of the most difficult aspects of relational data modeling, at least with respect to SQL.
overkalix 5y ago
Again, what's the difference between a data warehouse and a data lake? Honest question.
- cdcarter 5y ago
  In my experience, a data warehouse usually has an ETL process at the beginning. Data comes in from disparate sources and on a regular basis, it is ETLd into a shape that is ready to use by the business. On the other hand, a data lake slurps in all the data as soon as it is available, in whatever form it is in. You have to process it into the business-consumable form when you query/egress it, but you don't have to know your dream schema up front.
  - lunatuna 5y ago
    My experience is similar: extract process -> raw data -> clean/merge -> model Normally you extract from source, then load to destination. There is no business logic in this process. From raw you do all of your transforms to get clean up and merge and then get it into a usable model. With big data sets I've done wtih Hadoop and then moved the clean/merged data to a standard or MPP DB for analysts. For normal sets this can all be done in a standard DB. The other part is all the data is available from raw and clean/merge for analysts to use and is kept. With the thinking the storage cost are extremely low and heading to zero. Whereas in traditional DW analysts used only the modeled sets and depending on the data earlier sets are deleted as they are for operational purposes only. Storage is considered expensive and limiting. The move to ELT and using a declarative dataops tool has been mind bending and has been a multiplier in terms of speed to get to something usable. I don't want to see another DW again.

binkHN 5y ago

emmelaich 5y ago

jeff-davis 5y ago

This purely about database language semantics, not other aspects of database systems. In other words, it's a manifesto about languages for databases, and a criticism of SQL in particular. The challenges of a database language are different than those of a general purpose language. Queries live a long time, spread over all kinds of applications (and different versions) and reports and scripts. And the data is always growing and changing. Constraints and declarative queries help bridge the concerns of the readers and writers of the data. I read quite a few books by Date & Darwen, in particular, Temporal Databases and the Relational Model. Out of that came my work on Exclusion Constraints and Range Types for PostgreSQL, which allow you to deal with ranges of time (with beginning and end) much more effectively. So I believe the authors have good insights. But they are definitely in an ivory tower. They make strong claims about superiority of one approach over another without connecting with practice. You can feel their frustration that their ideas aren't put into practice, but they underestimate the difficulty of doing so. And I suspect that to bridge that gap enough to see a net benefit over SQL would require some revisions and amendments to their theories. I believe haskell has some really nice answers to problems in database languages, and that database queries would be a great application area for a haskell-like language. It's too bad traditional PL theory people and DB people don't mix a little more.

jkhdigital 5y ago
> It's too bad traditional PL theory people and DB people don't mix a little more. The only ones who do mix seem to be the ones who work with type theory or category theory! I predict that we’ll see an absolute revolution in about 20 years, after successive cohorts of undergrads are exposed to this stuff and slowly carry it out into academia and industry.
tome 5y ago
Hello, author of a Haskell library for Postgres[1] here! I agree with you. Darwen and Date have some very weird requirements, notably: 1. Requirement that "relations" should be sets not bags. Having one means you automatically have the other[2]. There's no point going out of one's way to forbid bags. 2. Requirement that the contents of "relations" should be "tuples". The contents of a "relation" should be allowed to be any data type, whether compound or not. 3. Completely ignoring sum types. 4. Forbidding NULLs even though there's an easy way to permit them sensibly: have nullability be part of the type. Overall, Darwen and Date's language design is poor from both the point of compatibility with real-world implementations and with current practice in programming language theory. I think my package Opaleye is a good candidate for what Darwen and Date's proposed "D" language should have been. [1] https://hackage.haskell.org/package/opaleye https://hackage.haskell.org/package/opaleye [2] http://h2.jaguarpaw.co.uk/posts/set-bag-irrelevance/ http://h2.jaguarpaw.co.uk/posts/set-bag-irrelevance/