The Postgres database management system was originally designed as object-relational. We remind why PostgreSQL is an object-relational rather than just relational database management system, and briefly discuss what kind of object-oriented features it offers. We demonstrate how these features can be used to manage hierarchies, and how applications can benefit using them.

The discussion is illustrated with examples of SQL code based on the postgres_air database [6, https://github.com/hettie-d/postgres_air].

There are many ways to implement a hierarchy in a relational database. Techniques with names like adjacency lists and nested sets, not to mention some other RDBMS have built methods of managing hierarchies. Some of these techniques will work in PostgreSQL as well, but in this article, we will be looking at a method that is native to PostgreSQL that may not be obvious initially but is very powerful once you understand how it works.

Editor note: I wrote a book named: “Practical Graph Structures in SQL Server and Azure SQL”, and this method of managing hierarchies was not something I had seen previously! I had not seen similar in “Joe Celko’s Trees and Hierarchies in SQL for Smarties” either.

Introduction

The relational model came out from research labs into practice in the simplified form of SQL databases which gradually gain popularity and became dominating database model.

However, application developers figured out very soon that a narrow interpretation of relational model in the form of SQL is not perfect for applications other than financial transaction processing.

This happened during the period when programming languages were becoming object-oriented. Dozens of object-oriented models were proposed and some of them implemented as programming languages. Naturally, the idea to make databases object-oriented was in the air and several prototype systems were developed. This trend was summarized in [1].

The concepts of object-oriented databases were later formalized in the object-oriented database standard (ODMG) [3]. Despite aggressive expectations, object-oriented databases did not gain significant popularity, although they are suitable for some classes of applications.

At the same time other researchers were exploring more conservative approaches that could combine the relational model with object-oriented features. Their position is presented in [2]. The original Postgres system was created as a prototype demonstrating this approach. Currently all major SQL DBMSs follow this approach offering several features that can be viewed as object-oriented.

One of the most limiting simplifications of early versions of SQL (in comparison with relational model) is the restriction to fixed set of basic data types, namely, numeric types, character strings, dates and time). In contrast, the relational model requires that attribute values must belong to a domain. The elements of a domain are considered scalar (that is, their structure, if any, is not visible to the model) and an equality predicate must be defined on any domain. In plain words the latter means that it is possible to check if any two elements of the same domain are equal or are not equal. Nothing else is required, but any additional functions, operators and predicates are allowed, although the relational model itself does not provide anything for definition of such functions.

Note that such functions (or operators) are necessary to perform the operation. Relational domains are like abstract data types.

For example, consider domains of weights and lengths. Ideally, + is needed to sum weights with weights and lengths with lengths but not weights with lengths. However, both domains are represented with the same numeric type in SQL.

So, we can exploit the full power of relational or SQL query languages on top of domains that contain arbitrary complex values if we do not dive into the structure of these values explicitly. That is, we need functions to access any structural parts or other values that can be derived from the domain elements.

A composite data type is like a structure type known in many programming languages. It consists of a fixed number of named attributes. A row of an SQL table can be viewed as a composite type although early SQL does not define composite types explicitly and does not allow composite types as values of attributes.

Yet another way to go beyond the scalar values of relational domains is to use collections. A collection consist of several values of the same type, rather than just a single value. The ODMB standard specifies the following kinds of collections:

The elements of a collection usually belong to a composite type.

To make objects from the structured data structures described above we need means for definition of object methods or functions. All DBMS supporting object features provide for user-defined functions of several different kinds. However, we do not discuss any kind of functions in this article.

Hierarchies

There are several ways to define what is a hierarchy. For the purposes of this article, we define a hierarchy as an instance of a composite type that contains collections among its attributes. The type of the collection elements can also contain collections.

Hierarchies are essential for almost any kind of business, as illustrated by the following examples:

Note that last two examples contain same data organized into different hierarchies.

The importance of hierarchies for programming is obvious and was recognized long time ago. The list of data models in any database textbook starts from hierarchical data model. One of the first widely used systems (IBM IMS) provides hierarchical views for applications accessing the database. This system is usually called hierarchical although the internal structures used in this system are much more complex than just hierarchies and can be characterized as a kind of network data model.

Hierarchies were theoretically studied under the name of non-first normal form relations (NFNF or NF²). More detailed discussion of NFNF can be found in the article [5].

Modern data formats JSON and XML provide notation for representation of hierarchical data structures.

Hierarchies are so important and popular for the following reasons:

However, storing hierarchies in a database may result in several disadvantages.

If the relationship between root of a hierarchy and elements of a collection is not one-to-many, then redundancy is unavoidable. For example, if the booking hierarchy contains information on flights, then the information about each flight is stored as many times are there are bookings on this flight. Similarly, if the flight hierarchy contains collection of bookings, then each booking is stored as many times as are in this booking.

Note that this kind of redundancy was avoidable in the IBM IMS system because hierarchies returned to the application might be constructed dynamically using pointers interconnecting elements of different hierarchies.

Our take-out form the above is that hierarchies are desirable for data exchange over network but are not the best as the database storage structure.

Object-Oriented Features of PostgreSQL

Although the PostgreSQL database management system does not provide objects explicitly, it offers several features typically found in object-oriented models. We limit ourselves to discussion of data structures only in this article, although the most powerful features are related to user-defined functions of various kinds Note that the core of object features of PostgreSQL are inherited from the original Postgres prototype which was designed when neither object database models nor object models in general weren’t mature yet.

We mentioned above the importance of domains in the relational theory. Domains can be defined in PostgreSQL, but they are not as powerful as relational domains. A domain is defined as a sub-type of a basic type satisfying additional constraints. For example, we can define weight and height as positive float numbers:

The system will ensure that the constraints are satisfied:

This would cause the following error:

ERROR: value for domain weight_kg violates check constraint "weight_kg_check"

However, any operation defined on the basic type can also be applied to the values in the domain. So, a sum of weight and height will be still a valid expression.

Which would return the aptly named:

The PostgreSQL syntax for composite type definition is very similar to the syntax for table definition (CREATE TABLE) and actually any table also defines a composite type.

We’ll use the following composite type to show how to build collections in the PostgreSQL system. We define a composite type for dictionary entries:

Values of a composite type are constructed using row( ) pseudo-function. Explicit cast to a composite type is usually needed to create a value of such type:

The output:

To be able to build hierarchies we need collections as types of composite type attributes. The only kind of collections allowed as attribute type in PG is an array.

Let’s define a table containing a dictionary in every row:

This table contains a collection as a column, so, it is not in the first normal form.

We use array constructor to create values of arrays in this section. The following SQL statement populates the table defined above:

What about other kinds of collections? They cannot be stored as column values, but arrays can be converted into sets or bags and can then be used in queries as table expressions. The set-valued pseudo-function unnest extracts each element of an array argument as a separate row:

The output:

This SQL statement converts nested table into first normal form. Of course, we can extract collection from a single row of the table using conditions in where clause. The output is either set or bag depending on the existence of duplicates.

To store a set or bag as a column value, we have to convert it into an array. This can be done using array_agg aggregate. Examples can be found in the nest section.

Building and Processing Hierarchies

In this section we discuss how to build hierarchies from relations in PostgreSQL and how to use them.

We already defined simple nested table above. Our more complex example is a travel itinerary: an airfare booking that contains several passengers and several flights. A complete itinerary extracted from the postgres_air database requires data from 6 tables. In this article we build a simplified hierarchy that contains only two levels.

We need a composite type to represent a passenger in our hierarchy. PostgreSQL allows to use tables as type definitions, so we could just use the passenger table. However, this table contains columns that are not needed in the hierarchy: the booking_id column is redundant because the collection of passenger’s data will be embedded into itinerary. So, we define a type to represent a passenger in the itinerary:

The composite type it_flight combines data from two tables (booking_leg and flight):

We are now ready to extract itineraries from the relations stored in the postgres_air database. To do this, we create a view, each row of which contains a complete itinerary hierarchy for a booking. So, this view returns a nested (NFNF) relation.

PostgreSQL allows us to use relations (tables, views etc.) as composite type definitions. The query in the view definition uses sub-queries with array_agg function to build nested collections (passengers and flights):

The output produces from this view for a booking looks like follows:

The output looks like this:

So, we can obtain complete itineraries from this view and pass then to an application in response to a single SQL query.

Why the number of queries is so important?

Nearly all applications wait for response from the database server for each query they. The time needed for processing of a query touching small number of rows is negligible in comparison with time needed for network round trip. To extract data contained in the hierarchy above, a typical object-relational mapper (ORM) would execute 11 queries, making access to the database really slow.

However, the application developers will not be happy with such representation of the output. To make hierarchies acceptable for application developers we have to convert it into another format.

The PostgreSQL system provides several features for processing hierarchical data represented in JSON and XML. Our choice is JSON for this article.

To show how JSON hierarchy can be converted into PostgreSQL relations we need some JSON data. To obtain such data we store output of the itinerary view converted to JSON in a table. Of course, such table is not needed if the generated JSON is just passed to an application. Our table have only one column and will contain one row:

The following SQL statement inserts itineraries for two bookings converted into a JSON array. So, the JSON value can contain itineraries for multiple bookings, and we can pass several itineraries to an application in one SQL query. This can be done with a SELECT statement, but we need data to demonstrate conversion in the opposite direction (from JSON to relational tables).So, we store the output into a table and use RETURNING clause to show how this output looks like.

To improve readability, we use jsonb_pretty function. Note also that the view is used both as source relation and composite type definition: )

Which outputs:

The JSON output above is like the output that can be obtained from a document store.

If an application sends data in JSON format, a conversion into relational data is needed for handling of these data at the database side.

PostgreSQL provides several functions for processing SON. We mention here only those that can produce values of composite types (rather than scalar values).

The most powerful tool for conversion of JSON data into relations provided in PostgrQL is the JSON_TABLE function. This function can many levels of a hierarchy in a single invocation. However, this function is not available in versions prior to 17, and the specification of conversion is somewhat complex.

An alternative is the json_potulate_recordset function that converts one JSON object into values of a composite type at one level of hierarchy. This function converts values of JSON keys into values of composite type attributes with the same name. Missing values are replaced with defaults, extra JSON keys are ignored.

We need one more type to convert JSON data into relations:

Our first SQL statement converts the hierarchy into two rows containing values of top level attributes, but nested collections are still in the form of JSON arrays:

Which outputs:

We can use subqueries to convert JSON arrays into PostgreSQL arrays. The output of this query is exactly same as the output from the itinerary view, so we do not include it in the article.

Alternatively, we can use LATERAL JOIN to combine each row of nested collections with the top-level row. This will produce a cartesian product of nested collection, which in general does not make much sense. However, the product of passengers and flights produces data needed for boarding passes: a boarding pass is issued for every passenger for all flights in a booking.

The SQL statement is here:

The output to this statement is:

The relational data converted from JSON should be, most likely, serve as an input for INSERT, UPDATE, or DELETE statements. Our itinerary hierarchies cannot be inserted into Postgres_air database because we tried to make this hierarchy as simple as possible and did not include some of necessary columns into itinerary hierarchy.

More complex examples of hierarchies and data modification based on hierarchies can be found in the NORM framework [7]. This framework also facilitates specification of search criteria and database modification based on JSON input.

Let’s look at the big picture again. Hierarchies are desirable as units of data exchange between applications and the database. Hierarchies are also supported with standardized communication formats (JSON and XML). Why not to store hierarchies in a database without any transformation, as document stores do?

There are several reasons not to do that:

The items above suggest that storing of hierarchies in a database almost never makes sense. Generation of hierarchies on demand and conversion them to relational table is a better option from both logical and performance perspectives.

Conclusion

Hierarchies are perfect for data exchange between applications and the database but are not suitable as an internal storage format. The PostgreSQL system provides everything needed for processing hierarchies.

A reasonable approach is to use hierarchies to transfer data between an application and a database but convert data to/from relational representation on demand.

This article shows how to convert data between tables and JSON format in PostgreSQL.

References