An important issue in programming is the Object-Relational Mismatch, but I have not seen any good explanations that use familiar terms. I came up with one involving a Family Tree application.

The idea is to store data rows that include name information and foreign keys to both parents and a spouse. (Can also store useful info like birth date, birthplace, gender and so on.) This table would obviously contain reflexive relations (self-joins) on these three foreign keys. No information about the relationships such as brother, nephew, grandparent and so on can or should be stored in this table.

The application would pull in all of this data in to a tree structure, and based on who is selected as the focus person ("me" in the tree), all of the relationship titles can be 'computed' and displayed. They are me-centric and so are not part of the data, only part of who is centered in the display.

This example points out the many and very vivid differences between a data storage method and an Object-Oriented view of data:

  • the data rows simply have links to parents and a spouse
  • data rows cannot contain any relationship titles (brother, etc.)
  • the display can show all of the titles relative to who is "me"
  • changing the "me" pointer in the display relabels all the relationships
  • all relationships of any generation previous and successive can label themselves in the display

This shows the differences between data in a database and objects at run-time very clearly. I have not seen this example given anywhere else. Does it explain the "Object-Relational Mismatch" in a useful way?

  • 2
    $\begingroup$ Do you mean object-relational impedance mismatch? $\endgroup$ – Kevin Workman Nov 7 '17 at 18:03
  • $\begingroup$ This shows the differences between data in a database and objects at run-time very clearly. Not trying to be facetious, but it doesn't show anything like that. If I tell you that there is a car on my driveway, have I shown you the car? You're stating the existence of the differences, you're not showing why they are/need to be different. $\endgroup$ – Flater Nov 8 '17 at 16:54
  • $\begingroup$ The mismatch is that objects contain other objects (the parent contains the child) but relational database child records reference the parent. Relational tables have no place to store the "here are my children" relationship, but easily stores "my parent has this identity. The object model had no need to store the parents identity because the parent "knows" its children $\endgroup$ – pojo-guy Nov 23 '17 at 14:38

I'm not seeing an explanation of object-relational mismatch there for two reasons:

  1. What are the objects? You've sketched a database table definition and a visualisation, but I don't see a sketch of the application program's structures.
  2. As far as I can see, all of the additional information in the visualisation can be made available in a purely relational database view. I've done this kind of hierarchy visualisation with CTEs.

This isn't an example, but rather an explanation.

Here is how I think about this issue. In the early days of computing, machine language and assembly language, the meaning of the program and its constructs were almost entirely in the heads of programmers. The program meant what the user thought it meant and the output (bunch of numbers) was interpreted accordingly.

With each programming language advance more and more of the meaning (the semantics) of the program was captured by the language itself, which, among other things made it possible for one programmer to read and understand another's work. Procedures (with appropriate names) and functions were a big advance. It is why you are always encouraged (required in the workplace, of course) to use intention revealing names for even simple things. It is also why the Obfuscated C contest is such "fun."

Object Oriented languages take the inclusion of semantics in the program to a new level. A class encapsulates an idea and it uses several names to convey that idea. You should be able to understand a class and its behavior by knowing a few public names with brief descriptions of their intent.

An OODatabase contains Objects and so the semantics of the application as a whole are captured in those stored objects. You can think of an OODatabase as optimized for semantics, for meaning.

A Relational Database, however, which is a set of tables, with operations on tables, captures the semantics of tables not the semantics of the concepts intended by the data stored in the tables. You can, of course, capture some of it by building tables for the data that might constitute the implementation of an object. Somewhat possible, but harder, to capture the operations (in modern Relational Databases). However, the relational database is optimized for speed of retrieval and creation of new tables, as well as for the minimization of redundancy. In order to do that, the tables in, say, SQL are Normalized, which breaks them into parts. Thus what you put together to try to capture the semantics of an object are broken up for optimization.

So, once again, the semantics of the application or system in SQL is captured outside the database in the applications that save, retrieve, and use the data.

SQL databases are normally fantastically efficient. OODatabases less so. On the other hand, one captures the meaning while the other doesn't (and can't if optimization is to be achieved). With an SQL database, the user/programmer thinks about the tables. In an OODatabase he/she thinks about the concepts captured in the objects.


To @Peter Taylor: "Not So". In the example, the objects are people, and each person can have two parents and a spouse. So, that is one reason why a CTE will not solve this problem directly.

For the other reason, please refer to this article: Graph Algorithms in a Database: Recursive CTEs and Topological Sort with Postgres

Which says near the end:

Warning: Here Be Dragons Although topologically sorting a generic graph using SQL is a fun challenge, for anything other than small graphs this method would be a bad idea in real code. Why?

Well, our method computes the topological sort by traversing every possible path in the graph that leads from a node with no parents to a node with no children. In the worst case, for dense graphs that have close to the maximum number of edges, the number of paths will be exponential in the number of vertices! (Specifically, O(2^V), assuming no cycles.) Clearly, this isn't going to scale well.

In contrast, implemented in procedural code, topological sort runs in O(V + E) time, where V is the number of vertices and E the number of edges. (Check out Kahn's algorithm, which is my favorite way of doing it.) Worst case, for dense graphs, i.e. E = O(V^2), it will run in O(V^2) in the number of vertices V.

So in fact, unless our graphs were always very small, we'd be much better off doing the topological sort outside the database for a generic graph. The tree example is not exponential and would be safe to use in real code, although I certainly don't guarantee it will perform well when the trees get very large.

Maybe there's a non-exponential SQL query for topological sort, but if so, I haven't been able to find it yet. Either way, the final point stands: it's possible to be too clever. Just because you can compute anything in SQL doesn't mean you necessarily should.

I think that the application should move all the rows in to a collection of objects, forging the three possible links as it goes and making the links run both directions. This will only work in the program, not in the SQL query.

  • $\begingroup$ Welcome to Computer Science Educators! Answers are not the right way to reply to another answer or question; we use comments for that. Seeing as you don't have 50 reputation, you can't comment just yet. If you feel like you must reply with more than a comment, then be sure to do so in a way that still answers the question. $\endgroup$ – ItamarG3 Nov 8 '17 at 13:55

Your Answer

