Keeping Denormalized Values Correct

A normalized database stores each fact in exactly one place. This makes for very robust write operations, it is much easier to get things right on the way in. But it becomes much harder to get things out efficiently or easily, so very often we denormalize, that is, we store facts in more than one place for easier retrieval. This requires a very well thought out strategy to make sure these repeated values are always correct.

There are links to related essays on normalization and denormalization at the bottom of this post.

This blog has two tables of contents, the Topical Table of Contents and the list of Database Skills.

Review of Methods

For our example this week we will consider a shopping cart. The orders are kept in the ORDERS table and the items purchased are in the ORDER_LINES table. We have denormalized the database by keeping the value ORDER_TOTAL in the ORDERS table. Every time a line item is changed, the ORDER_TOTAL must be updated.

There are a handful of methods that are popular in the wild for doing this. Some practices emphasize programmer discipline, others seek to prevent actions that will lead to inccorrect values. Strategies also fall into application level or database level, while still others operate at the architecture level.

Personally I chose triggers about four years ago, which I will explain at the end of this essay.

The Weakest Approach: Discipline

The simplest approach is to require that programmers be made aware of all denormalized values and that they must remember if they modify a line item to update the ORDER_TOTAL. This works well enough actually for small programming teams, where there is only one or maybe two programmers, preferably sitting right next to other. Mind-reading helps here as well.

Of course this approach falls apart like a rotten burlap bag as soon as the team or the program exceeds the ability of the team to keep it all straight in their heads.

But I did not bring up this example just to ridicule it. I have found that even seasoned veteran programmers (including your humble author) will fall into the trap of trying to enforce conventions at many levels in their programming. To see why this is always a bad idea and should always be avoided, consider this hypothetical case.

Imagine a new programming language is introduced known as Super-G, which is fashionable and wonderful and everybody loves it. It has a well-thought out typing system except for one odd behavior: If you code a line that concatenates a string with a date, program execution ends with no error. The compiler does not trap for this and run-time does not tell you why it quits. You can Google for it and find out that everybody knows about it, and you just have to remember not to do that! The language's authors have no plans to fix it because nothing is wrong. The fully expec you to always remember never to concatenate strings and dates.

The example is meant to be absurd, but to reinforce that any strategy where you just have to remember is out of the running from the start. Since we would not accept this in any tool we use, we should certainly never build our own practices upon such sand, and certainly we would not count on it to keep denormalized values correct.

Limiting Access To The Database

The next simplest strategy is to prune down what agents (programs or users) can get at the database. The idea is simple: just let one program get at the database, make sure that program is correct, and force everybody to go through the application.

This will work if you can get your programs right and there is no chance that any of the check-signers will demand access except through your application. Many programmers believe this is true for them. Some of them are right, but many are not: their users would love to get access to the database but the programmer has created a situation where it is impossible.

Personally I try to avoid this approach completely, and my reasons are both philosophical and technical.

On the technical side, successful programs always expand in scope, and the demand for flexible database access always increases. Limiting access to the database means that eventually you have to recode the entire database interface. This means work for you, cost to the customer, and work for the customer in plugging into whatever interface you create. This may be doable, but the overriding fact is that databases already have an interface, and any time spent re-inventing it could better be spent on just about anything.

On the philosophical side I simply do not like any architecture where limitations are built in from the start. Call it a personal prejudice, but I much prefer to find the flexible solution where there is one (and personally I love to find it where it appears it does not exist). Overall the flexible solution always leads to more possibilities for work, more features, and just plain more fun.

Application Framework Strategies

If you are committed mainting the ORDER_TOTAL in application code, and you wish to avoid the "please remember to always...." blunder, then it must not be possible for new programmers or prima donna programmers to violate the requirement. This means your framework cannot allow random SQL commands, and must somehow force all write access to particular tables to route through particular objects or functions. A good ORM system should at very least not only provide a mechanism for updating related tables, but also prevent any access except through that mechanism.

Personally I have no use for these kinds of systems, for reasons explained in the previous section, and so I cannot really comment on them beyond describing these basic minimum requirements.

Server-Side Strategy: Stored Procedure

A few years ago I was working in Manhattan and a fellow programmer explained that at his wife's job all database write access had to go through stored procedures. The idea was to ensure that business rules were always enforced and to prevent any programmer from wittingly or unwittingly violating the rules. In the interest of full disclosure, I'll point out that I have never worked on such a system, and all of my knowledge of such systems is second-hand or third-hand.

With that being said, the obvious up-side to this method is that you avoid forcing database access through your application, making things much more robust and extendable. Further, you make sure, by coding up routines that handle UPDATES and INSERTS to ORDERS and ORDER_LINES that the useful but troubesome ORDER_TOTAL value is always updated when it needs to be. Further still, you can tie security to the stored procedures and control who can modify orders, which is a prime feature mentioned by everybody who has ever explained such a system to me.

There is a significant down-side if you intend to code the stored procedures manually. My own experience is that server-side code is the most difficult to debug (please feel free to post a comment trumpeting your favorite debugger for stored procedures, I'm all ears).

I have never been tempted to use a system like this because I believe it is still exactly one level more complicated than it needs to be. What I really want is to be able to directly code an INESRT to the ORDER_LINES table from any source and know the ORDER_TOTAL field will always be correct. If that were possible, then all parties are liberated from inventing and then using any API except SQL. Now of course many of us prefer to build some layer on top of SQL (myself inclued), but if the architecture supports direct SQL while enforcing business rules then all parties are free to use abstraction layers of their choosing, and nobody is forced to invent or accomodate anything they do not wish to.

Server-Side Stragey: Triggers

It is a simple technical fact that the tightest possible encapsulation of code and data occurs when you attach triggers to tables. In our example of the ORDER_TOTAL value, any INSERT, UPDATE, or DELETE to the ORDER_LINES table would update the ORDER_TOTAL in the ORDERS table. This approach gives maximum flexibility: you can directly access the database without violating rules, and any player can use an abstraction layer of their choice, or none at all.

Since many programmers find it very tedious and error-prone to code and debug server-side routines, this approach still faces a large obstacle if you intend to code the triggers by hand. But this should not be necessary when taking this approach, because all denormalization will follow patterns. This is a theme that I tend to repeat over and over in these essays: your tables will all follow predictable patterns and your denormalizations will likewise follow patterns. Whenever you have patterns you can have automation, and in this case that means generating the triggers instead of coding them by hand.

Another concern with this approach is security. I have been stressing the inevitable need for expanded database access as your application matures, but if you let somebody in with full priveleges, they could accidentally or maliciously cause huge damage if they can run willy-nilly wherever they want in the database. The trigger-based approach is the tightest possible way to enforce business rules, but it does nothing to address security. And if you end up granting database access based on confidence in triggers, then you are forced into enforcing security as well inside of the database -- but that is an essay for another day.

Conclusion

Once we decide to denormalize then we are required to dream up a strategy to keep things correct going in. The weakest strategies depend upon voluntary adherence to some set of conventions, and many strategies accept limitations in overall flexibilty to reduce the threat from unknown elements. The trigger option, not very popular these days, provides the tightest encapsulation of code and data, and lends itself well to code generation.

Related Essays

This blog has two tables of contents, the Topical Table of Contents and the list of Database Skills.

The normalization essays on this blog are:

• Revisiting Normalization and Denormalization.
• Pay Me Now Or Pay Me Later
• The Argument for Normalization
• First Normal Form
• Second Normal Form
• Third Normal Form and Calculated Values
• The Argument for Denormalization
• Denormalization Patterns
• Keeping Denormalized Values Correct (this essay)
• Triggers, Encapsulation and Composition
• The Data Dictionary and Calculations, Part 1
• The Data Dictionary and Calculations, Part 2

Data and Code at the Application Level

This week I would like to address the assertion that "code is data" and how the application developer might benefit or be harmed by this idea in the practical pursuit of deadlines and functioning code. For some reason my essay written back in May, Minimize Code, Maximize Data got picked up on the blogosphere on Thursday, and comments on ycombinator, on reddit.com, and on the post itself have suggested the thesis is flawed or unworkable because "code is data." Let's take a look at that.

Credit Where Credit Due

I first heard the thesis "Minimize Code, Maximize Data" from A. Neil Pappalardo. I consider it the "best kept secret in programming" because I personally have found it to be almost completely absent from my own day-to-day experience with other programmers.

However, glomek over at reddit.com also credits Eric Raymond with the following quote, "Smart data structures and dumb code works a lot better than the other way around."

Also, sciolizer over on the news.ycombinator.com comments area gives us these quotes from some of the greats:

• Fred Brooks: "Show me your flow charts and conceal your tables and I shall continue to be mystified, show me your tables and I won't usually need your flow charts; they'll be obvious."
• Rob Pike: "Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming."
• Eric S. Raymond (again): "Fold knowledge into data, so program logic can be stupid and robust."
• Peter Norvig: "Use data-driven programming, where pattern/action pairs are stored in a table."

And finally, Kragen Javier Sitaker left a comment on my original essay mentioning Tim Berners-Lee and his theory of "least power." You can read a description of that here.

So Why Do They Say Code is Data?

The suprising answer is that code is data, in particular contexts and when trying accomplish certain tasks. The contexts do not include application development, and the tasks do not involve storing of customer information, but the fact remains true for those who work in the right contexts.

As an example, at the bottom layer of the modern computer are the physical devices of CPU and RAM. Both the computer program being executed and the data it operates on are stored in RAM in the same way. This is called the Von Neumann architecture. Its a fascinating study and a programmer can only be improved by understanding it. At this level code is data in the most fundamental ways. There are many many other contexts and tasks for which it is true that code is data.

But we who create applications for customers are separated from Von Neumann by decades. These decades have seen a larger and larger stack of tools that allow us to concentrate on specialized tasks without worrying about how the tools below are doing their jobs. One of the most significant sets of tools that we use allow us to cleanly separate code from data and handle them differently.

The One and Only Difference

Trying to explain the differences between code and data is like trying to explain the differences between a fish and a bicycle. You can get bogged down endlessly explaining the rubber tire of the wheel, which the fish does not even have, or explaining the complexity of the gills, which the bicycle does not even have.

To avoid all of that nonsense I want to go straight to what data is and what code is. The differences after that are apparent.

Data is an inert record of fact. It does nothing but sit there.

A program is the actor, the agent, the power. The application program picks up the data, shakes it, polishes, and puts it down somewhere else (as in picking it up from the db server, transforming it into HTML, and delivering it to a browser).

To repeat: data is facts. Code is actions that operate on facts. The one and only difference is simply that they are not the same thing at all, they are a fish and a bicycle.

Exploiting The Difference

All of the quotes listed above, and my original essay in May on the subject, try to bring home a certain point. This point is simply that the better class of programs are those that begin with a distinction between fact and action, and seek first to organize the facts and only then to plan the actions.

Put another way, it is of enormous practical advantage to the programmer to fully understand that first and always he is manipulating facts (data). If he ignores the principles of how facts are organized and operated on, he can never reach his full abilities as a programmer. Only when he understands how the facts are organized can he see the clearest program designs.

And Again: Understand the facts first. From there design your data structures. After that the algorithms write themselves.

Minimizing and Maximizing

The specific advice to minimize code and maximize data is nothing more than taking the idea to its logical conclusion. If I write program X so that the data structures are paramount, and I find the algorithms to be simple (or "dumb" as ESR would say), easy to write and easy to maintain, don't I want to do that all of the time?

Conclusion

The wise programmer is one who can take the wisdom and theory of the industry and correctly judge what is appropriate and applicable and what is not. This is the programmer who has a shot at keeping focused, making budget and making deadlines. He knows when a generalized routine will support the overall project and when to just code the case at hand and move on.

The unwise programmer is one who cannot properly apply a theoretical concept to the correct context, or cannot judge the context in which a concept is appropriate. He is the one who produces mammoth abstractions, loses sight of the end-goals of the check-signers and end-users, and never seems to be able to make the deadline.

Of all of the advice I have received over the years, one of the most useful and productive has been to "minimize code, maximize data." As an application developer and framework developer it has served me better than most.

The Argument For Denormalization

There are links to related essays on normalization and denormalization at the bottom of this post.

This blog has two tables of contents, the Topical Table of Contents and the list of Database Skills.

Non-normalized, Normalized and Denormalized

A nonnormalized database is a disorganized one, where nobody has bothered to work out where the facts should be stored. It is like a stack of paper files that has been tossed down the stairs. We are not interested in non-normalized databases.

A normalized database has been organized so that each fact is stored in exactly one place (2nf and greater) and no more than one fact is stored in each place (1nf). In a normalized database there is a place for everything and everything is in its place.

A denormalized database is a normalized database that has had redundancies deliberately re-introduced for some practical gain.

Most denormalizing means adding columns to tables that provide values you would otherwise have to calculate as needed. Values are copied from table to table, calculations are made within a row, and totals, averages and other aggregrations are made between child and parent tables.

Related Essays

If you are a first-time reader of this blog, I recommend taking a look at Third Normal Form and Calculated Values and Denormalization Patterns, which cover issues related to today's post.

The Practical Problems Of Normalization

There are four practical problems with a fully normalized database, three of which I have listed before. I will list them all here for completeness:

1. No calculated values. Calculated values are a fact of life for all applications, but a normalized database lacks them. The burden of providing calculated values must be taken up by somebody somehow. Denormalization is one approach to this, though there are others.
2. Non-reproducible Calculations. If you do not store calculated values in your database, your application must generate them on the fly as needed. If your application changes over time, you risk not being able to reproduce prior results when the business rules drift far enough from the original.
3. Join Jungles. When each fact is stored in exactly one place, you may find it daunting to pull together everything needed for a certain query. A query joining 4,5, 7 or even 12 tables may be required for something the end-user considers trivial and easy. Such queries are hard to code, hard to debug, and dangerous to alter.
4. Performance. When you face a JOIN jungle you almost always face performance problems. A JOIN is a very expensive operation compared to a single-table read, and the more JOINs you have the worse it gets.

The Convenience Argument

The convenience argument addresses the first problem listed above, no calculated values. When calculated values are generated and added to tables, it is far easier for downstream programmers (including members of the customer's IT department) to generate their own reports and ad-hoc queries. It is also much easier for members of the original team to generate display pages and reports.

This convenience is not a result of the simple presence of the calculated values. The convenience stems from the fact that the downstream programmers do not have to get involved in code that generates or calculates the values. They do not have to know anything about the API, the language the app was written in, or anything else, they just have to pull the data they need.

This convenience goes beyond the programmers to semi-technical users who may want to use their favorite 3rd party reporting tool (like Crystal Reports) to query the database. If your application API will not work with their favorite tool (or if you don't have an API), then you have a dissappointed customer. But if the data is right there in tables they can pretty much use anything.

At this point you may be saying, sure, that's fine, but views get all of this done without denormalizing. That is true, but when we go on to the next 3 arguments we will see something of why denormalizing often wins out over views.

The Stability Argument

Every healthy computer program changes and grows as new users and customers make use of it. During this process it is inevitable that later customers will request significant changes to very basic functions that were coded early on and are considered stable. When this happens the programmers have the daunting task of providing the original functionality unchanged for established customers, while providing the new functionality for the newer customers.

Denormalizing can help here. When derived values are calculated during write operations and put directly into the database, they can basically stay there forever unchanged. When a significant new version brings newer code to older users, there is no need to fear that that an invoice printed last week will suddenly come out with different numbers.

There still remains of course the fact that a bug in this whole effort means future calculations are wrong, and the worst case is when a bug gets out to production and generates bad calculated values. When this happens you face the prospect of fixing bad data on a live system. This is definitely my least favorite thing to do.

The Simple Queries Argument

The third problem listed above is JOIN jungles: queries that involve so many JOINs that they become impractical to write, difficult to debug, and dangerous to change.

When you denormalize a database by copying values around between parent and child tables, you reduce the number of JOINs that are required. Very obvious examples include things like copying an items price onto an order_lines table when a customer puts an item in their cart. Each time you copy a fact from one table to another, you eliminate the need for a JOIN between those two tables. Each eliminated JOIN is a simpler query that is easier to get right the first time, easier to debug, and easier to keep correct when changed.

This argument also goes directly back to the convenience argument. If that huge customer you just landed is happy to hear that they can use Crystal Reports to generate reports, you may still face disappointment when they find the reports involve "too many tables" from their perspective for reports that "ought to be simple".

The Performance Argument

The final argument proceeds from our fourth problem listed above. Normalized databases require a lot more JOINs than denormalized databases, and JOINs are very expensive. This means that, overall, any operation that reads and presents data will be more expensive in a normalized database than a denormalized one.

Once we reduce the JOINs by copying data between tables, we end up improving performance because we need fewer JOINs to retrieve the same number of facts.

Denormalization is not the only way to get the convenience of copied values and calculated values. Views and materialized views are the most often mentioned alternatives. The choice between denormalizing and using views has a lot to do with the Pay Me Now or Pay Me Later decision.

Conclusion

Denormalization is not an absolute: it is not one of those things that all wise experienced programmers always do, and it is not something that only fools ignore. The four arguments listed here have guided me well in deciding when to denormalize (and when not to), and I hope that they are of some benefit to you when you face the same decisions.

Related Essays

This blog has two tables of contents, the Topical Table of Contents and the list of Database Skills.

The normalization essays on this blog are:

• Revisiting Normalization and Denormalization.
• Pay Me Now Or Pay Me Later
• The Argument for Normalization
• First Normal Form
• Second Normal Form
• Third Normal Form and Calculated Values
• The Argument for Denormalization (this essay)
• Denormalization Patterns
• Keeping Denormalized Values Correct
• Triggers, Encapsulation and Composition
• The Data Dictionary and Calculations, Part 1
• The Data Dictionary and Calculations, Part 2

The Argument For Normalization

This week we will review the practical arguments in favor of normalization. The major concern as always on this blog is to examine database decisions in light of how they affect the overall application. The major argument for normalization is very simple: you end up coding less, coding easier, and coding stronger, and you end up with fewer data errors.

There are links to related essays on normalization and denormalization at the bottom of this post.

This blog has two tables of contents, the Topical Table of Contents and the list of Database Skills.

Informal Description of Normalization

When I find a programmer who is stuck trying to grasp the concepts of normalization, the problem usually comes down to not being able to see the big picture. The programmer may read any number of rigorous papers on the subject (the Wikipedia article is a good place to start) but still be unable to get the basic point. This leaves the programmer stumbling through table design, second-guessing himself, and then running through a frustrating sequence of redesigns. In the worst case it leads him to conclude normalization may not be worth the effort, at which point he starts writing really crappy applications.

The goal of normalization in simple terms is just this: to store each fact in exactly one place. When you put each fact in only one place, you always know where to go to read it or write it. When facts are repeated in the database, the application programmer has an increased burden to make sure they are all consistent. If he fails to shoulder this burden completely, the database will have inconsistent values for the same facts, leading to emergency phone calls and emails requesting help. These request for help always come at 4:30pm as you are getting ready for a date or an extended vacation.

Once the programmer understands this very simple goal, he usually has an "aha!" moment reading the various articles on normalization. Each rule for normalizing suddenly makes more sense, as it appears as just another way to make sure that there is a place for everything and everything is in its place.

The Programmer's Burden

When a programmer is dealing with a non-normalized database, he is going to run into 4 problems over and over again. Three of these are called "anomalies" and the fourth is "inconsistency" (a fancy way of saying the database holds bad data). Most authors who write on normalization take it for granted that the reader can readily see why the anomalies are bad, but I would like to spell it out here to make it crystal clear. First we will look at the three kinds of anomalies, then we will go to the inconsistency problem, and see exactly how they affect the programmer.

Consider a fledgling programmer who has ready too many Web 2.0 blogs saying that relational databases are bad, and so has not bothered to learn anything about them. In the name of "simplicity", he creates a single table that lists employees, their email addresses, the customers they are assigned to, and the primary email address of each customer. This will lead to three kinds of anomaly, each of which leads to inconsistency.

An Update Anomaly occurs when a fact is stored in multiple locations and a user is able to change one without changing them all. If a user goes to this employee-customer table and changes an employee's email on only one row, and no provision is made to change the others, then the database now has inconsistent values for the employee's email.

An Insert Anomaly occurs when it is not actually possible to record a fact. If an employee is hired but not yet assigned to any customers, it is not possible to store his email address!

A Delete Anomaly occurs when the user deletes one fact and clobbers some other fact along the way. If an employee goes on leave, so that we must remove (delete) their assignments, then we have lost their email address!

This non-normalized database requires the programmer to write additional application code to try to intercept and correct these issues. This is the Programmer's Burden in a non-normalized situation, and it gets worse and worse as the program expands.

The Programmer's Burden also emerges as a continuing stream of complaints from users that "the program is wrong." For every case where the programmer fails to provide exception-handling code, a user will stumble across inconsistent data. The customer says, "it says 'X' on this screen but it says 'Y' on that screen, what's going on?" As far as they are concerned it is a bug (which of course it is) and must be fixed. You can't make money coding new features when you are fixing garbage like that.

The Basic Argument

So the basic argument for normalization is: we wish to avoid the Programmer's Burden as completely as possible. We want to spend our time on cool features, not going back over and over to fix features we thought were finished already.

Special Comment on First Normal Form

First normal form is different from the others. When a database designer violates the higher normal forms, the result is that a fact is recorded in more than one place. However, when you violate first normal form it results in more than one fact in the same place.

A basic example would be the same table of employees and customers, where we "solve" the problems listed above by storing only one row for each employee, with a comma-separated list of accounts, like so:

EMPLOYEE   EMAIL                     CUSTOMERS
------------------------------------------------------------
ARANDOLPH  art@praxis.com            100, 523, 638, 724
SRUSSELL   sax@overlook.edu          516, 123, 158
PBOYLE     phyllis@sp-elevataor.com  713, 928, 212

The above scheme increases the Programmer's Burden because now he must decompose the data that comes from the server. In technical terms we say that the value CUSTOMERS is non-atomic, it is not a single fact. Every piece of code that touches that table must break down the list of customers and sometimes reassemble it.

To see this, consider the basic task of adding a customer for employee Art Randolph. If the tables were set up properly, you would insert into a cross-reference of employees and customers, and duplicates would be trapped by a primary key. But here you must retrieve the list of existing customers, split it up in application code, and check that the value is not repeated. Then you have collapse the list back down and send it up to the server.

All I can say is, no thanks.

By The Way, What Is The Right Way?

Now that we have beat up our fledgeling programmer's lousy employee-customer table, it would be worthwhile to spell out how to do it correctly.

First off, we always need one table for each kind of thing we are keeping track of. That means we will have a table of employees and a table customers. This solves all of the anomalies and inconsistencies listed above because we put facts about employees in the employees table (like email address) and facts about customers in the customers table.

This leaves the issue of linking employees to customers. There are three ways to do it:

1. If each customer gets a team of employees assigned to them, but an employee only ever works for one customer, then put a Foreign Key on the employees table that links to the customers table.
2. If each employee works on more than one customer, but each customer gets only one employee, then put a foreign key on the customers table that links back to employees.
3. If an employee can work for more than one customer and vice-versa, make a Cross-reference between customers and employees.

Conclusion

This week we have seen a fairly simple argument for normalization, and one that regular readers of this blog have seen before: normalization eliminates unnecessary coding burdens. It is hard enough to get software projects done on time and on budget without imposing additional labor that could be avoided entirely by normalizing.

I do not mean to imply that normalizing takes no time or is instantly easier than a fear-based retreat into coding your way out of things. It does take time to learn to normalize and it does take time to learn to code an application around normalized tables. In my own experience I passed through the various erroneous mindsets that I make fun of in this blog, and each time I put effort into learning the "right way" then every effort I made after that was forever easier, had fewer bugs, and made my customers more happy. So I am not saying it is free, but I am saying it is one of the best bargains in town.

Related Essays

This blog has two tables of contents, the Topical Table of Contents and the list of Database Skills.

The normalization essays on this blog are:

• Revisiting Normalization and Denormalization.
• Pay Me Now Or Pay Me Later
• The Argument for Normalization (this essay)
• First Normal Form
• Second Normal Form
• Third Normal Form and Calculated Values
• The Argument for Denormalization
• Denormalization Patterns
• Keeping Denormalized Values Correct
• Triggers, Encapsulation and Composition
• The Data Dictionary and Calculations, Part 1
• The Data Dictionary and Calculations, Part 2

The Quest for the Absolute

This is the Database Programmer blog, for anybody who wants practical advice on database use.

There are links to other essays at the bottom of this post.

This blog has two tables of contents, the Topical Table of Contents and the list of Database Skills.

Today I am taking a huge detour from technical matters to lay out the philosophical groundwork behind this blog. The ideas presented today lie beneath every essay on this site. It is easy to observe that people seem driven to formulate absolute truths to guide their pursuits. Programming is no different, programmers are driven to find the absolutes that will universally guide their efforts. Those absolutes are not that hard to find, if you know the method for seeking them out. Fortunately, we have hundreds and thousands of years of human efforts, both successes and failures, to draw upon when embarking upon the task.

Absolutes in the Post-Modern Age

Academics refer to our current stage of history as the "Post-Modern" age. Thinking in the post-modern age is dominated by a deep mistrust of the very concept of absolute truth. Many thinkers have noted that in the post-modern age the only absolute is that there are no absolutes. Now, anybody who has not bothered to read much past what they are handed likely believes much of this without even thinking about it, they may not know that in the history of the human race such thinking is less than 60 years old.

But that "no absolutes" stuff is all nonsense at best and downright cowardice at worst. If you want an example of an absolute truth, try stepping off the edge of a cliff: even if you do not believe in gravity, gravity believes in you. It is an absolute truth for me that if I do not take care of my customers my life becomes unpleasant. It is a further absolute truth for me that I constantly obvserve programmers proclaiming absolutes (always use relational, always use OO, etc). When I stop observing it, then I suppose it won't be an absolute anymore (and I suppose then it never was?)

So let us now cheerfully ignore the wailing of those who cry that there are no absolutes, and ask if we might discover some elements of software development strategy that hold true always (ok, maybe mostly always) for the context of database application development.

Aristotle and Virtue

Nowadays nobody has to read philosophy much anymore, at least not where I live (in the United States), so most programmers have never heard of a man named Aristotle, who lived about 2500 years ago. This is a shame, because Aristotle had a logical way of thinking about things that would warm the heart of any programmer.

One of Aristotle's major contributions to civilization was his formulation of what philosophers call "virtue". Philosophers use the term in a technical sense, and they do not use "virtuous" to mean "nice" or "pleasant" or "good-natured." To a philosopher (or at least those that taught me) something is virtuous in Aristotelean terms if if performs its function well. The standard classroom example is that a virtuous table serves the function of a table, and a virtuous table maker is somebody who makes good tables.

This is a very useful concept for programmers. If we want to speak of a "virtuous" program, we mean simply one that meets its goals. This takes the whole high-minded theory and philosophy stuff back to real down-to-earth terms. (This is why I always preferred Aristotle to Plato).

In the quest for the absolute, if we let the ancient philosophers guide us, we discover the surprisingly basic idea that our programs should perform their functions well if they are to be called virtuous. This is easy to swallow, easy to understand, and easy to flesh out.

What is a Virtuous Computer Program?

A virtuous computer program is one that serves its purpose well, and so we need to flesh out the three purposes that are common to most programs:

• To meet some institutional or strategic goal of those who sign the checks (or accept the work as charity in some case).
• To meet the goals of end-users, which almost always comes down to performance and ease-of-use.
• To provide income for the developers (or meet their own goal of providing charity work for non-profits).

Notice what is not on the list, things like ensure all data resides in a relational database, or implement all code in strictly object-oriented languages. We are not nearly ready to consider such specific strategies as those, they are completely out of place here in a discussion of the unifying goals of all projects.

So let's review. So far we know that the absolutes of programming are the pursuit of virtue, which turns out to be a fancy way of saying that the program should perform its functions well, which turns out to mean simply that it should do what the check-signer asked for, in a way that is workable for the end-users, and at a price that keeps the programmer fed.

This leads us towards strategies for reaching those goals.

The Virtuous Programming Strategy

Continuing with the idea that a virtuous program meets is basic goals, we can say that a virtuous strategy smooths the way for a programmer to meet the basic goals. An unvirtuous (or just plain bad) strategy litters the path with obstructions or ends up not meeting the goals of the check-signer, end-users, programmer, or all of the above.

Before we can begin to formulate a strategy, we must look next at the reality of the programming world. Some of the fundamental realities include (but are not limited to):

• The end-user or check-signer may not fully understand or be able to articulate their requirements.
• The programmer may not correctly understand requirements, even when correctly articulated.
• In a healthy prosperous situation there will be new requirements that interact with established requirements in ways that range from no interaction at all to fiendish incompatibilities.
• The world will change around you, creating demands that did not exist when the system was created (some of us can still remember when there was no internet).
• Staff will come and go.
• ...and so on.

So even before we begin formulating particular strategies for particular situations, we recognize that our strategy had underlying goals it must facilitate, such as:

• Being easy to change, both for correcting mistakes and adding features.
• Being able to maintain and sort out possibly contradictory requirements that arise as the years go by.
• Requiring little or no "deep magic" that depends on arcance knowledge of employees who may depart.
• Being able to expect the unexpected (like the explosion of the web etc.)

Only after we have worked through to this point can we begin to evaluate specific strategies and technologies. We can now begin to ask about the proper context of the database server, where to use object orientation, and if javascript is a good programming language. Anything that responds to our core goals and realities can be considered for use, anything which does not play into the core goals is useless at best and obstructive at worst.

Future essays (and some past essays) in this series will refer back to these ideas. For example, many developers have observed over the years that if you Minimize Code and Maximize Data then you gain many advantages in terms of development time, robustness, and feature count. Other ideas similar to this will come out over and over in future essays in this series.

Conclusion

The strategies and techniques that you will see on this blog are all aimed at one way or another towards the goals expressed in this essay. At the very beginning comes the goals of the check-signer, the end-users, and the programmer. From there we seek strategies that will satisfy our need to grow, change, correct, and adapt. Only then can we ask about the technologies such as databases and object-oriented languages and see how well they let us meet all of these goals.

Related Essays

This blog has two tables of contents, the Topical Table of Contents and the list of Database Skills.

Other philosophy essays are:

Prepare Now For Possible Future Head Transplant
• The Quest for The Absolute (this essay)
• I Am But A Humble Filing Clerk
• Why I Do Not Use ORM
• Minimize Code, Maximize Data

Topical Table of Contents

This posting is updated whenever a new post goes up.

There is a also a Skills-oriented Table Of Contents. It is not as complete as this list, which lists all posts, but it is more centered on links as they relate to skills.

If you want some free analysis, why not submit your schema to the Database Programmer? If you are willing to discuss your issues with a bit of public exposure, I will provide free analysis, and everybody can benefit!

User-Submitted Analysis Topic: Email

The Application Stack

• A Working Definition of Business Logic, With Implications for CRUD Code
• The Cost of Round Trips To The Server
• Critical Analysis of An Algorithm: Sproc, Embedded SQL, ORM
• Historical Perspective of ORM and Alternatives
• The Framework And The Database
• Data And Code At The Application Level
• Approaches to UPSERT
• Why I Do Not Use ORM

Table Design Basics: Keys, Normalization, Denormalization

The first group of posts introduces the must-know terms and techniques for table design.

It might be a good idea to start with The Relational Model.

• Introduction (spell it out or figure it out)
• Primary Keys
• Foreign Keys
• First Normal Form
• Second Normal Form
• Third Normal Form and Calculated Values
• Of Tables and Constraints (also listed below in Table Design Patterns)

Following up on the normal forms are some basic discussions of normalization and denormalization.

• The Argument For Normalization
• The Argument For Denormalization
• Revisiting Normalization And Denormalization
• Denormalization Patterns
• Keeping Denormalized Values Correct
• The Data Dictionary and Calculations, Part 1
• The Data Dictionary and Calculations, Part 2

Table Design Patterns

The second subseries details commonly occurring patterns in table design, how to recognize them and when to use them.

There is a complete List of Table Design Patterns. The rest of the entries are:

• A Sane Approach To Choosing Primary Keys
• Different Foreign Keys for Different Primary Keys
• Cross Reference Validation Pattern
• Limited Transaction Pattern
• False Patterns and the Reverse Foreign Key
• The Primary Key That Wasn't: Impermanent Primary Keys
• Resolutions (Also listed in Queries below)
• Of Tables And Constraints (Also listed above in keys, normalization, denormalization)
• How the SQL UNION Affects Table Design (Also listed below in Queries)
• History Tables
• Secure Password Resets
• A Case When Table Design is Easy and Predictable (combinatorial and maximum complexity)

SQL SELECT and Queries

• Introduction To Queries
• GROUP BY, HAVING, SUM, AVG and COUNT(*)
• How SQL UNION Affects Table Design
• The JOIN is the Cornerstone of Powerful Queries
• Joins Part Two, The Many Forms of JOIN
• Resolutions (Also listed in Table Designs Above)
• Recursive Queries With Common Table Expressions
• The Really Cool NTILE() Window Function

Algorithms and Processes

• Sequencing Dependencies

Server-Side Code

• Triggers, Encapsulation and Composition
• Loops Without Cursors

Analysis

• The Requirements Are Always Wrong
• This Application Has Unique Business Rule Needs

Development Cycle

• Table Structure Changes
• Dictionary Based Database Upgrades
• Upgrading Indexes With A Data Dictionary

Philosophy

• Minimize Code, Maximize Data
• The Quest For The Absolute
• I Am But A Humble Filing Clerk
• Triggers, Encapsulation and Composition (repeated here because there is some philosophy in there)

Data Dictionary

Many of these posts are listed elsewhere in this table of contents, but I wanted to have them altogether in one place as well.

• Using a Data Dictionary
• The Data Dictionary and Calculations, Part 1
• The Data Dictionary and Calculations, Part 2
• Dictionary Based Database Upgrades
• Upgrading Indexes With A Data Dictionary

Security

• Introducing Database Security
• A Comprehensive Database Security Model
• Secure Password Resets

Performance

• Huge Inserts
• Pay Me Now or Pay Me Later
• The Web Layer

The Browser

• The Wonderful Awful Browser
• Javascript As a Foreign Language

Advanced Table Design: Secure Password Resets

Most web-based database applications make use of email to allow users to change their passwords. Completing securing this operation can be tricky business, and one of the best ways to do it is to user database server abilities.

Disclaimer 1: Only As Secure as Email

We tend to take it for granted today that password reset systems work through email. We reason that if a user can access an email sent by us then they are who they say they are. Obviously this will not be true if a user's email account has been compromised.

Dealing with the possibility of compromised email accounts is outside the scope of this week's essay. There are other strategies available to reduce that risk, but they will be treated in some future essay.

Disclaimer 2: Only SSL (HTTPS) of Course!

It is not much use giving yourself a super-secure email system if you transmit sensitive information over unencrypted connections. Secure Socket Layers (SSL) should always be used when high security is required. For the end-user this means they are going to a site through HTTPS instead of HTTP.

Password Resets vs. Sending Passwords

On some low-security systems it is acceptable to send a user his password in an email. This approach is very ill-advised in higher security contexts because we have no control over the user's storage of that email. It could end up anywhere, and anybody might read it.

When security requirements are higher, it is better to force the user to reset their password. There are several reasons for this, but the important one here is that we do not want to send the actual password in an email. Therefore we must send a link that sends them to a page where they can provide a new password.

The Requirements

If we spell out the requirements for a secure password reset system, they are at the very least these:

1. We must generate some hash and send it to the user, this is how she will identify herself so we can let her change her password.
2. The hash must expire at some point, since we cannot be sure the user will completely purge out the email (or that he even can, depending on the policy of the email host).
3. It must be completely impossible for anybody to read the hash, otherwise they could intercept the reset process and set a password for themselves.
4. Despite requirement 3 just listed, we must somehow verify the hash when the user presents it.
5. We must be able to change the user's password, which is a priveleged operation, even though the user is not even logged in.

It is not actually possible to implement these requirements in application code alone (or perhaps I should say is not possible to do it and meet minimum acceptable risk). There are two problems if you try it:

1. Requirements 3 and 4 cannot be reconciled. If the application is able to read the hash to verify it, then a vulnerability in the application code could lead to compromise. If we implement in application code we have the burden of ensuring practically zero vulnerabilities, while if we go server-side we have no such burden (at least for this feature).
2. Requirement five requires the application code to connect at a very high privelege level, which could lead to completely unrelated vulnerabilities.

Implementing In The Database

The system I will now describe meets all 5 of the requirements listed above while never requiring a priveleged connection to the database. The feature is implemented in an isolated system that cannot touch other systems, and it has no burden to be particularly careful in writing the application code.

Since a picture is worth a thousand words, here it is:

The process begins at the top left. The user (Yellow circle) clicks on some "Forgot Password" link and provides an email or account id. This goes to web server which generates an INSERT to the insert-only table of hashes. This insert contains only the user's id, nothing else is needed. There is a trigger on the table that fires on the INSERT. This trigger generates the hash and sends the email to the user.

The salient features here are that the table is insert-only, which is explained below, and that the trigger operates at super-user level, which is also explained below.

Once the user receives the link and clicks on it, our process goes over to the right. The user lands on a page and provides a new password (and probably of course must type it in twice). The web server does basic things like making sure the two values match, that the password is long enough, and like that, and then generates an INSERT into a second table. The insert contains the email or account ID, the hash, and the desired new password.

The magic begins on the INSERT into the second table. An INSERT trigger running at superuser level is allowed to look at the first table and verify the hash and its expiration. If these match, it sets the user's password.

Simple, really, IMHO.

Feature 1: Insert Only Tables

This system depends on creating tables that any unpriveleged user can insert into, but which nobody can SELECT from or UPDATE to or DELETE from.

This may sound like a joke: "Insert Only Table", something like "Write only memory". But the idea is very simple, if nobody can SELECT from the table then nobody can discover active hashes. If nobody can UPDATE the table then nobody can forge hashes. Finally, if nobody can DELETE from the table then nobody can cause mischief.

The code for the tables looks like this:

-- FIRST TABLE
CREATE TABLE users_pwrequests
(
  recnum_pwr integer,
  user_id character varying(40),
  md5 character(32),
  ts_ins timestamp without time zone,
)
-- NOTE! This syntax is PostgreSQL, there may be
-- slight variations on other platforms.
REVOKE ALL ON TABLE users_pwrequests FROM PUBLIC;
GRANT INSERT ON TABLE users_pwrequests FROM PUBLIC;

-- SECOND TABLE
CREATE TABLE users_pwverifies
(
  recnum_pwv integer,
  user_id character varying(40),
  md5 character(32),
  member_password character varying(20),
)
REVOKE ALL ON TABLE users_pwverifies FROM PUBLIC;
GRANT INSERT ON TABLE users_pwverifies FROM PUBLIC;

Feature 2: Trigger Security Priveleges

It is possible on most servers to severely limit a user's allowed actions on a table, but then to provide trigger code that fires on those actions and executes a super-user level. Today's technique depends upon this ability. Trigger code operating at superuser level can look at the insert-only table to verify a hash, and it can also set the user's password.

This basic ability is what makes triggers so amazing and cool for implementing business logic (see also Triggers and Encapsulation), because there is no way for a user to directly invoke a trigger for his own nefarious purposes, and there is no way for a cracker to avoid the firing of the trigger if he performs an action on a table. Triggers are truly the most powerful example of encapsulation of data and code that is available to today's programmer.

The first trigger looks something like this ( this is PostgreSQL code, your server will likely require variations) (I have also stripped it down for brevity, it may not work exactly without modification):

CREATE OR REPLACE FUNCTION users_pwrequests_ins_bef_r_f()
  RETURNS trigger AS
$BODY$
DECLARE
    NotifyList text = '';
    ErrorList text = '';
    ErrorCount int = 0;
    AnyInt int;
    AnyRow RECORD;
    AnyChar varchar;
    AnyChar2 varchar;
    AnyChar3 varchar;
    AnyChar4 varchar;
BEGIN
    -- necessary for an old glitch in pg security
    SET search_path TO public;

    -- Only execute if the user's id is valid
    SELECT INTO AnyInt Count(*)
           FROM users WHERE user_id = new.user_id;
    IF AnyInt > 0 THEN 
       SELECT INTO AnyChar email
              FROM users WHERE user_id = new.user_id;
       -- This lets you put the email itself into 
       -- a table for admin control
       SELECT INTO AnyChar2 variable_value
              FROM variables
             WHERE variable = 'PW_EMAILCONTENT';
       -- Also the server is stored in a table
       SELECT INTO AnyChar3 variable_value
              FROM variables
             WHERE variable = 'SMTP_SERVER';
             
       -- This becomes the email FROM Address
       SELECT INTO AnyChar4 variable_value
              FROM variables
             WHERE variable = 'EMAIL_FROM';
       IF AnyChar4 IS NULL THEN AnyChar4 = ''; END IF;
       
       -- Very important! Set the md5 hash!
       new.md5 := md5(now()::varchar);
       
       -- Call out to a stored procedure that sends emails
       PERFORM pwmail(AnyChar
          ,'Password Reset Request'
          ,AnyChar2 || new.md5
          ,AnyChar3
          ,AnyChar4);
       EXECUTE ' ALTER ROLE ' || new.user_id || ' NOLOGIN ';
    END IF;    -- 3000 PK/UNIQUE Insert Validation

END; $BODY$
  -- The "SECURITY DEFINER" is crucial, it allows 
  -- the trigger to run as the super-user who 
  -- created it
  LANGUAGE 'plpgsql' VOLATILE SECURITY DEFINER

The second trigger looks like this:

CREATE OR REPLACE FUNCTION users_pwverifies_ins_bef_r_f()
  RETURNS trigger AS
$BODY$
DECLARE
    NotifyList text = '';
    ErrorList text = '';
    ErrorCount int = 0;
    AnyInt int;
    AnyRow RECORD;
    AnyChar varchar;
    AnyChar2 varchar;
    AnyChar3 varchar;
    AnyChar4 varchar;
BEGIN
    SET search_path TO public;

    -- Read the first table to see if the 
    -- link is valid and has not expired
    SELECT INTO AnyInt Count(*)
           FROM users_pwrequests
          WHERE user_id = new.user_id
            AND md5     = new.md5
            AND age(now(),ts_ins) < '20  min';         
    IF AnyInt = 0 THEN                                
        ErrorCount = ErrorCount + 1; 
        ErrorList  = ErrorList || 'user_id,9005,Invalid Link;';
    ELSE 
       -- Magic!  The user's password is set
        EXECUTE 'ALTER ROLE ' ||  new.user_id 
            || ' LOGIN PASSWORD ' 
            || quote_literal(new.member_password);
            
        -- Very important!  Now that we have set it,
        -- erase it so it is not saved to the table
        new.member_password := '';
    END IF;    -- 3000 PK/UNIQUE Insert Validation

    IF ErrorCount > 0 THEN
        RAISE EXCEPTION '%',ErrorList;
        RETURN null;
    ELSE
        RETURN new;
    END IF;
END; $BODY$
  LANGUAGE 'plpgsql' VOLATILE SECURITY DEFINER;

Feature 3: Sending Email From Database Server

The technique present above requires that your database server be able to send emails. This is not always possible. Postgresql (www.postgresql.org) can do it, and I have to believe the other big guys can as well, but I have not tried it yet personally.

To send emails through a PostgreSQL server, you must install Perl as an untrusted language, and then install the Perl MAIL package. If anybody wants to know more about that then please leave a comment and I will expand the essay to include that.

Feature 4: The Empty Column

There is one more note that should be made. To use this system, you must tell the server the user's desired new password. To do that, you must actually make it part of the INSERT command and therefore you must have a column for it in the 2nd read-only table. However, you certainly do not want to actually save it, so you have the trigger set the password first and then blank out the value, so the final row saved to the table does not actually contain anything. This is noted in the code comments on the second trigger, which is included above.

Conclusion

The technique presented today makes full use of database server abilities to create a password reset system that is highly resistant to forgery, interception, and evil-admin meddling. It makes use of a combination of restrictive table security, priveleged trigger code, and sending emails from the database server.

Advanced Algorithm: Sequencing Dependencies

Some database applications require you to perform a series of actions where you know only that some actions must be performed before others. Before you can perform the actions, you must work out a safe sequence that takes into account all of the dependencies. This week in The Database Programmer we will see an algorithm for doing this.

Examples

There are many examples where a programmer must work out dependencies before doing something.

A manufacturing package may track many steps in the manufacture of an item. Some steps cannot be performed until others are complete. A simple system would require the end-user to work out the entire process, but a better system would let the user enter only the dependencies: which processes require others to be complete. In this kind of system the computer can be used to schedule manufacturing tasks.

All popular Linux distributions have a package installation system in which each package lists its required dependencies. If you want to install a large number of packages in one shot, producing a tangled bunch of related dependencies, today's algorithm can be used to work them all out.

If you are using a data dictionary to build tables, every foreign key represents a dependency, where the child table requires the parent table to exist before it can be built. Today's algorithm can be used to sequence the tables and build them in order.

Another database example is generating code to perform calculations. Some calculations will depend on previous calculations, so your code generator must be able to sequence them all so that the calculations are performed in the proper order.

Big Words: Directed Acyclic Graph

The examples abvoe are all cases of what mathematicians call a Directed Acyclic Graph. If you do not want to read the entire Wikipedia article, the main points are these:

• We have a set of items. These can be anything you are keeping track of in your database.
• Any item may be connected to zero or more other items.
• The connection is one-way only. So if we say A requires B, we are not saying that B also requires A (in fact it is forbidden).
• There can be no loops (cycles). If A requires B, B may not require A. Further, if A requires B, and B requires C, C may not require A.

Whenever I can, I like to point out that it is very useful to read up on the mathematical foundations of certain programming techniques. We can often pick up very useful insights from those who think of these things at the most abstract level. It is also much easier to get advice from the more abstract-minded database people if you are at least marginally familiar with the mathematical terms.

The Tables

So now let us proceed to the tables and the code. The tables below show a data dictionary that will be used to generate DDL to build a database:

Table: TABLES

TABLE       | DESCRIPTION            | SEQUENCE
------------+------------------------+---------
ORDERS      | Sales Orders Headers   |  ?
ORDER_LINES | Sales order lines      |  ?
CUSTOMERS   | Customers              |  ?
ITEMS       | Items                  |  ?


Table: DEPENDENCIES

CHILD_TABLE  | PARENT_TABLE
-------------+---------------
ORDERS       | CUSTOMERS
ORDER_LINES  | ORDERS
ORDER_LINES  | ITEMS

The problem here is knowing the safe order in which to build the tables. If I try to build ORDER_LINES before I have built ITEMS, then I cannot put a foreign key onto ORDER_LINES, because ITEMS is not there. In short, I need to know the value of the SEQUENCE column in the example above.

The Expected Answer

The example above is simple enough that we can work it out by hand. This is actually a good idea, because we want to get an idea of what the answer will look like:

TABLE       | DESCRIPTION            | SEQUENCE
------------+------------------------+---------
ORDERS      | Sales Orders Headers   |  1
ORDER_LINES | Sales order lines      |  2
CUSTOMERS   | Customers              |  0
ITEMS       | Items                  |  0

This answer should be self-explanatory, except maybe for the fact that both CUSTOMERS and ITEMS have the same value. We need to look at that before we can see the code that produces it. Is it OK that two entries have the same value, and how would our program handle that?

The short answer is that it is perfectly OK and natural for two or more entries to have the same value. All this means is that they can be done in any order relative to each other, so long as they are done before the other entries.

In terms of the example, where we want to build these tables in a database, it means that:

• We would query the list of tables and sort by SEQUENCE
• We would loop through and build each table
• We don't care about ITEMS and CUSTOMERS having the same value, they get built in whatever which-way the server gives us the list.

The same concept applies to the other potential examples: manufacturing, software packages, and generating calculations. So long as you follow the sequence, we don't care about items that have the same value.

Stating the Solution in Plain English

We are now ready to work out a program that will generate the SEQUENCE column. The basic steps the program must perform are:

1. Initialize the column to -1. A value of -1 means "Not sequenced."
2. Update the column to zero for all items that have no dependencies.
3. Repeat the following action until the affected rows are zero: Update the SEQUENCE column to 1 (then 2, then 3) for all rows that have all of their dependencies sequenced already.
4. Once the command in step 3 is no longer affecting any rows, check for any rows that have -1, these are involved in circular dependencies and we cannot proceed until the user straightens them out.

Stating the Solution in Code

The first step is very easy, we initialize the table with this command:

UPDATE TABLES SET SEQUENCE = -1;

The next step is also very easy, we mark with a '0' all of the tables that have no dependencies. The basic idea is to find all of the entries that have no entries in DEPENDENCIES.

UPDATE TABLES SET SEQUENCE = 0
 WHERE NOT EXISTS (SELECT child FROM DEPENDENCIES
                    WHERE child = TABLES.TABLE)

Now for the hard part. We now have to execute a loop. On each pass of the loop we are looking for all items whose dependencies have all been sequenced. We will do this over and over until the command is not affecting any rows. It is important that we cannot exit the loop by testing if all rows are sequenced, because a circular dependency will prevent this from happening and we will have an infinite loop.

You can control this loop from client code, but I wrote mine as a Postgres stored procedure. This algorithm turns out to be surprisingly complicated. The UPDATE command below may not be all that self-explanatory. What it works out is:

• Get a list of child tables from the DEPENDENCIES table
• JOIN through to TABLES to look at the SEQUENCE value of their parents.
• Group and check that the minimum value is greater than zero, if it is it means all parents are sequenced and the table can be sequenced.
• Update the SEQUENCE value for the tables we found

CREATE OR REPLACE FUNCTION zdd.Table_Sequencer() RETURNS void AS
$BODY$
DECLARE
    -- Note that rowcount is initialized to be > 0, this makes
    -- the loop work properly
    rowcount integer := 1;
    
    -- This tracks the value we are assigning to SEQUENCE.  We
    -- initialize it to 1 because we already took care of the
    -- the rows that have value 0
    lnSeq integer := 1;
BEGIN
    while rowcount > 0 LOOP
        UPDATE tables set SEQUENCE = lnSeq
          FROM (SELECT t1.CHILD 
                  FROM DEPENDENCIES t1 
                  JOIN TABLES       t2 ON t1.PARENT = t2.TABLE
                 GROUP BY t1.CHILD
                HAVING MIN(t2.SEQUENCE) >= 0
                ) fins
          WHERE TABLES.TABLE = fins.CHILD
            AND TABLES.SEQUENCE = -1;

  lnSeq := lnSeq + 1;
  GET DIAGNOSTICS rowcount = ROW_COUNT;
 END LOOP;
 
 RETURN;
END;
$BODY$
LANGUAGE plpgsql;

The stored procedure above will stop executing once the UPDATE command is no longer having any effect. Once that happens, your final step is to make sure that all rows have a valid SEQUENCE value, which is to say that no entry has SEQUENCE of -1. If any of the rows have that value then you have a circular dependency. You must report those rows to the user, and you can also report the dependencies that are causing the loop.

Conclusion

Sequencing dependencies is a fundamental algorithm that has a lot of use cases in database applications. It is easy enough to accomplish, but the innermost UPDATE command can be a little puzzling when you first look at it. Once you have mastered this algorithm you are on the way to the "big leagues" of database applications such as ERP, MRP and others.

Next Essay: Secure Password Resets

Javascript As a Foreign Language

So you know 37 different programming languages, you've programmed moon landers, missiles and toasters, and how could Javascript be any problem? Then you start trying to code up some Javascript and find that it just does not feel right, nothing seems to flow naturally or easily. Your instincts do not seem to guide you. You are not alone, here is your cheatsheet...

Welcome to the Database Programmer blog. If you are trying to write database applications in 2008 then you most likely bump into Javascript. My hope in this week's essay is to provide a "soft landing" into this beautiful and powerful but somewhat strange language.

To see the other essays in this series, consult our Complete Table of Contents.

Contents

Today's essay is rather long. It covers extremely basic ideas but proceeds directly to very powerful techniques. I have provided a summary here so that you can skip over the material that may already be familiar to you.

• Firefox and Firebug
• Execution
• Variable Scope
• Adding Methods to Core Javascript
• Functions as First Class Citizens
• Objects And Classes
• Creating An Object Without A Class
• Accessing Object Properties and Methods
• Iteration
• JSON and Ajax
• Synchronous Ajax: S-JSON
• JQuery and Friends

Start Off: Firefox and Firebug

In case you have been living under a rock for the past few years, let me tell you to do your development in a real web browser, that is, Firefox, and to immediately download the Firebug extension. Firebug more or less does everything you need to debug Javascript, and it has many features you may not even know you need. Do not try to develop Javascript without Firebug.

In particular, firebug has a "console" object that you can send messages to, such as this:

console.log("this is so much better than alert()!");
for(var x = 1; x<10; x++) {
    console.log("We are on "+x);
}

Execution

Javascript executes while your page is being loaded, and can be placed anywhere on the page. While I make no claims that the example below is good or bad practice, it does illustrate how Javascript executes.

<html>
<head>
<script>
// Script is executing as it is encountered,
// so this variable comes into existence
// immediately
var x = 5;  

function square(x) {
    return x * x;
}

// Now that the square function is defined,
// we can call it
var y = square(x);
</script>
</head>
<body>
<h1 id='h1'>Here is a Javascript Example!</h2>

<script>
// Script can be embedded directly in the
// body of your HTML (for better or worse!)
var h1 = document.getElementById('h1');
h1.innerHTML = 'I changed the H1 content!';

// This function can be used anywhere downstream
function changeH1(newText) {
    var h1 = document.getElementById('h1');
    h1.innerHTML = newText;
}
</script>
</body>
<div>Here is a div of text</div>
<script>
changeH1("Changing H1 yet again!");
</script>

Variable Scope

Scoping in Javascript is pretty straightforward. If you assign a value to a variable outside of any function it becomes a global. If you explicitly define a variable as "window.x = 5" it becomes a global. If you put the keyword var in front of it before using it it becomes local (and can mask a global variable of the same name). You can use the "var" keyword inside of loops, and many javascript programmers use "var" everywhere. Here is an example.

<html>
<head>
<script>
// We are executing outside of a function, so
// both of these are globals:
var x = 5;
y = 10;

function example() {
    // Since a global named 'x' exists, and we do
    // not use the "var" keyword, we are re-assigning
    // the global variable
    x = 7;
    
    // Using the "var" keyword makes a local variable,
    // we cannot "see" the global x anymore
    var x = 2;
    alert(x);
    
    // I can still access the global variable to
    // set its value back:
    window.x = 5;
    alert(x);
    alert(window.x);    
}

</script>
</head>

Adding Methods to Core Javascript

Javascript lacks certain functions that are very useful to have, such as trimming spaces from strings. One very cool thing about Javascript is that you can directly add these methods to the core language, by adding functions to the "prototype" object of the core classes. Here is how you add a "trim" function to core Javascript.

String.prototype.trim = function() {
 return this.replace(/^\s+|\s+$/g,"");
}
x = "   abc  ";
alert('-' + x + '-'); // the dashes let you see the spaces
alert('-' + x.trim() + '-');  // spaces removed!

When I first saw this trick I dutifully copy-n-pasted it in and it worked, but the syntax looked very perplexing, I could not figure out how to make use of it myself. My brain had not yet wrapped itself around the Javascript mentality. This leads directly to our next concept, that functions are "first class cizitens".

Functions as First Class Citizens

You may have heard that Javascript treats functions as "first class citizens" and wondered, "what does that mean?" The best way to explain it in terms of other languages is that you can create functions on the fly and pass them around like variables. This may be a little hard to grasp, so we will go directly to examples.

// Most languages support this type of function definition
function square(x) {
    return x * x;
}

// Javascript gives you a slightly different syntax if
// you like, which can be extremely powerful
var square = function(x) {
    return x * x;
}

// The books usually go on to an example like this, 
// which frankly did not seem to me to have any purpose:
y = x;
alert( y(5) );

The basic idea to get here is that you can do anything with a function that you can do with a variable. There are multiple uses for this, but we have already seen one, namely, the ability to add a method to a previously created class. This is what we did above when we added the "trim()" method to the base "String" class. This means that our approach to building class hierarchies is very different than in other Object-oriented languages like PHP, Foxpro, Delphi, VB and so forth.

// This example shows two different ways to add methods
// to HTML elements and make them act more object-oriented.

// Method 1, make a function that makes an INPUT read-only
// by changing its style and setting a property.  Notice
// the code refers to "this" as if it were part of an
// object, see below to see why that works.
function makeReadOnly() {
    this.className = 'readOnly';
    this.readOnly = true;
}

// Now attach that function to a DOM element (an HTML INPUT)
var input = document.getElementById('myInput');
input.makeReadOnly = makeReadOnly;

// Some other code can now tell the input to go into
// read only mode:
function changeModes() {
    var input = document.getElementById('myInput);
    // When this executes, the "this" variable in 
    // the function will refer to "input"
    input.makeReadOnly();
}

There is another way to do this as well, that really illustrates how to make use of Javascript's native abilities:

// Method 2 is to defne the function while adding it
// to the INPUT element.
var input = document.getElementById('myInput');
input.makeReadOnly = function() {
    this.className = 'readOnly';
    this.readOnly = true;
}

// This code works exactly as it did above
function changeModes() {
    var input = document.getElementById('myInput);
    input.makeReadOnly();
}

Now that we have introduced this idea, it will come up all over the place in later examples.

Objects And Classes

When I first tried to use Javascript I kept looking for the "class" keyword, but it's not there! Believe it or not you use the "function" keyword to create what we would call a class in other languages. Here is an example of how to create and instantiate an object in Javascript:

// Here is a simple PHP class for an 
// object that handles a row from a database
class dbRow {
    var tableName = '';
    var rowId = 0;
    
    function dbRow(tableName,id) {
        this.tableId = table;
        this.fetchRow(id);
    }
    
    function fetchRow(id) {
        # ...more code here
    }
}

var x = new dbRow('customers',23);

In Javascript we make a function instead of a class:

function dbRow(tableName,id) {
    // When the object is instantiated, this
    // code runs immediately
    this.tableName = tableName;
    
    // We must define a fetchRow function before
    // we can actually call it....
    this.fetchRow = function(id) {
        // some kind of ajax stuff going on here
    }
    
    // ...and now we can invoke the function
    this.fetchRow(id);
}

// When this command returns we have a new "dbRow"
// object.  
var x = new dbRow('customers',23);

Creating An Object Without a Class

We can say Javascript is "purely dynamic", by which we mean you can define anything on the fly, including ojects, even if you have no class definition (er, I mean no "function()" definition...). You can explicitly create an object by enclosing the definition in curly braces. Properties and their values are assigned with "name: value" syntax, separated by commas. Since you can do anything with a function that you can do with a variable, the following is a nifty way to create an object:

var x = {
    propertyName: 'value',
    otherProperty: 'otherValue',
    
    square: function(x) {
        return x * x;
    }
    // Don't put a comma after the last property!
    // It will work in firefox but not in IE!
}

alert(x.square(5));

This syntax is called "JSON" by the way, for "Javascript Object Notation". If you can get comfortable with JSON you can start to code up some really elegant Javascript.

Accessing Object Properties and Methods

You can hardcode references to an object's properties by using the ".property" syntax, but you can also use variables that hold the name of the property.

// Create an object
var x = {
    first: 'Sax',
    last: 'Russel',
    
    combine: function() {
        return this.first + ' ' + this.last;
    }
}

// You can now explicitly access properties
alert (x.first);
alert (x.last);

// But you can also have a variable hold the name
// of the property you want:
var propName = 'first';
alert (x[propName]);

// Objects can be nested to any depth, and you can
// mix hardcoded and variable names.  If we had a
// complex data dictionary stored on the browser,
// we might get the caption for a column like this:
var tableId = 'customers';
var columnId = 'total_sales';
var caption = dd[tableId].columns[columnId].caption;

This works also for functions. Assuming the same object as the above, we can invoke functions that are named by other variables:

var x = { .... repeated from above example };

var methodName = 'combine';
alert( x[methodName]() );

Iteration

As a database programmer I write a lot of code that iterates arrays and associative arrays. Iteration tends to be very important to database programmers, as it is the most natural way to loop through rows retrieved from a database, or to loop through the values in a row. Basic iteration of an array looks like this:

// make an array 
var myList = [ 'sax', 'anne', 'nirgal', 'frank' ];
for(var idx in myList) {
    // console.log() requires firebug
    console.log("Index and value: "+idx+", "+myList[idx])
}

All of the action is in the line "for(var idx in myList)", this structure will loop through the array. On each pass the variable "idx" will contain the array's index number. To actually get the value you need you have to go looking for myList[idx].

Associate Arrays are a very natural data structure for a database programmer, as they are an easy way to represent a single row retrieved from the database. There is no explicit support for associative arrays in Javascript, but this does not matter because you can use an object and get the same results.

// Here is an object
var myObject = {
   first: 'Sax',
   last: 'Russel',
   occupation: 'Physicist'
}
// Now we loop through it like an associative array
for(var key in myObject) {
    console.log("The array key is: " + key);
    console.log("The value is: " + myObject[key]);
}

JSON and Ajax

Nowadays everybody is jumping into AJAX with both feet. AJAX can be particularly useful to a database programmer, because you can make AJAX calls that return objects (including code), arrays, and database data.

I should note that the term "AJAX" itself means something very precise, being "Asynchronous Javascript and XML", while the example I am about to show contains no XML, so my use of the term is not strictly correct. Nevertheless, many people routinely use the term AJAX to mean any round-trip to the browser that fetches some fragment of information without doing an entire page refresh. While this is regrettable, I'm not going to try to buck that trend here.

That being said, here is a nifty way to use PHP to send a data structure back on an AJAX request:

# THE PHP CODE:
function someAjaxHandler() {
    $table = myFrameworkGetPostRetrievalFunction('table');
    $id    = myFrameworkGetPostRetrievalFunction('id');
    $row = myFrameworkRowRetrievalFunction("customers",23);
    
    # This nifty PHP function encodes arrays and objects
    # into JSON, very cool
    echo json_encode($row);
}

This would be handled in the browser like so:

function someAjaxResponseHandler() {
    if (this.readyState != 4) return;
    try {
        eval( 'window.requestData ='+this.responseText);
    }
    catch(e) {
        alert("The server response was not parsable JSON!");
        return;
    }
}

Synchronous AJAX and JSON: S-JSON

It is pretty safe to say that the asynchronous nature of AJAX is a powerful part of its appeal. The request is sent and the browser remains responsive to the user until the request comes back. This is especially powerful for fetching things in the background while the user works.

However, in database applications sometimes it is the Right Thing for the browser to stop while fetching data. If a user clicks on [SAVE] on a CRUD screen to save some changes, we actually want the browser to wait until the server tells them that it all went ok (or not). You can do this by setting a flag on your call. I have found this a very powerful approach to writing desktop-in-browser applications:

function JSON(url) {
    // Create an object
    var browser = navigator.appName;
    if(browser == "Microsoft Internet Explorer"){
        var http = new ActiveXObject("Microsoft.XMLHTTP");
    }
    else {
        var http = new XMLHttpRequest();
    }

    // The trick is to pass "false" as the third parameter,
    // which says to not go asynchronously.

    http.open('POST' , url, false);
    http.send(null);
    
    // Execution now halts, waiting for the complete
    // return value

    // Once execution resumes, we can capture the
    // JSON string sent back by the server and do anything
    // we want with it
    try {
        eval( 'window.requestData ='+http.responseText);
    }
    catch(e) {
        alert("The server response was not parsable JSON!");
        return;
    }

    // Processing of the result occurs here...  
}

jQuery and Friends

Nowadays we have a growing list of very powerful Javascript libraries available. Some of them are very high level and some of them are low-level.

One library I will mention by name as being very useful is jQuery. This library provides a wealth of extremely simple and powerful abilities for finding and manipulating the HTML that is in your document. I highly recommend it.

Closing Thoughts

Any database programmer working in 2008 is either already required to use Javascript or may find himself facing it soon. Javascript is very flexible and powerful, but is different from the languages we are used to for writing applications, like PHP, Foxpro, Delphi, VB and others.

Nevertheless, Javascript can do everything you need it to do, you just have to grasp the "javascript mentality" as it were. I have attempted this week in this essay to put into one place all of the facts and tricks that were not so obvious to me from reading books or simply taking a snippet of code and trying to modify it. I hope that you find it useful!

Next Essay: Sequencing Dependencies