Relations ain’t “flat”

A new month a new job. I’m now working as a Java Application Developer for a large software consultancy. I’ll be developing Java EE applications for this job, which will be an interesting experience. I’m keen to really get my hands dirty with what is currently the de facto standard for building large business apps.

My first challenge is to get to grips with the Java Persistence API (JPA), which provides a standardised object-relational mapping (ORM) for Java applications. Basically, it takes a bunch of annotated Java classes and determines how best to map these to a relational database, taking care of foreign key constraints, inheritance, joins, and so forth. On the surface, this is all very good. Current best practice in developing these kinds of apps is to separate out the data model of the domain into a layer of simple Java beans (i.e., objects with properties and little custom behaviour), so something like JPA makes this much easier to knock together than using JDBC directly. (Although, it’s not that hard to use JDBC).

My beef is not with JPA, then, which does a reasonable job. My beef is with some of the documentation that surrounds it. In particular, most of the docs seem to be written by people with a strong OO background, but a weak logic/relational background. For example, I’m currently working through Java EE 6: From Novice to Professional by Antonio Goncalves. This is largely an excellent book, but even this author makes the same basic mistakes that are common to this literature, and indicate a lack of understanding of basic relational concepts. For example, here is a representative quote from page 105 (discussing inheritance mapping in JPA):

“How do you organize a hierarchical model into a flat relational one?”

The mistake here is in believing that relational models are in any way “flat”. I can only assume this comes from a rather literal interpretation of the usual representation as relations as tables on a page, which are (given the 2D nature of paper) naturally flat. However, any high school student will have had experience of drawing graphs and charts from data in tables, and so will know that the relations they describe are often anything but flat.

In mathematical terms, a relational database describes a hypergraph. This is a very general structure that very much subsumes simple hierarchies. If you imagine any collection of nodes in an N-dimensional space, and then connect them up with edges in almost any way you want, such a model can be described relationally in a straight-forward fashion. The same is true for hierarchies. Of course, OO models don’t just model hierarchies, but are also capable of modelling general graphs. The difference with OO is that it can only directly describe normal graphs, where each edge connects only at most two vertices (entities) – in other words, OO is limited to describing at most binary relations, much like RDF. Of course, this is not a problem as you can always reify N-ary relations into a separate entity and a bunch of binary relations.

So, neither description is correct: relations aren’t flat, and OO models are rarely strictly hierarhical. But let’s get back to the issue of inheritance. The problems, as far as I can see, of mapping inheritance hierarchies to relations come ultimately from an initial mis-design of how to map classes to relations. The common approach is to map each object to a row of a database table. Each property of the object then maps to a column in the table. This seems natural enough, but soon runs into problems. Firstly, it is difficult to represent collection-valued attributes this way. Secondly, missing attributes lead to NULL entries in the table (with all the problems they bring). Thirdly, it becomes difficult to know how best to incorporate attributes from super classes – do you collapse them all into one table, or distribute the data across multiple tables. To my mind, this mapping is just plain wrong from a logical point of view. Fixing the logical view should be the first step. After that, then you can worry about optimising access.

So, what is the correct logical view of OO and inheritance? Here, I believe OWL (the Web Ontology Language) has shown the correct interpretation. Each attribute of an OO class describes a binary relation, and so each attribute should be a separate relation (table). That may initially seem like madness, but it is the correct logical way of viewing the situation. Consider an Order class like the following:

class Order {
    Customer customer;
    Set<Product> productsOrdered;
    Address shippingAddress;
}

In the logical view I am recommending, you would have 4 relations to describe each order:

1. order: a unary relation containing the IDs (primary keys) of all orders. Thus order(x) is true if x is an order.
2. customer: a binary many-t0-one (functional) relation mapping order ids to customer ids.
3. productsOrdered: a binary many-to-many relation mapping order ids to product ids.
4. shippingAddress: a binary many-to-one relation mapping order ids to address ids.

The customer, address, and product descriptions would be similarly broken down into multiple relations.

So, how do we represent inheritance in this scenario? The answer is very simple: we simply add more relations. For example, suppose we add a new class of customers who are eligible for a discount on their orders. In Java, we might describe this as follows:

class VipCustomer extends Customer {
    double discountPercentage;
}

If the customer is a VIP customer, then we can discount their order according to the discount they are eligible for. To add this extended class, we merely have to add two new relations: VipCustomer (unary) to record the IDs of those eligible for discounts, and discountPercentage to record the discount allowed. We can then further constrain the database to ensure that all VIP customers are also customers (using a foreign key constraint). Alternatively, we can in fact infer this information using view definitions. In Datalog, we would write this as follows:

VipCustomer(X) :- discountPercentage(X,_).

This states that a VipCustomer is someone who has an associated discount percentage recorded. We can go further and infer that all VipCustomers are also customers:

Customer(X) :- VipCustomer(X).

In SQL terms, these can be written as view queries:

CREATE VIEW VipCustomer(ID) AS SELECT CustID AS ID FROM discountPercentage;
CREATE VIEW Customer(ID) AS SELECT ID FROM VipCustomer UNION ...;

Here you can start to leverage the power of the relational database to infer information for you. I recommend anyone wanting to learn about relational database design to spend some time playing with Prolog/Datalog and OWL to learn about logical modelling. Relational databases are more than just simple persistent stores: they are essentially inference engines for a restricted form of first-order logic, and you can really leverage them much better once you understand the implications of that.

Of course, you are probably screaming at me that this is terribly inefficient due to the number of joins that are required, and you are probably correct (although you should alway measure first). Once you have the logical model correct, you can then consider de-normalising the model to avoid common joins. Typically, you’d do this by finding functional dependencies, as described in most database textbooks. For example, there is only one customer and one delivery address in our order, so we can merge these columns directly into the base Order relation. However, I’d still leave the original logical design around as a set of views that map onto this base relation: the query optimiser should be able to eliminate them:

CREATE TABLE BaseOrder(Id ..., CustID ..., AddressID ...);
CREATE VIEW Order AS SELECT Id FROM BaseOrder;
CREATE VIEW customer AS SELECT Id, CustID FROM BaseOrder;
CREATE VIEW shippingAddress AS SELECT Id, AddressID FROM BaseOrder;
...
SELECT c.CustID, a.AddressID FROM customer c, shippingAddress a where c.id = a.id;

This last query should be optimised into the following by any decent query optimiser:

SELECT CustID, AddressID FROM BaseOrder;