Jetisu is a toolset for modelling with intensionally defined relations.
- a "relation" is a table with columns and rows,
- "intensionally defined" means the table is not defined a list of rows, or derived from other tables, but defined by computable rules.
Prior to the advent of the relational model, programmers' mental model of data spanned multiple levels of abstraction and required them to procedurally navigate either hierarchies or networks to access data. The relational model challenged this approach and provided a long-lived and robust mental model of data for programmers to use (Schemas and SQL).
One of the relational model's key benefits is that programmers were, to a greater extent, insulated from innovation in database technologies. This isolation reduced, or removed, the cost of adoption of innovations in technologies such as: hardware, caching, virtualisation, cryptography, storage, sharding, redundancy, indexing, query optimisation, distributed systems, etc.
The Jetisu Toolkit is exploring the possibility that the relational model can do for rules and code what it did for data. The following diagram is a representation of what this might look like:
The examples are chosen to illustrate the benefits (and/or challenges) of querying intensionally defined relations to model rules as code.
- ACT Conveyance Duty
- Australian GST
- Birthday Money
- Australian COVID vaccinations up-to-date and eligibility
- Australian COVID vaccinations mandatory for work roles
- Eligibility for rates subsidy
- Range
This example shows interactive Q&A using the same rule-set as the above "Australian COVID vaccinations mandatory for work roles" example:
You can docker run
the example Jupyter notebooks for yourself.
docker run -p 8888:8888 ghcr.io/davidpratten/jetisu:latest
Here is help on How to run the example notebooks
Every table has an intension, which is its intended meaning and its extension which is its list of rows. But not all tables are defined in the same way!
How defined | Intension (a test that is true if a row is a member of the table) | Extension (list of rows) |
---|---|---|
Extensionally defined | Natural Language | Listed out in a table |
Derived from other relations | Query in Relational Algebra, SQL, Datalog, including fixed point operators | Generated on demand or materialised for reuse. |
Intensionally defined | Computable Constraints and Rules | Generated or recognised on demand |
The idea of a non-derived relation that is defined by computable constraints and rules goes back to the 1970's and 1980's at the beginning of the relational database era. Early references include:
- Algorithmic relations proposed in 1975 by Patrick Hall, Peter Hitchcock and Stephen Todd (hereafter HHT). (PDF)
- Computed relations described in 1981 by David Maier and David Warren (hereafter MW). (PDF)
These proposals share a common assumption that computation is inherently directed. Neither paper suggested that an algorithmic, or computed relation could be defined in such a way that all directions of computation might be possible "out-of-the-box" with just a single definition.
The maturation of satisfaction solvers and of the constraint language MiniZinc have provided the building blocks for realising ideas that were put forward nearly 50 years ago. The Jetisu toolkit calls these algorithmic, or computed, relations: "intensionally defined relations".
An intensionally defined relation is
- a set of typed attributes (or columns) A, along with
- a computable predicate (or constraint) C over the attributes in A, which
- when further constrained in a relational query, is indistinguishable, (within some error bound ๐), from its finite extension of tuples (rows).
This definition closely mirrors the definition of a relation in relational database theory, and here are some implications of this definition:
Not derived from other relations: An intensionally defined relation is a standalone computational artifact and not derived from other relations.
Queried by name: An intensionally defined relation appears by name
in a query in the same way that any other relation does. e.g. If australian_gst
is an intensionally defined relation then in SQL it will be queried like this: SELECT gst_amount FROM australian_gst WHERE price=100;
.
Robust abstraction: Intensionally defined relations protect the relational programmer from needing to master Logic Programming, Constraint Programming, Search, Numerical Methods, Linear Programming, Symbolic Computation, and manage multiple semantics, termination, and negation, closed and open worlds, etc.
Ready for query optimisation: Existing query optimisers for extensional and derived relations can be broadened to cover querying intensionally defined relations, leading to efficiency gains over time.
Intimate connection between the constraints in the relation's intensional definition and the WHERE
clause in a query over the relation: A key implication of the above definition is that the relational algebra SELECT
or ฯ
operator (WHERE
clause in SQL) contains constraints that may be pushed down into the definition of the relation prior to retrieving the rows in the relation, rather than being applied as a filter after retrieving the rows from the relation.
Single source of truth: The relational algebra is inherently agnostic to which attributes are known and used to constrain the relation and which attributes are unknown and which are sought as the answer. An intensionally defined relation may be used to query rules "forward" or in "reverse" depending on what is known prior to querying. Following HHT, the extent to which a relation is omnidirectional is called its 'effectiveness'.
Write once, use anywhere and Privacy friendly: Rules and data are kept in separate relations. Rules may be applied, when appropriate, to the right data by a variant of the relational join
โจ
creating a derived relation which is then available for further processing.
Better together: The natural join
โจ
of two intensionally defined relations with common attributes has a stronger predicate over its attributes than the two relations taken separately.
Technology agnostic: While it is convenient to use MiniZinc to define a relation's intension, it is not required. Any language, or system, that supports the above definitions may be used. As to the relational query language, it is convenient to use SQL, but the same queries could easily also be formulated in Datalog or other relational query language.
The Jetisu toolkit has been helped along by inspiration from