|Don't ask to ask, just ask|
SQL Crosstab, a hell of a DBI idiomby gmax (Abbot)
|on Dec 11, 2003 at 00:34 UTC||Need Help??|
A few months ago, dws, against the popular opinion promoting SQL statements builders, stated that hardcoded SQL is better and somethimes quicker to obtain. I heartily agree on his position, since I usually do the same thing, never trusting a tool to create SQL code for production purposes. However, there is an exception to this rule, and I rely on a special tool to produce complex queries for cross-tabulation. Since I am the author of such a tool, I am less suspicious towards its evil side effects on the rest of my applications.
Until a few months ago, the tool we are talking about was just a ugly perl script with a few dozen variables, which I used to create these exceedingly long queries that I then pasted to the production code. That was not a satisfactory solution, though, and when the requirements for truly dynamic queries became unavoidable, I created DBIx::SQLCrosstab, allowing the execution of dynamically created crosstab queries.
For those of you not familiar with the concept, let me remind that crosstab queries are quite peculiar, often involving hundreds of SQL lines, unlikely to be handled by simple DBI wrappers. A recent article explains in full detail the database theory behind the creation of crosstab queries and gives some tips on how to use DBIx::SQLCrosstab to its best.
What the article doesn't cover is most of the "under-the-hood" stuff, the juicy details of how the engine works and how to expand it. Since OnLamp editors wanted to keep the article focused on database matters, I stashed away all the Perl relevant issues for PerlMonks, and here it comes ...
One of the most intriguing aspects of DBIx::SQLCrosstab is the SQL builder engine, which, in addition to producing valid SQL code, must be also able to cope with a long list of requirements.
To create a realistic multi-level crosstab query, you must:
a simple, brute-force engine
To appreciate the complexity of the requirements, let's build a simpler engine that can only deal with a few rules, creating a query from simple requirements. The following example will create a query from a list of values and the corresponding field names, and some information on the operation to perform.
This script shows only the SQL builder part. The preparatory part would require a few additional queries, one for each level of header, to get the values from the appropriate database tables. Something along the lines of:
The heart of the engine is in those two joins, the first of which creates a composite condition. Each item is a combination "field name + value". Several items are joined by a "AND" operator. The resulting operation is included inside a "CASE" function (SQL ANSI 92), which passes to the "SUM" function either the relevant field or a NULL.
The second join creates the column name for the result set. What is missing in this crude version is a check on the applicability of the character used here as a field separator. Also, some database engines have limitations on the column name, which has a maximum length and some restriction on the characters to use in it. The real module has a default mechanism to use fake names (fld001, fld002, and so on) and a support hash to keep track of the real names. This trick makes the query more acceptable to fragile DBMS parsers.
The resulting query follows. Don't be afraid. It isn't the shortest you can get, but it's far from being the longest one. Crosstab queries with the tiny sample database that ships with the module (9 records) can be up to 600 lines long.
Trees and combinations
The simple example in the previous section can solve many cases. But if we expand the requirements as to include column sub-totals, that simple paradigm can't carry out the task successfully. We need to either modify the engine to take sub totals into account or modify the permutation algorithm to produce the sub totals combinations in the same data structure used for the normal processing.
I chose the second solution, and I implemented a second permutation function that produces a modified @permuted array.
There were several choices to create this modified array. Although I got some clever tips on how to make this function, in the end I decided to implement it with a Tree::DAG_Node, mostly because I would need this module to process the cross tabulation output.
When passed to the same engine, this data structure produces a query with a sub total for each level of headers.
A (brief) digression about database algorithms
A more difficult case is when a level depends on the previous one, such as "countries / towns" or "University faculties / subjects". If I were processing such columns with the same algorithm used so far, I would end up with things like "Mathematics / Greek Philosophy", "Languages / calculus", or "History / operating systems."
The difficult thing about database programming is that an algorithm can involve steps in the client interspersed with steps in the server.
If you are used to designing algorithms on the client side, dealing with this mixed nature can be frustrating, since you could try to solve on the client side what you should do on the server side. On the other hand, if you are familiar with database solutions, you could be tempted to do on the server side simple operations that should be treated in the client.
When you reach the right balance, you can create sensible algorithms. Trouble is, sometimes you become too much confident in what you've done, especially if you have just created a good, clever-looking, and efficient paradigm. When this happens, it is harder for you to find a fault in your work, and when you find it, your mind is clouded by your previous success, thus making it more difficult to find a solution for your latest problem.
In my case, when I found out that my algorithm did not cover this particular aspect, I spent some time fantasizing about very complicated variations of what I had already done, with intermediate data structures and acrobatic manipulations of the latter. Then I decided that I was doing something wrong, and I left the matter rest for a while. Finally, the clear solution came to me, i.e. whenever there is a case of dependency among levels, then I let the database engine find the legal permutations. Just querying for the DISTINCT values of all the involved columns will return all the valid permutations. So I added this variation as an option and now the module seems to cover every angle of the matter.
Expanding the engine
Creating the query was only half of the problem. Returning the data in a format suitable for human consumption is a strictly related issue, and I designed the module to facilitate this important part.
The format issue is not addressed directly by DBIx::SQLCrosstab. To keep the contents separated from their appearance, I created a descendant of the first module, DBIx::SQLCrosstab::Format, which can do everything its parent can do, and can also create some good-looking reports, like the one shown here.
This table was created by the as_html method, with the help of a few data structures that I designed to deal with general purpose tree-like reports, like this peculiar HTML table or a rich XML document.
Data structures for format depicting
The above table was created using these two data structures, each one describing a tree-like header, one at the top of the table and one at its left.
The first one, $header_formats, is a description of the headers at the top. Each element in this array reference describes one line of headers as an array of hashes. For example, the first line says that 'Area' will occupy one column, but it will span down three rows. Armed with this information, it is very easy to build a HTML table header.
The second data structure, $recs_formats, describes the row headers in a different way. It is a hash, whose values are hashes of arrays. The keys for the hash are the level, i.e. the column number. The inner hash keys are the same values that will show up in the data.
This structure is supposed to be used in a destructive way:
Reading the records, at column  I get the value "N". I check if there is a "N" key in the hashref under "0". If I find it and the value is defined, then I get the first available item from the arrayref. Something along the lines of:
The real code is a tad more complex than this, but just to give you the idea.
Descending from Trees
These structures didn't come from the sky, but were created from two trees that can both produce simpler structures or be the basis for some demanding reports. For example, the XML output was generated directly from the co-operation between these two trees.
You can see how these trees are related with the simpler data structures shown before. Generating a array of hashes is a straightforward exploit of tree traversal functions. Using a post-order traversal you get the column span values, and with a pre-order traversal you push the data into the array of hashes. A similar treatment is due for the record descriptor.
The same features are useful to create a XML document. A pre-order traversal will create the opening tags, while a post-order traversal will create the closing tags. This approach, rather than using XML::Simple, was preferred because this special structure can also add information about the data before the DBMS processing. The data set reports 'pers' and 'f', but the module internal memory knows that 'pers' is a 'department' and 'f' is a 'gender'. The resulting XML is enriched by this knowledge which would be lost in a simple conversion.
Where does all this talk lead?
The module is designed for expansion, and you could expand it to suit your needs if it doesn't do it now. You could create a new format or adapt existing formats to accept cross tabulations. You could integrate crosstabs into graphical interfaces, statistical packages, decision making applications, or whichever fancies you today.
It is not that hard. The above structures would be easily available to a descendant of DBIx::SQLCrosstab::Format. Your descending object should be used as the ones in the official examples until you get the records. After that, the private method _find_headers() will create the data structures described in this node. From that point on, it's all yours.
Thanks to tye, who adjusted PM allowed tags and made the formatting of this node much easier.
_ _ _ _ (_|| | |(_|>< _|