Rain flips its q – a database engine
for simple folk
Motivation
There was a time, long ago and far away, when I used to write proper business applications in APL. I am thinking back to 1983 and my Loughborough paper on databases, which reminded me of just how heavily I depended on a simple, reliable DBM working entirely within the confines of the APL workspace. Subsequently, I had evolved into something of a tool-builder rather than a tool user, and this state persisted until a few weeks ago.
When I had a phone call from a old Rowntree friend (he used to run Assortments in York) for whom I wrote a lot of planning and scheduling applications. He is kinda retired now, and has ended up managing the rebuild of the east end of York Minster ‘in his spare time’. This is a big project (around £21M of lottery funding over 5 years) and has put huge pressure on the Minster Stoneyard to turn out carved blocks to a predictable schedule. Herding cats comes to mind.
So Peter called me, and wondered if I would be interested in reviving some 20-year old skills and cranking out a little scheduler for them, so at least they might know a little way ahead who will be carving which blocks when, and consequently when various bits of the overall project might get completed. Was I interested – of course I was!
Panic then set in fairly quickly, as I realised that an essential chunk of the software I needed was last seen on a VS APL system that was turned off in late 1999. So I looked around my collection of heaps of things and found a flipdb user guide and (of course) a copy of “q for Mortals” which I recently reviewed. Towards the end of this review, I caught myself musing around the possibility of implementing something comparable in APL. After all, kdb was originally just a bunch of q and Paul had gone down a very parallel road with flipdb. Time to give it a go, thought Adrian.
A database architecture for APL
Firstly, this has to be designed to make the raw data available to your
application in the simplest way imaginable. You must not have to run
a query (or call a server) just to get some numbers back. In the old days I
just used variables in the workspace, with a ‘master variable’ called
(say) ⍙emp which was just a namelist of other variables
like ∆name, ∆sal and so on. A few simple utilities implemented
operations like take and compress on the table as a whole. The description
variable developed a few whistles and bells, the main one being support for
foreign keys (when the emp table has a pointer to a dept table) which were
implemented as simple (zero-tolerant) 1-origin indexer variables. So when
you deleted a department, it knew to fix up the indices in any other tables
which referenced it (or yell at you if the deletion was not acceptable).
Let’s slide forward from the VS APL timeframe where this was all written, to the 21st century and Dyalog APL. Namespaces could be very handy here, and maybe those foreign keys could just be refs? If we start with the basic notion that a table maps to a namespace with some variables in it, then we pass the first hurdle of data-accessibility. What could be easier than:
emp.sal
12340 2345 2345 1200 1234 0 1234
+/emp.sal
20698
Rather than using prefixed names in the old-fashioned way, we just prefix with the namespace. This makes it pretty trivial to code up (for example)
8 db.take emp
emp.sal
12340 2345 2345 1200 1234 0 1234 0
∇ {tbl}←len take tbl;nl2
[1] ⍝ Normal APL take/overtake for all vars in namespace <tbl>
[2] nl2←tbl.⎕NL ¯2
[3] :With tbl
[4] ⍎¯2↓∊(⊂'↑⍨←len ⋄ '),⍨¨nl2
[5] :End
∇
Of course you need to be sure that the only variables you leave lying around
are valid to be taken/compressed by the same expression. Anything else we
want to store about the data is going to be tucked away in a sub-namespace.
Alert readers should have spotted the flaw in the above function. I should
really have formatted the length and used dyadic execute rather than :with
here. One day I’ll have a variable called len in a table, and it will all
go horribly wrong.
Anyway, moving quickly on, if we could throw some descriptive stuff into a sub-namespace, that would help with the formatting of the output, and also give me somewhere to record those pesky relationships.
db.Columns emp
Varname Key Type Format References Shape
------- --- ---- ------ ---------- -----
#.emp.id ⍝ * num 8
#.emp.name ⍝ text 8
#.emp.dept ⍝ ptr #.dept 8
#.emp.sal ⍝ num £##,##0.00 8
#.emp.bonus ⍝ num 8
#.emp.band ⍝ num 00 8
#.emp.sex ⍝ ptr #.sex 8
The references really are refs here, everything else in the description
namespace is just text, so is pretty trivial to edit. There are a few handy
utilities called db.CreateTable and db.CreateColumn which help you to get things in the right
order. So far so good. If I re-order the dept table it can check for any
refs to itself and go fix up the corresponding pointers (fortunately most
primitives like iota and membership work fine on refs now) so we are still
quite low on rocket science. Just formatting the content and throwing it
into the session is very easy now:
db.Show emp
id name dept* sal bonus band sex*
---- ---- ---- ---------- ----- ---- ---
5728 │ William 451 £12,340.00 100 01 Male
1234 │ Gill 777 £2,345.00 100 03 Female
1238 │ Richard 451 £2,345.00 400 02 Male
1240 │ Tim 822 £1,200.00 100 02 Male
1241 │ Beryl 451 £1,234.00 0 01 Female
1242 │ Hello there 822 £0.00 0 01 Male
1243 │ Farewell 451 £1,234.00 321 02 Never
0 │ 0 £0.00 0 00
Better get rid of that dodgy extra row (the overtake a few lines back) but at least you can see what it did.
How hard can it be
To write a db.Select utility that takes a table and some expressions, and throws
you back what is effectively another table
db.Select emp ('' 'sal>1000')
#.db.sel
Well, it returned a ref all right, can we see the content with the same kit we used to see the original table?
db.Show qq←db.Select emp ('' 'sal>1000')
id name dept* sal bonus band sex*
---- ---- ---- ---------- ----- ---- ---
5728 │ William 451 £12,340.00 100 01 Male
1234 │ Gill 777 £2,345.00 100 03 Female
1238 │ Richard 451 £2,345.00 400 02 Male
1240 │ Tim 822 £1,200.00 100 02 Male
1241 │ Beryl 451 £1,234.00 0 01 Female
1243 │ Farewell 451 £1,234.00 321 02 Never
More to the point, can we run a further query on the result of this one?
qqq←db.Select qq ('name,sal,bonus,both←sal+bonus' 'bonus>100')
db.Show qqq
name sal bonus both
---- --------- ----- ----
Richard £2,345.00 400 2745
Farewell £1,234.00 321 1555
This is the property of closure that the database gurus insist is so important. It allows you to write a proper relational algebra, with functions like set-union and set-difference that act on tables and return tables. It is one of the great strengths of q and is something we should constantly keep in mind. Of course we can still get at the raw data very easily:
qqq.(name both)
Richard Farewell 2745 1555
The only magic here is the magic that comes with your interpreter. Honest!
More interesting queries
Hands up everyone who hates writing joins in SQL. Both Arthur and Paul (independently, I think) had the brilliant idea of using the dot-notation to allow a query to ‘look down the link’ in a very intuitive way. An example will make this clear:
sel←db.Show∘db.Select
sel emp ('name,dname←dept.name,mgr←dept.mgr.name' 'bonus<100')
name dname mgr
---- ----- ---
Beryl Main office
Hello there Dogsbodies Gill
The dot is appropriate for many-to-one relationships, and of course you can chain them to follow the links to the end of the earth (and back again, as in the example above). Just try asking Oracle to list all employees who earn more than their manager, and you will rapidly appreciate the power of this simple extension. Incidentally variables get ‘sensible’ new names if you leave them to default, but giving them names explicitly generally makes sense.
Paul takes this a step further by allowing us to look through the wrong end of the telescope and see the many from the one, like this:
sel dept 'id,name,emp[dept].bonus'
id name bonus
--- ---- -----
451 │ Main office [100 400 0 321]
977 │ Real workers are here again []
822 │ Dogsbodies [100 0]
777 │ The End [100]
Which illustrates another great thing about q (and flipdb, of course) which is that you are allowed to group things without applying a reduction. Of course you can reduce the groups if you want to:
sel dept 'id,name,max emp[dept].sal'
id name sal
--- ---- -------------------
451 │ Main office 12340
977 │ Real workers are here again ¯1.797693135E308
822 │ Dogsbodies 1200
777 │ The End 2345
… but be aware that this is APL and that reductions on empty arrays don’t always do what you expect! I need to have a proper think about missing-value support before I fix this one.
Grouping is something we need to do all the time, so it makes sense to accommodate it in the normal query syntax. Along comes another optional argument (sorry Arthur, I put these in a different order) to the selection to give us the new keys for the output table:
sel emp ('count,sum sal,avg sal+bonus' '' 'dept.name')
name count sum sal avg col4
---- ----- ------- --------
Main office │ 4 17153 4493.5
The End │ 1 2345 2445
Dogsbodies │ 2 1200 650
Note that the grouper(s) are marked as keys (as they are always unique combinations) and the output is once again a table that we can do further processing with, or just treat as a handy repository for some working data. If we group on two columns:
sel emp ('count,sum sal,avg sal+bonus' '' 'dept.name,band')
name band count sum sal avg col5
---- ---- ----- ------- --------
Main office 01 │ 2 13574 6837
The End 03 │ 1 2345 2445
Main office 02 │ 2 3579 2150
Dogsbodies 02 │ 1 1200 1300
Dogsbodies 01 │ 1 0 0
Then we get two keys (duh!) and something stirs deep in Adrian’s subconscious. Maybe we could use these as the row/column indices into a crosstab, like this:
xtab←db.XTab∘db.Select
xtab emp ('sum sal' '' 'dept.name,band')
name 01 03 02
---- ------- ------- -------
Main office │ 13574 3579
The End │ 2345
Dogsbodies │ 0 1200
As of today, this is just a fancy way of displaying a table with two keys, but a sense that it should become another first-class object, related to a table, but not quite the same. Perhaps a brick or a box would be good names for it. Cube has already been done to death, I think! The bit in the middle looks awfully like a matrix.
A quick look beneath the surface
There is really only one important idea behind this. Having checked out the
tokens in each expression, the Select function runs the expressions in the
table (so they can see all the variables) but with the path set to look for
the utility namespace which lives inside #.db. This allows you to write any
APL you like in the query, or make use of some simple canned functions if
you can’t be bothered to re-invent average every time you want it.
Here are the 6 wettest days we have had, in date order:
sel rain ('' '{⍵>¯6+⌈/⍵}⍋⍋rain')
date rain mintemp maxtemp
---- ---- ------- -------
25/10/92 │ 38.9 ¯2 6
08/06/99 │ 38.1 6 11
02/08/02 │ 49.3 15 20
10/08/04 │ 55.4 18 21
15/06/07 │ 53.4 10 12
25/06/07 │ 38.1 12 18
… and here is what our avg function does:
avg←{1{(+/⍵)÷↑⍴,⍵}godeep ⍵}
godeep←{
(1+⍺)>|≡⍵:⍺⍺ ⍵
⍺ ∇¨⍵
}
… with much the same stuff for all the standard summary functions. I am sure 10 mins of Alan Sykes’ time will add lots more, like variance, median and all those other ones that standard databases never have when you want them.
With one mighty bound
We have a functional query engine, we have an APL session. Perhaps we should put them together to make one of those little languages that we all remember from the 1970s. Remember where we came in? Well, Stones have Types and Types have estimated days, so wouldn’t it be great if we could type:
xtab count,ManDays←sum Type.Mason+Type.Carve
from ym.Stone
by Type.Id,Level.Name
where Level.Id in 'B,C'
asc Type.Id
Id Level B Level C
-- count ManDays count ManDays
Arcading │ 1 25
Arcading/string │ 3 45
Ashlar │ 4 4 3 3
Grotesque │ 2 80 2 80
Niche head │ 4 180
Niche head course 2 │ 2 48 5 120
Shaft moulding │ 31 248 44 352
Shaft stooling │ 2 20
String/pedestal │ 3 60
… to get an overview of how much work is left. Perhaps some of you are old enough to remember those special daisy-wheels that allowed you to plot to some small fraction of a character? Well, with Unicode we have some 1/8th blocks, so it’s back to the future again:
select ManDays←sum Type.Mason+Type.Carve '⎕24 ###9'
from ym.Stone by Type.Id asc Type.Id where Type>0
Id ManDays
-- -----------------------------
Arcading │ ▌ 25
Arcading/string │ █ 45
Ashlar │ ▎ 12
Ashlar return │ ▎ 12
Carved pedestal │ █▎ 60
Grotesque │ ███▍ 160
Niche head │ ██████▋ 315
Niche head course 2 │ ████▌ 216
Shaft moulding │ ████████████████████████ 1144
Shaft stooling │ ▍ 20
String │ ▍ 20
String/grotesque │ █▋ 80
String/pedestal │ █▎ 60
String/shaft stooling │ ▌ 25
There is a font update on your keydrive if you don’t see all the blocks
correctly! The workspace is called iqx, it is definitely work in progress,
and there are plenty more examples. You won’t see the stone data (for
obvious privacy reasons) but there is 15 years of rainfall to play with, as
well as the infamous “Suppliers and Parts” data that everyone uses these
days. Of course what would be really nice would be:
select photo from ym.Stone where Id=467
… but that one will have to await the next update to the Dyalog session!
Roundup
This is first and foremost a programmer’s toolkit, and I would expect to use
the functional form of db.Select nearly all the time. The stuff with queries and
the session I see mostly as a handy debugging tool, but you never know. That
is really how q got started, and look what happened to it. The
session is a much under-appreciated resource, so exploiting it in this
simple way was good fun, and may develop into something useful. Let me know.