EXPLAIN EXTENDED

This year, I'll be implementing a Lisp interpreter in SQL.

Now, what's Lisp, and why would I want to do that? Well, let me tell you a little story about that.

Several decades ago, I got a New Year's present from my roommate's girlfriend. It was a book. She got it at a used bookstore in the UK. She wasn't sure what to get me, so she turned for advice to the store clerk. He asked her what kind of person I was, and she aptly described me as "a guy who loves math and mutters to himself". The clerk, without batting an eyelash, handed her a book with a yellow bird on its cover and told her I would like it.

He turned out to be right. I did like the book. It was written by Raymond M. Smullyan, and its title was "To Mock a Mockingbird".

By that time, I was already familiar with the author. I had read his books before. They were collections of logic puzzles, set in the now-popular Knights-and-Knaves world of his own invention. "To Mock a Mockingbird", at first glance, was the same. Its first two chapters were collections of logic puzzles as well. The puzzles weren't too easy, nor were they too hard. Each of them would make you flex your brain just the right amount. Back then, I used to commute a lot every day, and these puzzles turned out to be perfect time killers during long commutes. It took me something like two weeks to get through the first two chapters.

The third chapter, as is typical for the genre, started with a preface explaining the setup. Instead of knights and knaves, this chapter had a forest inhabited by magic birds. The birds are programmed to call out each other's names. When, say, a finch hears "parrot", it would (always) respond with "jay". When a parrot would hear "jay", it would say "crane", and so on, and so forth. All the birds have to say something when they hear another bird's name. This chain never stops.

The very first puzzle introduced a couple of conditions (which didn't look like much), and asked to prove some facts about the birds.

At first, I thought it would be the same old, same old. It wasn't. I couldn't solve it. Not in five minutes, not in an hour, not in a day.

I lost sleep for a week.

I had been reading a lot of math puzzle books, so I sort of knew there were math concepts behind the fantasy setup. It was obviously some kind of logic. I was pretty good with regular, first-order logic. It was easy. There's data: numbers and facts. There are functions, or formulas, which operate on the data. The two never mix. You can add two numbers together, or you can combine two theorems to prove a new one. But you can't "subtract" the Pythagorean theorem from the law of the excluded middle, or "multiply" Bézout's lemma by two; it doesn't make sense. You know exactly what's what.

With those damned birds, all the bets were off. If it's logic, are the birds data or functions in that logic? Remember the finch. It hears "parrot", it says "jay". It maps one to the other. When something maps things to things, it's a function, so "parrot" and "jay" must be data. Ok, parrots are data. But at the same time, the parrot maps "jay" to "crane", so the parrot is a function. So now the birds are functions? And the data? Should we put their name in quotes when they're data? Double quotes when they're a function again? It never stops. You think you've put your finger on it, and then it eludes you again.

It wasn't just that I couldn't find the solution; I didn't even know where to start looking. I spent (I believe) two months of my life pondering this problem. And then, in a surge of inspiration, I just saw the solution, clear as day. I still remember where I was at that moment.

The book had promised that the solution would be "extremely ingenious". It was. To this day, the fact that I found it without looking it up fills me with pride. I won't spoil it for you. I'll leave finding the book and going through the same experience as an exercise for the curious reader.

That exact feeling came back to me several times after that.

I had that feeling when I started learning programming and came across the concept of first-class functions. Store functions as if they were data? Call a variable as if it were a function? What a weird idea at first! And what a brilliant one, when you start thinking about it.

I had it again when I came across what turned out to be the theory behind the bird puzzles: the lambda calculus and its evil twin, the combinatory logic. It takes the idea of combining data and functions to the extreme: There's no data at all, only functions. There's no starting point, nor the stopping one; it's the functions all the way down. And yet, if you're clever enough, you can build arithmetic, algebra, and programming languages using only these functions that have no beginning and no end.

And then I had it again, almost as a déjà vu, when I first came across Lisp.
Read the rest of this entry »

From Stack Overflow:

I am trying to insert into the target table values from the source table, but also insert the primary key of the source table into the tracking table.

INSERT
INTO    TRN_TEMP (TRN_TRAN_DATE, TRN_DESCRIPTION, TRN_AMT)
OUTPUT  D.DET_PRIMARY, GETDATE()
INTO    REGISTER (DET_PRIMARY_LINK, INS_DATE)
SELECT  D.DET_DATE, 'SOMETEXT', SUM(D.DET_NET)
FROM    DETAIL D
LEFT JOIN
REGISTER R
ON      R.DET_PRIMARY_LINK = D.DET_PRIMARY
WHERE   R.LINE_ID IS NULL -- TO REMOVE LINES ALREADY PROCESSED
GROUP BY
D.DET_DATE

I can't see a problem with the text above but I get an error:

The multi part identifier 'D.DET_PRIMARY' could not be bound.

I've tried both D.DET_DETAIL and DETAIL.DET_DETAIL and the error is the same.

This is a limitation of SQL Server which can be easily worked around by substituting MERGE instead of INSERT.

Let's create some sample tables and see:

CREATE TABLE
source
(
id INT NOT NULL PRIMARY KEY,
grouper INT NOT NULL,
value INT NOT NULL
)

CREATE TABLE
destination
(
id INT NOT NULL IDENTITY PRIMARY KEY,
grouper INT NOT NULL,
aggregated_value INT NOT NULL
)

CREATE TABLE
register
(
dest_id INT NOT NULL PRIMARY KEY,
max_source_id INT NOT NULL UNIQUE,
grouper INT NOT NULL UNIQUE,
regdate DATE NOT NULL,
)

INSERT
INTO    source
VALUES
(1, 1, 5),
(2, 1, 2),
(3, 2, 6),
(4, 2, 8)

, and run the query:

MERGE
INTO    destination d
USING   (
SELECT  grouper, SUM(value), MAX(id)
FROM    source
WHERE   grouper NOT IN
(
SELECT  grouper
FROM    register
)
GROUP BY
grouper
) s (grouper, aggregated_value, max_source_id)
ON      (1 = 0)
WHEN NOT MATCHED THEN
INSERT  (grouper, aggregated_value)
VALUES  (grouper, aggregated_value)
OUTPUT  INSERTED.id, s.max_source_id, s.grouper, GETDATE()
INTO    register;

SELECT  *
FROM    register;

You can try it yourself on SQL Fiddle.

As you can see, we are using both destination table's INSERTED.id, source table's s.max_source_id, s.grouper and an arbitrary expression GETDATE() in the OUTPUT clause which works just alright.

An alert reader may notice that there is another problem with the original query, but this will be covered in the next post. Watch this space!

It's been a really long year.

The blog has not been updated during this year. I focused on improving my SQL skills and helping other folks to improve theirs.

During this year Explain Extended has become a team. We now do SQL consulting and database development. I'll write a post about it soon, but send me a message if you're impatient to wait.

Now, to the new year post.

New Year has always seemed like the most global thing to me. It does not happen to everyone at once. When I was a kid I wanted to go to space and see the New Year marching through the planet with my own eyes (and it's not that I don't want it anymore).

Now we have satellite images and such, but with a little effort we can see how our planet looks from space using SQL.

To do this, we need some map data, basic math and pretty simple SQL. I'll use PostgreSQL for that.
Read the rest of this entry »