XST: Some Thoughts on Extended Set Theory

Database Apps, Spikes, Frameworks

I was working with a client last week where we were building a “simple” data entry app that is part of a very large database-based application. We were doing an Architectural Spike, using XP style development to implement the first story in a week. We were quite successful, and I’m thinking of suggesting to my client teams that we always start that way. The spike let us focus on doing XP-style things such as TDD, with a very simple design, and yet we were able to get everything hooked up and working. We had pretty clean code by the end of the week, and the team was able to begin to see how simple design plus refactoring can lead to a very sensible and practical design.

One of the team members, Reza, had put together a very neat framework in anticipation that it might be useful. Though this is anathema to my preferred style of XP for building applications, it was a cool idea that was easy to get excited about. It used C# Attributes to make field declarations inside objects. The framework used reflection on the class to figure out what the fields of the object were, and to produce XML versions of the object, to build SQL statements loading and storing the objects, and the like. We interfaced the framework into our code, refactored it to be more pretty, and left things in a place where the framework will be a useful part of the overall design of the system.

All that got me thinking about the strengths of a framework of some kind knowing things about data-bearing objects, and the possibility that we could build collections of objects, search them, store them, get them back, and the like, not using an object-relational model but instead using something that might turn out to be more smooth.

When we use an ORM, it’s not easy to work just with the objects and collections of them. In addition, if we have a collection of, say, People, it’s not easy to implement general searching operations on that collection, at least in a language like C#. (Rumor has it that help is on the way in some future version of .NET. I should live so long.) So my mind has been mulling the awkwardness of the ORM approach, the elegance of Reza’s basic idea of declaring the fields of an object, and a topic from my distant past, Extended Set Theory.

The mathematics of Extended Set Theory (XST) was discovered by David L Childs, then at the University of Michigan. It is a very formal approach to the design, development, and deployment of operation-centric system architectures, including database, and it is also very practical. Dave himself has used the theory and his programming of it to outperform Oracle servers, on a very large query, on his laptop! I’ve known Dave for years, and have learned a bit about his ideas. Based on what we learned, a team of mine at Comshare built a relational database system that was a marvel of generality and capability. That product is now pretty well buried, though there are a few people around with versions running at home. I got involved in another company that was doing XST, where we did some really good work that came to nothing. And then a pal of mine, Lee Johnson, joined me in building a little PC library based on XST.

It’s a marvelous and interesting technology which has not as yet found the home it really deserves, though there are various successful applications of it around. Every now and again I think about it and about using it, and this is one of those times.

Toward a Product Vision

In this article, I’ll describe a bit about XST. I’ll have to get a little mathematical but will try not to overstress your mind, or, more importantly, my own. I’ll try to keep focused on the things that XST can do that are interesting, and ultimately, to begin to sketch a vision for a product or products based on XST.

Think of this as early work on an XP product that we might want to build. We’re kicking around some math and technical ideas, trying to see whether there is a product of some kind to build. We are thinking of a technical product, most likely, like a library of handy objects, or a new kind of data store.

XP is usually described in terms of products or projects that are more specific, aimed at users with some business need. People often ask how one might build a framework using XP, and the usual answer is that we’d build the real application and then extract a framework from it. That’s a very good answer in my opinion, especially if your business people are interested in the application and not in selling a framework. Here, though, we’re going to look at whether there is a technical product that we could make available to the world of programmers. I have no idea what will happen, but I’m pretty sure we’ll get in some trouble and learn something.

Simple Tables

Imagine a relational table like this:

In Extended Set Theory (XST), the first row of that table might be represented this way: R1 = { Jeffries^LastName, Ron^FirstName }. Roughly, that means that the record is a set, with two elements, “Jeffries” and “Ron”, and the Jeffries element is named “LastName” and the Ron element is named “FirstName”. Regarding that record, we would like to say that the LastName element of the set is Jeffries and the FirstName element is Ron. We would usually prefer to use the “epsilon” or “element” symbol for this, but in text, for this article I’ll express those notions this way: Jeffries elt_LastName R1 Ron elt_FirstName R1.

We might also write, in flat text: Jeffries elt-LastName R1 Ron elt-FirstName R1.

These can be read aloud as you wish, perhaps as “Jeffries is the LastName element of R1”, or “Jeffries element-LastName R1”, or whatever strikes your fancy. It is possible to be much more formal about these notions, but my purpose here is to get some starting ideas across and see where they take us.

In classical set theory, the fundamental operation is “element”, which is a predicate answering whether some item x is an element of some set X. In XST, the fundamental operation is extended to take a “range” value (e.g. Jeffries) and a “domain” value (e.g. LastName). The formal reasons behind this have to do with the fact that in classical set theory, ordered pairs are represented using nesting of sets. You may have been spared the Kuratowski definition: <a, b> ::= { {a}, {a, b}}.

Suffice it to say, that’s the way ordered sets are defined in classical set theory, and the result of that is that it’s hard to say things about ordered sets, and ordinary sets, all in the same sentence. Extended Set Theory re-axiomatizes set theory to avoid this difficulty. Fortunately, we won’t have to worry about that, but what’s important is that this makes ordered information like records, much more mathematically tractable. For our purposes, we’re hoping that it will make for an interesting set of programming options, down the road in this paper and subsequent ones.

In memory or on the disk, our table and record above need to be represented as something like an array of characters. We might imagine that the “real” definition of the table was something like this:

(That was bloody hard to type in. I’m going to try never to have to do it again, so keep in mind the notion that sometimes, on disk or in memory, a set of records might be represented by a neat rectangular array of characters.)

Set Operations

As with classical set theory, XST has some set operations. Because XST is intended to be much more rich – rich enough to express all of relational database and more – there are many such operators. We’ll introduce as few as possible here. One important one is called “Restrict”. Given two sets, Restrict returns a new set with records from the first set which match the second set. Restrict, in turn, is defined in terms of another operator, “Intersect” or “Intersection”. The intersection of two sets is just the elements that are common to each. Because XST considers both domain and range, the elements must match in both.

That’s read as “the set of all a such there exists an x such that a is element-x of set A and also element-x of set B”. For example:

{ a^x, b^y } intersect { a^x, b^z } = { a^x }

Stick with me here, this gets just a bit more weird and then we can get back to things that are easier to understand. Restrict is defined as

In words, the restriction of two sets is all the records of the first set that match any record from the second set, where by match we mean that all the elements of the second record are in the first. All that comes down is that Restrict does something that makes sense in terms of searching. Back to our name table above, call it R:

Given this table S:

The restriction of R by S is

Cool. However, XST can do something that relational cannot. Imagine that in the table below, the missing items are not just blank, but literally missing. Let S be this:

As a set, this is { { Anderson^LastName }, { Chet^FirstName } }

The restriction of the original name table with that is:

The selecting records don’t have to all look alike: they just have to match!! But wait, there’s more. Imagine that the name table is represented in that flat 0 1 2 way shown above, and that we restrict it with the set:

{ { e¹ } }. That’s an e in position 1. The result is:

… because both “Jeffries” and “Hendrickson” have an “e” in position 1.

The idea to hold on to here is that XST refers to both the values in a record (be they bytes or atomic values like strings or integers), and to the names of those things. Those names are just names for an abstract notion of “position”, and they can be integers representing physical positions, or integers representing some abstract position, or even other atoms like strings such as “LastName”.

Because the XST operations are formally defined, they can be used at any level we wish. We can refer to the abstract fields and field names of a set of records, as does relational theory. But we can also use the same notions to refer to the bytes in a set, which relational theory cannot. We can even refer to sets with “holes” in them, or to even more complex nested structures. We won’t go there today. Instead, let’s turn to some ideas about how XST might help us in our programming.

Product Idea: Searching

Let’s kick around some things an XST product might do. Try to hang with me: this is just blue sky. In a typical database application, we might have an object in our OO code that represents a record in the database. That object might have little more than some field definitions, or it might be more complex. We’ll see. For now, let’s suppose it’s flat.

Now the database itself is a collection of the relational form of these records. We can ask the database to do a selection, such as “SELECT * WHERE Name = ‘Jeffries’”, and with only a whole xxxxload of auxiliary code, wind up with a collection of something more or less like records. But given that collection as a collection in Java or C#, it’s hard to do additional selections or similar manipulations. We basically have to write things out longhand.

We might like to say myCollection.Select(LastName == “Jeffries”), but you might as well forget that. Anonymous methods and delegates later, we’ve got a really ugly blob of code that no one would write. Much more likely we’ll do something like this:

    ArrayList list = new ArrayList();
    foreach (Person p in myCollection) {
      if (p.LastName == "Jeffries")
        list.Add(p);
    }

Ugly. Violates the Law of Demeter. Multiple lines for one idea. Gack.

Now imagine that there was a kind of collection, XST, that understood domains and ranges (field names and field values). And suppose we could create an instance of one of those this way:

XST.SingleRecord("LastName", "Jeffries");

Then given an XST collection people:

list = people.Restrict(XST.SingleRecord("LastName", "Jeffries"));

turns out to be just what we want. Still not exactly lovely, but it’s all nicely encapsulated.

In fact, while one kind of XST collection might be nothing more than a smart ArrayList, another kind might be a flat table of bytes in memory, like the 0,1,2 table shown above. Still another kind of XST might be a wrapper for a relational dataset stored in a database. The implementation of Restrict for the first case would be fairly direct: is there an element “Jeffries” with name “LastName”.

But the implementation of Restrict for the flat table would turn into a restrict against { J⁰, e¹, f²…, s⁷ }, and could turn into a very fast byte scan or maybe even a regex.

And the implementation of Restrict against the relational table could emit SQL in a pretty obvious way.

We might be able to provide a reasonable way to represent data set manipulations like searching, using a single convenient notation, and to completely hide the physical implementation of the data. We could use collections of objects, flat memory tables, flat files, and database tables, all interchangeably.

There’s even the possibility that optimizations could be carried out inside the XST instances. For example. Suppose we have a large ArrayList inside our people object. We get a query for LastName. We could just sequentially search, and that might be OK. But based on the size of the data, and the kind of query made, we might build an auxiliary data structure inside the XST object. We might build a hash table by LastName. Or, if our flat table manipulations were screamingly fast (and they can be), we might convert the whole set to a flat table once, so that subsequent searches would be fast.

Rather than make optimization decisions in our application code, we could make them inside the XST library. Using Attributes like those in Reza’s example, we could arrange that different classes use different strategies. We could even make those attributes dynamic, so that we could send a message to a collection telling it what kind of operations to expect and how to arrange itself.

Thoughts on Implementation

Much of the joy with this idea comes from the ability to process large numbers of records very quickly, using byte operations. The idea is to map a logical operation down to a physical operation, or a series of operations, that run very quickly. Let’s look at our restrict.

Given our name set, call it R:

And a restricting set, call it S:

We can map those into simple binary arrays, as shown before above and repeated here for R:

And like this for S:

Now let’s imagine that we have tables rtable, stable, and ttable, with sizes rsize, and ssize and record lengths rlen and slen. We can implement restrict with approximately the following loop in C-like code:

    tbyte = 0;
    for ( rbyte = 0; rbyte < rsize; rbyte+=rlen)
      for (sbyte = 0; sbyte < ssize; sbyte+=slen)
        if (memcmp(rtable+rbyte, stable+sbyte, rlen) == 0) {
          memcpy(rtable+rbyte, ttable+tbyte, rlen);
          tbyte+=rlen;
        }

I happen to know from experience that this code will fly if we implement it over big buffer-loads of file-based bytes, compared to running an equivalent SQL query. And it will very likely run substantially faster than a search in memory over an ArrayList or Array of records, asking each one to render up its LastName field.

However, today’s languages like C# and Java are rather far abstracted away from the bytes, and it may be difficult to get things whipped in and out of byte arrays. I just don’t know – I haven’t done that kind of thing in those languages. So I’m asking for help: see the end of the article.

Enough for Now

We’re just kicking around a technical thing we know a bit about, with an eye to whether there is some interesting software to build around it. Initial indications offer some possibilities that could be exciting:

• Better searching of collections than now exists;
• More uniform access to collections, files, and database;
• Possible high performance with behind-the-scenes optimization.

There are issues to consider, especially if we’re really thinking about a product and not just an exercise:

• Hard to compete with existing relational products. (But look at Hibernate and SimpleORM.)
• Initial syntax isn't entirely tasty.
• If it gets too mathematical, no one will understand it.
• No evidence that it is implementable.
• Might be inefficient despite all I say about optimizing.

I remain interested in this, and might undertake some technical experiments – Architectural Spikes – to get a sense of what might be possible.

However, at this writing, I don’t know whether it’s worth pushing forward technically, because I’m not familiar enough with the parts of C# and Java that get that close to the metal. Who knows, maybe it would go better in Ruby? Advice from you, Constant Reader, will be valuable. If you have ideas or interest, please email me at the usual addresses and be sure to have [ron] as part of the subject line.