Many tables in a database house what I will call temporal data. This data is related to the main objects of the database and changes over time. For example, in a database about people it includes: data about where a person lives, information about who a person works for, and what a person's name is. Each of these data may be different at different moments in time. In this modern age even a person's gender might change during their lifetime. It is necessary that temporal data be maintained as such, if a database is to model reality.
The places where people live shouldn't go away when a person moves; the companies that people work for don't go out of existence when the only person in the database who works for them, leaves them. If these places and companies exist in the real world, and are ever associated with the objects for which the database exists, they should be represented in the database. Even when they do cease to exist, the fact that at some time they did exist, should be reflected in a database. If these entities exist only once in the real world then they should exist only once in the database.
Consider the data stored about people: only a person's date of birth and date of death are static. Everything else about a person is temporal. Each person only requires an identifier and a date of birth! A person's names are temporal; at birth the person's parents usually give them names, but over a life-time the person's names may change. A name history is needed; a table storing the person's names for the duration of their time spent on this planet. Not only will this track legal changes of name but it may also be used for aliases. Each name-history entry will have to include a start date and optionally, a stop date. Again, we are trying to model reality – and people's names do change. People's names are also ordered and in some cultures they take a large number of names.
If your database is conscientiously updated all the time, and doesn't have a name history, then how will you find that undergraduate named Maxine Smythe who was in the class of 1972? She has had two husbands since you were class-mates, is now single, and has legally changed her name to something quite different. Keep your database up to date, but don't throw away the history. These temporal data can be very valuable.
The excuse used by most database designers is that for all practical purposes the data in their database may be considered static. I have yet to see one instance of a database, that has a lifespan of more than a few weeks, for which this is true! There is very little static data in most databases. Most of the data stored in most databases is temporal data.
2012-04-14
2012-04-11
Domain tables
How should City Names, State Names and Postal Codes be represented in a database being built for the USA? Let’s assume that we have a table representing the zip codes comprised of just zip-code, state, and city. The zip-code has all the right properties to be a primary key (but must be treated as text because some start with a zero). The two character state abbreviation should suffice to identify a state. There are fewer than 4,000 zip codes in any 1 state and no state has more than 200 different city names. Large numbers of the zip codes will have the same city name. In reality each city (or rather, city name) should exist only once. For this reason the city names should be removed from the table and should be stored in a table of their own. This new table has a unique property, it serves simply to identify which city name from among many city names is intended. This table defines a domain, the entire set of city names that might be used in zip codes. The primary key for this domain table (as I'll call such tables) is simply an integer and the set of primary keys is simply an index set viz. {1, 2, 3, 4, 5, … n}. Similarly, the state names can be stored in a domain table where the primary key is the two-character abbreviation for the state and the full state name is the other value. A third domain table that is made up of an index set primary key and the county names should be included for completeness. There are two kinds of domain table; those that are not user-extensible and those that are. These three domain tables need not be user-extensible.
Many states have cities with identical city names: for example, 20 states have a city called Jackson and 12 states have a city named Alexandria. By eliminating the duplicates in the domain table, the domain table will become much smaller and much more readily accessible. If a city name is found to be wrong then there are two possible cases: either it is indeed misspelled or two cities have phonetically similar names with different spellings. (An interesting case can be found in county names—Allegany in NY and MD, Alleghany in VA and NC, and Allegheny in PA.) In either case fixing the problem is simple, and once fixed, applies to all the uses of those city names in the database. The potential for bad data arises if the city name is stored in each row of a table. (Remember, our goal is to only have a single representation of everything; that includes cities' names and counties' names.)
Defining a view consistent with the needs of database programmers will make it simple for them to access the database. This entire database for the USA, including all indices, is less than 10 MB and the same tables may be plugged into any larger database. When a database is constructed like this it does truly represent reality and is not straight-jacketed. Programmers and users need never be aware of the underlying complexity. Below is a schema diagram of these tables (including some additional fields and a couple of views).
The referential integrity of this sub-schema is ensured by the three foreign keys associated with the zipcode table. They are all many-to-one relationships that will allow the domain contents to be shared by multiple zipcode rows. Each domain table has a specific context and need not be user-extensible. When a new state, county or city is created the database administrator can add the data.
The integrity of this small part of the database is assured and there will be no need for any user to alter any of the data in it. All entries in the domain tables should be case sensitive and should use both uppercase and lowercase letters as needed. A canonical form for entries into all fields in all tables should be established and enforced. The two views both include the city state and zip code; one (v_citystzip) uses the abbreviated state name while the other uses the complete state name.
Many states have cities with identical city names: for example, 20 states have a city called Jackson and 12 states have a city named Alexandria. By eliminating the duplicates in the domain table, the domain table will become much smaller and much more readily accessible. If a city name is found to be wrong then there are two possible cases: either it is indeed misspelled or two cities have phonetically similar names with different spellings. (An interesting case can be found in county names—Allegany in NY and MD, Alleghany in VA and NC, and Allegheny in PA.) In either case fixing the problem is simple, and once fixed, applies to all the uses of those city names in the database. The potential for bad data arises if the city name is stored in each row of a table. (Remember, our goal is to only have a single representation of everything; that includes cities' names and counties' names.)
Defining a view consistent with the needs of database programmers will make it simple for them to access the database. This entire database for the USA, including all indices, is less than 10 MB and the same tables may be plugged into any larger database. When a database is constructed like this it does truly represent reality and is not straight-jacketed. Programmers and users need never be aware of the underlying complexity. Below is a schema diagram of these tables (including some additional fields and a couple of views).
The referential integrity of this sub-schema is ensured by the three foreign keys associated with the zipcode table. They are all many-to-one relationships that will allow the domain contents to be shared by multiple zipcode rows. Each domain table has a specific context and need not be user-extensible. When a new state, county or city is created the database administrator can add the data.
The integrity of this small part of the database is assured and there will be no need for any user to alter any of the data in it. All entries in the domain tables should be case sensitive and should use both uppercase and lowercase letters as needed. A canonical form for entries into all fields in all tables should be established and enforced. The two views both include the city state and zip code; one (v_citystzip) uses the abbreviated state name while the other uses the complete state name.
2012-04-09
Why make your data live in a straight jacket?
Database designers have spent the past fifty years designing straight jackets for their data. I find this puzzling since designing a database to reflect the reality of a situation seems so much simpler. I will explain what I mean as we examine different snippets of databases. Most contemporary databases are confined to straight-jackets similar to the punched-card data record. The data record concept has been perpetuated by COBOL and other fixed-length, fixed field, data representations. I will discuss concepts that allow the real-world to be modeled.
There are many advantages to modeling reality. For one thing, relational database normalization is very nearly automatic. Having entities that exist once in the real-world, also exist only once in a database, ensures that bad data will seldom be stored in that database. (If erroneous data does slip in, it is very quickly found. As a corollary, the incorrectly entered data is quickly corrected.) Entire subsets of a schema may be reused in other databases because it is reality that’s being modeled.
When asked to illustrate what I mean by a real-world model, it is often sufficient to make a simple query in the context of an existing database. I ask to find all the different ways in which some specific entity is represented. In one university alumnus database I simply asked for all the unique, (or in SQL parlance distinct) City/State combinations in alumni’s home addresses with a specific postal code. The result was horrific! The query yielded more than 600 City/State combinations, only one of which was correct. This is the result of allowing each user to submit (or enter) this data. No database user should ever be asked to enter that sort of data!
When the data environment is correctly represented, data entry becomes a process of selecting from sets of alternatives. For instance, in the United States the postal codes partition (in a mathematical sense) the country. This means that once the postal code is known there is no reason to ask the user to supply the city name or the state name. Feedback to the user, in the form of a simple statement, is all that is needed to ensure that the correct postal code has been entered. For example; if the postal code is solicited and you enter 55604 when you meant to enter 55406, then popping Hovland, Minnesota (which has zip code 55604) up on the screen adjacent to the zip code entry is enough feedback to alert the user to correcting the postal code. If what the user was expecting was Minneapolis, Minnesota he/she would look at, and correct their postal code entry. (In an orally driven system it could be phrased as a question - Is that Hovland, Minnesota? When you respond No! the system would ask for the postal code again.)
Unfortunately there are a few postal codes in the United States that straddle state boundaries. When one of these is encountered disambiguation will be required. See Wikipedia:
Fortunately there are very few instances where ZIP code areas cross state boundaries.
There are many advantages to modeling reality. For one thing, relational database normalization is very nearly automatic. Having entities that exist once in the real-world, also exist only once in a database, ensures that bad data will seldom be stored in that database. (If erroneous data does slip in, it is very quickly found. As a corollary, the incorrectly entered data is quickly corrected.) Entire subsets of a schema may be reused in other databases because it is reality that’s being modeled.
When asked to illustrate what I mean by a real-world model, it is often sufficient to make a simple query in the context of an existing database. I ask to find all the different ways in which some specific entity is represented. In one university alumnus database I simply asked for all the unique, (or in SQL parlance distinct) City/State combinations in alumni’s home addresses with a specific postal code. The result was horrific! The query yielded more than 600 City/State combinations, only one of which was correct. This is the result of allowing each user to submit (or enter) this data. No database user should ever be asked to enter that sort of data!
When the data environment is correctly represented, data entry becomes a process of selecting from sets of alternatives. For instance, in the United States the postal codes partition (in a mathematical sense) the country. This means that once the postal code is known there is no reason to ask the user to supply the city name or the state name. Feedback to the user, in the form of a simple statement, is all that is needed to ensure that the correct postal code has been entered. For example; if the postal code is solicited and you enter 55604 when you meant to enter 55406, then popping Hovland, Minnesota (which has zip code 55604) up on the screen adjacent to the zip code entry is enough feedback to alert the user to correcting the postal code. If what the user was expecting was Minneapolis, Minnesota he/she would look at, and correct their postal code entry. (In an orally driven system it could be phrased as a question - Is that Hovland, Minnesota? When you respond No! the system would ask for the postal code again.)
Unfortunately there are a few postal codes in the United States that straddle state boundaries. When one of these is encountered disambiguation will be required. See Wikipedia:
Because ZIP codes are intended for efficient postal delivery, there are unusual cases where a ZIP code crosses state boundaries, such as a military facility spanning multiple states or remote areas of one state most easily serviced from an adjacent state. For example ZIP code 42223 spans Christian KY and Montgomery TN, and ZIP code 97635 spans Lake OR and Modoc CA.
Fortunately there are very few instances where ZIP code areas cross state boundaries.
2012-03-24
Free at last!
The punched-card was restrictive in many ways: there were only codes for letters, digits and a small collection of special characters. No provision was made for both upper and lower case letters and a very few codes were designated for control characters. Each of the computer manufacturers introduced their own version of the cards to accommodate their code needs.
The American Standards Association’s (ASA) X3.2 subcommittee published the first version of the ASCII 8-bit code-set in 1963. The ASCII code-set was an 8-bit character encoding that eliminated most of the shortcomings of earlier code-sets. The ASA had created an earlier 7-bit code-set which included four separator codes. When IBM launched its System 360 it also introduced the EBCDIC encoding for punched-cards, which included the separator control codes introduced in the ASCII 7-bit code-set. In 1968 President Johnson mandated that all government computers would use ASCII, so IBM dropped their many-flavored EBCDIC and embraced the ASCII 8-bit code-set for System 370.
ASCII has since evolved to UTF-8, UTF-16 and UTF-32. Bigger and bigger code-sets that embrace all of mankind’s various alphabets and symbols. Code-sets went from 5-bits to 32-bits in 50 years. A 32-bit code-set allows for 4,294,967,296 different characters! (I don’t know anyone who uses UTF-32. Most programming is done using UTF-8.) The only reason that I even discuss this issue is because ASCII introduced the four very important control characters; the hierarchical separators. Quoting Wikipedia:
I decided to use these separators to free IT records from their straight jackets. I devised a scheme for using these control characters to allow variable length fields and unrestrained nesting of dependent data. The paper that I wrote about my scheme may be found here (it was presented at the ACM SICFIDET Workshop in Houston Texas in 1970). Unfortunately, I have found it impossible to persuade anyone to employ this technique. I am aware of only two implementations of the use of these concepts. Both were in systems that I developed. (Yes – I’ve been worrying this problem for a long time.)
ASCII has since evolved to UTF-8, UTF-16 and UTF-32. Bigger and bigger code-sets that embrace all of mankind’s various alphabets and symbols. Code-sets went from 5-bits to 32-bits in 50 years. A 32-bit code-set allows for 4,294,967,296 different characters! (I don’t know anyone who uses UTF-32. Most programming is done using UTF-8.) The only reason that I even discuss this issue is because ASCII introduced the four very important control characters; the hierarchical separators. Quoting Wikipedia:
Data structuring. The separators (File, Group, Record, and Unit: FS, GS, RS and US: 1C, 1D, 1E and 1F, hexadecimal) were made to structure data, usually on a tape, in order to simulate punched cards. End of medium (EM) warns that the tape (or other recording medium) is ending. While many systems use CR/LF and TAB for structuring data, it is possible to encounter the separator control characters in data that needs to be structured. The separator control characters are not overloaded; there is no general use of them except to separate data into structured groupings. Their numeric values are contiguous with the space character (20 hexadecimal) which can be considered a member of the group, as a word separator.
I decided to use these separators to free IT records from their straight jackets. I devised a scheme for using these control characters to allow variable length fields and unrestrained nesting of dependent data. The paper that I wrote about my scheme may be found here (it was presented at the ACM SICFIDET Workshop in Houston Texas in 1970). Unfortunately, I have found it impossible to persuade anyone to employ this technique. I am aware of only two implementations of the use of these concepts. Both were in systems that I developed. (Yes – I’ve been worrying this problem for a long time.)
The tyranny of the punched-card
In the early eighteenth century, perforated paper rolls were used to control looms in France. Basile Bouchon and Jean-Baptiste Falcon introduced punched-cards as a more robust and reliable method of controlling the looms. At the start of the nineteenth century, Joseph Marie Jacquard adopted and adapted their ideas for his looms. In 1832, a Russian homeopath, Semen Korsakov, use punched-cards to store information. His primary interest was to store information and then to search for similarities. Korsakov also invented a number of devices for comparing the data in his punched-cards.
Herman Hollerith developed a punched-card technology for the 1890 US Census. His company, the Tabulating Machine Company, started in 1896, later became IBM. James Powers, a former Census Bureau maintenance man for the Hollerith machines, introduced new devices that included a number of significant improvements. These new devices were marketed by Powers-Samas in Britain and France.
These first punched-cards were used primarily for storing data. Tabulators and sorters were used for accounting and conducting surveys. For IBM, punched-cards were to their equipment, what razor blades were to Gillette or Schick. In Endicott, NY, IBM printed, cut and stacked more than 5 million cards every day (generating a not-insignificant revenue—and their 'razors' were not inexpensive).
There are a fixed number of columns in a punched-card. Adjacent columns are assigned to fields; each field is assigned to different data in the database. A code, representing a letter, a number or a control, is punched into each column. The primary concept is that each card contain one record and that all the cards in a database have an identical layout. This was the first IT straight jacket. Everything needed to represent a single entity had to be contained in a single card (and later, in multiple cards)! Numerous clever schemes were invented to squeeze more data onto the cards. The first cards had quite a limited capacity, but over time the cards got bigger and bigger and the phrase 'Do not fold, spindle or mutilate,' became part of the modern psyche. When magnetic tape was introduced the size of the record went ballistic!
Instead of rethinking the way in which data was stored, magnetic tape simply became a collection of very big punched-cards; a larger straight jacket. More stuff could be squeezed into each record but it was simply a mindless extension of the punched-card. The programming language COBOL, that perpetuated this mistake, was developed. It was compatibility with the punched-card milieu that drove the effort. COBOL records were simply punched-card layouts that could become very complex. There were two major problems: the length of each field was fixed, and subordinate fields or groups of fields had to have a fixed number of occurrences. This resulted in some people’s long surnames being truncated, and employees who could have no more than, say eight, dependents. This also meant that a large number of columns in an individual record would go unused.
One of the major shortcomings of COBOL was that the external representation of the records was determined by the individual computer manufacturer. For example, IBM introduced slack bytes, a mechanism that ensured that the data would align itself correctly into their System 360 machine architecture. This meant that unused data would be inserted into records to avoid having to align the data with their word (32-bit) and double-word (64-bit) boundaries after reading it into memory. It also meant that another manufacturer could not read data written on an IBM computer without being cognizant of these slack bytes. Had the CODASYL committee explicitly controlled these external representations, it would have made it much easier to transfer data from one computer site to another.
These first punched-cards were used primarily for storing data. Tabulators and sorters were used for accounting and conducting surveys. For IBM, punched-cards were to their equipment, what razor blades were to Gillette or Schick. In Endicott, NY, IBM printed, cut and stacked more than 5 million cards every day (generating a not-insignificant revenue—and their 'razors' were not inexpensive).
There are a fixed number of columns in a punched-card. Adjacent columns are assigned to fields; each field is assigned to different data in the database. A code, representing a letter, a number or a control, is punched into each column. The primary concept is that each card contain one record and that all the cards in a database have an identical layout. This was the first IT straight jacket. Everything needed to represent a single entity had to be contained in a single card (and later, in multiple cards)! Numerous clever schemes were invented to squeeze more data onto the cards. The first cards had quite a limited capacity, but over time the cards got bigger and bigger and the phrase 'Do not fold, spindle or mutilate,' became part of the modern psyche. When magnetic tape was introduced the size of the record went ballistic!
Instead of rethinking the way in which data was stored, magnetic tape simply became a collection of very big punched-cards; a larger straight jacket. More stuff could be squeezed into each record but it was simply a mindless extension of the punched-card. The programming language COBOL, that perpetuated this mistake, was developed. It was compatibility with the punched-card milieu that drove the effort. COBOL records were simply punched-card layouts that could become very complex. There were two major problems: the length of each field was fixed, and subordinate fields or groups of fields had to have a fixed number of occurrences. This resulted in some people’s long surnames being truncated, and employees who could have no more than, say eight, dependents. This also meant that a large number of columns in an individual record would go unused.
One of the major shortcomings of COBOL was that the external representation of the records was determined by the individual computer manufacturer. For example, IBM introduced slack bytes, a mechanism that ensured that the data would align itself correctly into their System 360 machine architecture. This meant that unused data would be inserted into records to avoid having to align the data with their word (32-bit) and double-word (64-bit) boundaries after reading it into memory. It also meant that another manufacturer could not read data written on an IBM computer without being cognizant of these slack bytes. Had the CODASYL committee explicitly controlled these external representations, it would have made it much easier to transfer data from one computer site to another.
2012-03-23
Designing databases
Databases should be designed to model the real world. Most Relational Database Management Systems (RDBMS) database designs don't even follow the rudimentary dictates of proper normalization and many software packages allow databases with no referential integrity constraints to be built. If a datum exists only once in the real-world then that datum should only be represented once in a database. Regardless of how complex access to, or maintenance of that datum may become, only a single instance of the datum should exist in the database! (Access to, and maintenance of the datum will actually become simpler.)
The shortcomings of RDBMSs and how they are being implemented are presently being explored by Date and Darwen in The Third Manifesto, and by Terry Halpin who takes a different approach to database modeling with his Object Role Modeling. Once again I will quote from George Santayana who has said, “Those who do not learn from history are doomed to repeat it.” Indeed, it really is history that has hobbled database design. Some of this history will be discussed and the considerations that result in the modeling of the real world, without altering it, will be dealt with.
The shortcomings of RDBMSs and how they are being implemented are presently being explored by Date and Darwen in The Third Manifesto, and by Terry Halpin who takes a different approach to database modeling with his Object Role Modeling. Once again I will quote from George Santayana who has said, “Those who do not learn from history are doomed to repeat it.” Indeed, it really is history that has hobbled database design. Some of this history will be discussed and the considerations that result in the modeling of the real world, without altering it, will be dealt with.
2012-03-22
Two more tales
The COBOL compiler mystery
A major computer manufacturer invited me to present my decision table methodology to their software developers. After the presentation a group asked if I would demonstrate how it worked by looking at a very specific problem. They explained that there was a persistent problem in their COBOL compiler. I agreed to try to solve the problem.
We spent a few days constructing decision tables from the language specification. While constructing one of the tables, two groups of programmers disagreed about how a particular part of the specification should be interpreted. Each group had a different understanding of the intent of the specification.
I mediated the lengthy discussion that ensued. It was obvious that this ambiguity was the source of their problem. We looked at the pros and cons of each interpretation and then voted on which one to adopt. Once this decision had been made, the group, who had had the counter-interpretation, went back to their offices and rewrote their code. The rebuilt compiler no longer had the problem. (This all happened a few years after the compiler had been released to customers.)
The Jims and their epiphanies
Two colleagues, both named Jim, and I were working on a new file storage mechanism for a mainframe computer. (Our goal was to pack and unpack data into strings of contiguous bits. The target was to gain at least a tenfold increase in data density without incurring a large penalty in access speed.) Neither Jim was interested in using decision tables. They estimated that the task could be accomplished in about two weeks.
While they coded their solution I drew the decision tables and prepared a test with which to test their code. About 10 days later they claimed that the code was ready to be tested. I tested their program using the test I'd prepared and it failed in many different ways. I showed them exactly where it was failing. They felt that they could take care of the problems in a couple of days. A week later the code was still failing a number of tests. At this point I shared the decision tables with them, explained how they worked, and we coded the solution from the decision tables. The resulting code was much smaller than their original code and worked correctly for all the test cases.
All three of us left the company within the next three months. One of the Jims repaired to California to work on flat-bed plotters; the other went to the NIH to work with lab-computers; and I went to Minnesota to work on machine-independent operating systems.
The California Jim called me late one evening about six months later. He had been wrestling with a particularly difficult problem. Out of frustration he decided to try a decision table. His experience convinced him that decision tables really worked. He became a decision tables devotee and has used them ever since.
The other Jim called me a few months after his namesake. He told me about the problem he had been having interfacing a lab instrument to a computer, and how he had solved his problem by using a decision table. He too became a decision table devotee.
Neither of my friends, both very capable programmers, had liked the idea of using decision tables to solve programming problems. After the two incidents described above both started using decision tables in most of their work.
Video Presentation
I have prepared a YouTube presentation entitled 'A Disciplined Approach to Solving Problems' that walks through a theoretical problem space and then through a real problem space. This is available here. It is easy to follow and, should you care to view it, I urge you to persist and watch all four parts.
A major computer manufacturer invited me to present my decision table methodology to their software developers. After the presentation a group asked if I would demonstrate how it worked by looking at a very specific problem. They explained that there was a persistent problem in their COBOL compiler. I agreed to try to solve the problem.
We spent a few days constructing decision tables from the language specification. While constructing one of the tables, two groups of programmers disagreed about how a particular part of the specification should be interpreted. Each group had a different understanding of the intent of the specification.
I mediated the lengthy discussion that ensued. It was obvious that this ambiguity was the source of their problem. We looked at the pros and cons of each interpretation and then voted on which one to adopt. Once this decision had been made, the group, who had had the counter-interpretation, went back to their offices and rewrote their code. The rebuilt compiler no longer had the problem. (This all happened a few years after the compiler had been released to customers.)
The Jims and their epiphanies
Two colleagues, both named Jim, and I were working on a new file storage mechanism for a mainframe computer. (Our goal was to pack and unpack data into strings of contiguous bits. The target was to gain at least a tenfold increase in data density without incurring a large penalty in access speed.) Neither Jim was interested in using decision tables. They estimated that the task could be accomplished in about two weeks.
While they coded their solution I drew the decision tables and prepared a test with which to test their code. About 10 days later they claimed that the code was ready to be tested. I tested their program using the test I'd prepared and it failed in many different ways. I showed them exactly where it was failing. They felt that they could take care of the problems in a couple of days. A week later the code was still failing a number of tests. At this point I shared the decision tables with them, explained how they worked, and we coded the solution from the decision tables. The resulting code was much smaller than their original code and worked correctly for all the test cases.
All three of us left the company within the next three months. One of the Jims repaired to California to work on flat-bed plotters; the other went to the NIH to work with lab-computers; and I went to Minnesota to work on machine-independent operating systems.
The California Jim called me late one evening about six months later. He had been wrestling with a particularly difficult problem. Out of frustration he decided to try a decision table. His experience convinced him that decision tables really worked. He became a decision tables devotee and has used them ever since.
The other Jim called me a few months after his namesake. He told me about the problem he had been having interfacing a lab instrument to a computer, and how he had solved his problem by using a decision table. He too became a decision table devotee.
Neither of my friends, both very capable programmers, had liked the idea of using decision tables to solve programming problems. After the two incidents described above both started using decision tables in most of their work.
Video Presentation
I have prepared a YouTube presentation entitled 'A Disciplined Approach to Solving Problems' that walks through a theoretical problem space and then through a real problem space. This is available here. It is easy to follow and, should you care to view it, I urge you to persist and watch all four parts.
2012-03-18
Serendipitous trip to Ann Arbor
I wrote a paper about my database management concepts which I presented in Ann Arbor, Michigan, at the ACM SIGMOD Workshop on Data Description, Access and Control. It was May of 1974 and I had just left CDC and was looking for a new home. In my briefcase I had a handwritten paper describing my decision table methodology.
On the morning after I made my presentation I had breakfast with Jane Jodeit (from Software AG) and Jonas Rabin (from Western Electric). Jane told us something about ADABAS, the product she was supporting in the USA, and Jonas told us about his work with the Decision Table Task Group (DTTG) of CODASYL. I had the handwritten working paper about my decision table methodology copied and gave each of them a copy.
Jane asked if I would be available to meet her CEO, John Maguire, to whom she had spoken earlier that morning. At her behest he had agreed to fly to Ann Arbor to meet me. I met him that afternoon and by the end of the day was an employee of Software AG.
Several months later I received a phone call from Jonas Rabin. He invited me to present the paper, I’d given him a copy of in Ann Arbor, to the DTTG in Chicago the following day. I flew to Chicago, met the DTTG members, and presented my paper. They asked if I would be interested in becoming a member of the task group. I accepted their invitation and stayed in Chicago for the rest of that week.
There were about 20 people in the DTTG. They were divided into smaller groups each charged with the responsibility of dealing with a particular task. I was assigned to the group that was writing about development methodology.
I hosted a meeting for the DTTG in Saint Paul a few years later. Each sub-group made presentations to the entire DTTG. This was the first time that I heard how decision tables were going to be described mathematically. The description lacked substance and was full of holes. I was probably the most vocal critic and felt a little uncomfortable.
When our meeting ended, one of the members, Lewis Reinwald, had to wait for his daughter to arrive. She was going to drive him back to Washington, DC. He and I sat on a terrace discussing some of the issues that had been raised. He mentioned the way I had torn the mathematics apart and asked how I would characterize decision tables mathematically. I scribbled some of my ideas on paper napkins as we explored the possibilities. A set-theoretic approach seemed the best to me. I fleshed out some of my ideas about being able to prove completeness, and the consequent affect it would have on testing. Many beers and hours later Lewis’s daughter arrived. He asked me to gather up the paper napkins and put them into some sort of order, and took the bundle with him to Washington.
About 6 weeks later I received a parcel from Lewis. He requested that I review the document he had enclosed and asked if this is what I had had in mind. I was amazed, he had threshed out a very meaningful description of decision tables along the lines of our discussion. I made a few changes and suggested that we send it to all the DTTG members as a proposed formal characterization of decision tables. At our next meeting the DTTG adopted our proposal. The CODASYL Report, entitled A Modern Appraisal of Decision Tables, was published by the ACM in 1982.
Lewis had developed some very interesting ways of extending decision tables which didn’t fit my model. He called me a purist when I couldn’t fit his extensions into the model. We never did resolve this difference.
On the morning after I made my presentation I had breakfast with Jane Jodeit (from Software AG) and Jonas Rabin (from Western Electric). Jane told us something about ADABAS, the product she was supporting in the USA, and Jonas told us about his work with the Decision Table Task Group (DTTG) of CODASYL. I had the handwritten working paper about my decision table methodology copied and gave each of them a copy.
Jane asked if I would be available to meet her CEO, John Maguire, to whom she had spoken earlier that morning. At her behest he had agreed to fly to Ann Arbor to meet me. I met him that afternoon and by the end of the day was an employee of Software AG.
Several months later I received a phone call from Jonas Rabin. He invited me to present the paper, I’d given him a copy of in Ann Arbor, to the DTTG in Chicago the following day. I flew to Chicago, met the DTTG members, and presented my paper. They asked if I would be interested in becoming a member of the task group. I accepted their invitation and stayed in Chicago for the rest of that week.
There were about 20 people in the DTTG. They were divided into smaller groups each charged with the responsibility of dealing with a particular task. I was assigned to the group that was writing about development methodology.
I hosted a meeting for the DTTG in Saint Paul a few years later. Each sub-group made presentations to the entire DTTG. This was the first time that I heard how decision tables were going to be described mathematically. The description lacked substance and was full of holes. I was probably the most vocal critic and felt a little uncomfortable.
When our meeting ended, one of the members, Lewis Reinwald, had to wait for his daughter to arrive. She was going to drive him back to Washington, DC. He and I sat on a terrace discussing some of the issues that had been raised. He mentioned the way I had torn the mathematics apart and asked how I would characterize decision tables mathematically. I scribbled some of my ideas on paper napkins as we explored the possibilities. A set-theoretic approach seemed the best to me. I fleshed out some of my ideas about being able to prove completeness, and the consequent affect it would have on testing. Many beers and hours later Lewis’s daughter arrived. He asked me to gather up the paper napkins and put them into some sort of order, and took the bundle with him to Washington.
About 6 weeks later I received a parcel from Lewis. He requested that I review the document he had enclosed and asked if this is what I had had in mind. I was amazed, he had threshed out a very meaningful description of decision tables along the lines of our discussion. I made a few changes and suggested that we send it to all the DTTG members as a proposed formal characterization of decision tables. At our next meeting the DTTG adopted our proposal. The CODASYL Report, entitled A Modern Appraisal of Decision Tables, was published by the ACM in 1982.
Lewis had developed some very interesting ways of extending decision tables which didn’t fit my model. He called me a purist when I couldn’t fit his extensions into the model. We never did resolve this difference.
2012-03-17
The methodology works!
Years earlier, while working in a group dedicated to unraveling the complexities of operating systems, I had worked with Henry Stambler, a former IBM-er who had been recruited by CDC. Henry was intrigued by my database management concepts.
In 1967, CDC had provided the hardware for a very innovative project at Case Western Reserve University; Dr. Larry Weed’s Problem Oriented Medical Information Systems (PROMIS) project. They were using touch screen terminals (Digiscribe) to enter and retrieve medical records at patients’ bedsides. The PROMIS project moved, lock, stock and barrel, to the University of Vermont in Burlington, Vermont in 1969. Henry Stambler left CDC a few years later and joined the PROMIS project, where he designed their file system. The history of PROMIS is available here.
Henry Stambler persuaded the PROMIS project management to invite me in to tell them about my database management concepts. I went to visit the project for a couple of weeks. They liked my concepts and invited me to join them.
While I was in Vermont I also made some presentations on my problem-solving methodology. Everyone on the project attended. The software people rejected the ideas out of hand, they felt they didn’t need that sort of mothering. Ironically, it was the hardware engineers that wanted to try it. So I spent a few days with them using decision tables to solve some hardware design problems. They took to the methodology like the proverbial ducks to water.
The software group had been working together for some years and had a huge investment in their solution. I realized that changing horses in this rapidly moving stream wouldn’t work, so I thanked them for the offer to join them but did not accept the offer. (I went home to Minnesota with a huge jug of maple syrup.)
Somewhere along the line the hardware engineers must have persuaded the software people to try decision tables. From page 32 of the history referenced above:
The report referenced above was written nearly 10 years after my visit to the PROMIS project. I had no idea that the software group had embraced decision tables so enthusiastically.
In 1967, CDC had provided the hardware for a very innovative project at Case Western Reserve University; Dr. Larry Weed’s Problem Oriented Medical Information Systems (PROMIS) project. They were using touch screen terminals (Digiscribe) to enter and retrieve medical records at patients’ bedsides. The PROMIS project moved, lock, stock and barrel, to the University of Vermont in Burlington, Vermont in 1969. Henry Stambler left CDC a few years later and joined the PROMIS project, where he designed their file system. The history of PROMIS is available here.
Henry Stambler persuaded the PROMIS project management to invite me in to tell them about my database management concepts. I went to visit the project for a couple of weeks. They liked my concepts and invited me to join them.
While I was in Vermont I also made some presentations on my problem-solving methodology. Everyone on the project attended. The software people rejected the ideas out of hand, they felt they didn’t need that sort of mothering. Ironically, it was the hardware engineers that wanted to try it. So I spent a few days with them using decision tables to solve some hardware design problems. They took to the methodology like the proverbial ducks to water.
The software group had been working together for some years and had a huge investment in their solution. I realized that changing horses in this rapidly moving stream wouldn’t work, so I thanked them for the offer to join them but did not accept the offer. (I went home to Minnesota with a huge jug of maple syrup.)
Somewhere along the line the hardware engineers must have persuaded the software people to try decision tables. From page 32 of the history referenced above:
…Henry Beitz, a CDC consultant, convinced us that an unlimited entry decision table could be used as the basis for demonstrating an understanding of a problem and also as the fundamental design document. Decision tables were used to design and test the interface among hardware and software modules.
The run-time environment developed to support PPL (described in the next section) was defined in 17 decision tables and 78 rules. The definition of the polled multi-drop protocol to connect the high-speed terminals to the CPU was a set of 12 decision tables with a total of 77 rules. The protocol was used by Varian Data Machines, by MEGADATA, and by PROMIS Laboratory. When the hardware was delivered and the terminals were connected, the system operated correctly the first time it was tried (my emphasis).
The report referenced above was written nearly 10 years after my visit to the PROMIS project. I had no idea that the software group had embraced decision tables so enthusiastically.
2012-03-14
Putting the methodology’s feet to the fire
In 1972 I moved from the Advanced Research Laboratory, where CDC was developing the STAR-100 system, to the Scope Operating System group at CDC’s Arden Hills plant in Saint Paul. CDC wanted me to manage a group implementing part of their new operating system. Ray Nienberg, the General Manager, was willing to let me try my methods on one of the modules. They chose something that wasn’t really essential but that would be nice to have: a deadlock-preventing resource scheduler which would ensure that all jobs submitted for execution would run to completion without any resource deadlocks. The new operating system was to be released to users in 10 months.
I explained to the people in my group how we were going to implement our module. An analysis of precedent revealed that the problem had already been solved. Edsger Dijkstra called it the banker’s algorithm, and Wikipedia deals with it here. Not being one to reinvent the wheel, I simply implemented the banker’s algorithm for our operating environment resources. Decision tables were used to ensure that our implementation was robust.
Our group did not use one second of computer time during the first 6 months. We constructed and reviewed decision tables, refining them as we went. When we felt that all the rules (the meaningful combinations of alternatives of all the variables) had been dealt with we created an exhaustive testing mechanism to test our implementation. This suite of tests served as a regression test ensuring that when we fixed programming errors we didn’t break anything that had previously worked. The tests were designed to run until an expected outcome didn’t match a program outcome. If this happened we stopped the computer immediately and dumped out a complete map of the memory of the program. Each test situation was constructed mechanically from the decision tables. The tests were exhaustive and tested every possible situation. Remember, we were running on what was then the world’s fastest computer, the CDC 7600 (since we didn’t use any floating point arithmetic we must have been running even faster than its 36 MFLOP capability). When completed, the entire test, which included thousands of rules, took less than 1 second to execute.
We turned our module over to Integration and Evaluation on the day we got right through to the end of the testing sequence. We had completed our task within 8 months, and were one of the few groups ready to release their module by the release date. Integration and Evaluation declared our module ready for release after a couple of weeks of testing. I asked to see the test that Integration and Evaluation had used to test our module. They had used a dedicated super-computer for 300 minutes to test our module. On examination we found that they had tested some situations hundreds of millions of times while many situations had not been tested at all. We walked them through our tables and our testing procedure, and they got very excited. They realized the value of what we were doing and immediately wanted to use a similar methodology for all testing. They weren’t able to sell it to project management.
After reviewing the progress of the entire project the company management decided to slip the release date by 3 months. By now everyone in our group had a very good feel for our solution. We revisited our tables and decided how we could change things. After we had discussed the improvements for a few weeks we went ahead, altered the tables, revised the tests, and implemented the improvements.
The most costly aspect of maintaining a complex system is support. Fixing the bugs and releasing them to the users is very expensive. Monthly meetings were held to see how the new operating system was doing following its release. Every module would have an outstanding number of known bugs. On average there would be about 20 bugs per module. The support programmers would fix them at about the same rate, but the number of outstanding bugs didn’t appear to go down. New bugs were being created at about the same rate as old ones were fixed. Our module was the exception; a couple of bugs were reported in the first two months and then the module remained stable for the life of that version of the operating system (a number of years). My group was disbanded and all its members were reassigned to other projects. The maintenance of our module was assigned to another support group. There was virtually no cost attributable to maintaining our deadlock-preventing resource scheduler for the life of the operating system.
I explained to the people in my group how we were going to implement our module. An analysis of precedent revealed that the problem had already been solved. Edsger Dijkstra called it the banker’s algorithm, and Wikipedia deals with it here. Not being one to reinvent the wheel, I simply implemented the banker’s algorithm for our operating environment resources. Decision tables were used to ensure that our implementation was robust.
Our group did not use one second of computer time during the first 6 months. We constructed and reviewed decision tables, refining them as we went. When we felt that all the rules (the meaningful combinations of alternatives of all the variables) had been dealt with we created an exhaustive testing mechanism to test our implementation. This suite of tests served as a regression test ensuring that when we fixed programming errors we didn’t break anything that had previously worked. The tests were designed to run until an expected outcome didn’t match a program outcome. If this happened we stopped the computer immediately and dumped out a complete map of the memory of the program. Each test situation was constructed mechanically from the decision tables. The tests were exhaustive and tested every possible situation. Remember, we were running on what was then the world’s fastest computer, the CDC 7600 (since we didn’t use any floating point arithmetic we must have been running even faster than its 36 MFLOP capability). When completed, the entire test, which included thousands of rules, took less than 1 second to execute.
We turned our module over to Integration and Evaluation on the day we got right through to the end of the testing sequence. We had completed our task within 8 months, and were one of the few groups ready to release their module by the release date. Integration and Evaluation declared our module ready for release after a couple of weeks of testing. I asked to see the test that Integration and Evaluation had used to test our module. They had used a dedicated super-computer for 300 minutes to test our module. On examination we found that they had tested some situations hundreds of millions of times while many situations had not been tested at all. We walked them through our tables and our testing procedure, and they got very excited. They realized the value of what we were doing and immediately wanted to use a similar methodology for all testing. They weren’t able to sell it to project management.
After reviewing the progress of the entire project the company management decided to slip the release date by 3 months. By now everyone in our group had a very good feel for our solution. We revisited our tables and decided how we could change things. After we had discussed the improvements for a few weeks we went ahead, altered the tables, revised the tests, and implemented the improvements.
The most costly aspect of maintaining a complex system is support. Fixing the bugs and releasing them to the users is very expensive. Monthly meetings were held to see how the new operating system was doing following its release. Every module would have an outstanding number of known bugs. On average there would be about 20 bugs per module. The support programmers would fix them at about the same rate, but the number of outstanding bugs didn’t appear to go down. New bugs were being created at about the same rate as old ones were fixed. Our module was the exception; a couple of bugs were reported in the first two months and then the module remained stable for the life of that version of the operating system (a number of years). My group was disbanded and all its members were reassigned to other projects. The maintenance of our module was assigned to another support group. There was virtually no cost attributable to maintaining our deadlock-preventing resource scheduler for the life of the operating system.
2012-03-09
Problem Solving
The solutions to complex problems are seldom robust. What exactly do I mean by that? Simply that the solutions are incomplete; there are no planned actions for many of the situations that may arise. Some
errors are simply that – errors. Most errors are errors of omission. One source of unanticipated errors is a difference in the interpretation of the requirements and another is an inconsistency in the implementation of the solution. To solve complex problems, methodical methods for exhaustively enumerating all the possible situations that may arise, are needed.
The problem space, i. e. the combination of every possible alternative for every variable that describes a possible or impossible situation with respect to the problem, needs to be defined. All erroneous and impossible situations must be identified and each must be handled as explicitly as any other situation. A seemingly ridiculous goal since a very large number of situations may be identified. Fortunately, decision table can be shown to represent such problem spaces succinctly. Decision tables are useful for solving all kinds of problems, not just those related to computer programming.
The origins of the decision table
Some form of decision table was first tried in the 1950s. But like flow-charts, they were simply a crutch that enabled early programmers to get some idea of how they were going to program the solution to a problem. Early decision tables were neither complete nor robust.
In the early 1970s IBM started using DECTAT, a decision table translator for PL/1 and COBOL. I couldn’t find anything in the tool that enforced completeness. None of the tables, that I looked at in IBM's documentation, was complete. (The reference manual is available from Google Books – AF37765).
In 1964 the late Tom Rozwadowski and I set out to solve a very complex problem. We had worked together as a team for 5 years; first at LEO Computers and then at Control Data Corporation (CDC). The task was to write drivers for some very special devices that our customer wanted to connect to a computer system that we had never seen. Although we were employed by the company that made the computer it was impossible to get any documentation about how to interface hardware to the system. In frustration we decided to analyze how all the interfaces, for external devices connected to the computer system, were programmed.
A few years earlier Tom and I had made a proposal to a government for the implementation of a national population register. We had used tables to analyze the requirements. We realized that similar tables, with a few extensions, would make it possible to analyze the device drivers in the new computer's operating system. By the time the hardware was delivered our drivers were ready. We installed our drivers, connected all the devices to the computer system, and tested the devices. All the devices operated correctly and we were able to control the devices using our installed drivers. The methodology proved to be very robust and we both continued using it from that time forward.
Neither of us was able to convince any of our colleagues to use our methods. We read everything we could find about decision tables but found that none of the methods were robust. We had planned to formalize the whole concept together but this wasn’t to be (Tom and his family died in a tragic accident in October 1970). How I completed this task will be revealed later.
The problem space, i. e. the combination of every possible alternative for every variable that describes a possible or impossible situation with respect to the problem, needs to be defined. All erroneous and impossible situations must be identified and each must be handled as explicitly as any other situation. A seemingly ridiculous goal since a very large number of situations may be identified. Fortunately, decision table can be shown to represent such problem spaces succinctly. Decision tables are useful for solving all kinds of problems, not just those related to computer programming.
The origins of the decision table
Some form of decision table was first tried in the 1950s. But like flow-charts, they were simply a crutch that enabled early programmers to get some idea of how they were going to program the solution to a problem. Early decision tables were neither complete nor robust.
In the early 1970s IBM started using DECTAT, a decision table translator for PL/1 and COBOL. I couldn’t find anything in the tool that enforced completeness. None of the tables, that I looked at in IBM's documentation, was complete. (The reference manual is available from Google Books – AF37765).
In 1964 the late Tom Rozwadowski and I set out to solve a very complex problem. We had worked together as a team for 5 years; first at LEO Computers and then at Control Data Corporation (CDC). The task was to write drivers for some very special devices that our customer wanted to connect to a computer system that we had never seen. Although we were employed by the company that made the computer it was impossible to get any documentation about how to interface hardware to the system. In frustration we decided to analyze how all the interfaces, for external devices connected to the computer system, were programmed.
A few years earlier Tom and I had made a proposal to a government for the implementation of a national population register. We had used tables to analyze the requirements. We realized that similar tables, with a few extensions, would make it possible to analyze the device drivers in the new computer's operating system. By the time the hardware was delivered our drivers were ready. We installed our drivers, connected all the devices to the computer system, and tested the devices. All the devices operated correctly and we were able to control the devices using our installed drivers. The methodology proved to be very robust and we both continued using it from that time forward.
Neither of us was able to convince any of our colleagues to use our methods. We read everything we could find about decision tables but found that none of the methods were robust. We had planned to formalize the whole concept together but this wasn’t to be (Tom and his family died in a tragic accident in October 1970). How I completed this task will be revealed later.
2012-02-26
Introduction
During the nearly 50 years that I’ve spent in the computer field, I’ve learned a thing or two. Making robust, maintenance-free, software is the achievement I’m proudest of. Another area that has kept me busy, is database design. Every time I fill out a form, respond to a questionnaire, or answer questions on the telephone, I wonder why some questions are being asked. You’ll be surprised at how much you can discern, about the design of the database behind the fields and questions. In this blog I will explore both issues and provide insights that might prove to be helpful.
For designing software my tool of choice is the decision table. I started using decision tables in the 1950s, refined them for a specific problem in the 1960s, and then helped formalize them in the 1970s. Decision tables, when used properly, can help you produce robust software. I used to draw decision tables by hand in pencil, but now I use the Prologa software developed at KU Leuven in Belgium. Prologa is freely available from this website. Dr. Jan Vanthienen and his colleagues have produced a viable tool that takes the effort out of drawing decision tables, and helps to identify where the problems in the tables are. Prologa also ensures that the problem is exhaustively explored. With a tool like Prologa it’s feasible that all software can be built robustly.
Regardless of which database product you choose to use, the design of the database schema is what is important. There are many database products available. Most are implementations of Ted Codd’s Relational Model. Recently some object-oriented database products have appeared. Just about any one of these pieces of software may be used to implement a database. How you define and lay your tables out, is much more important than the software tool you use. Database normalization and referential integrity are the two missing ingredients in most databases. I will explore what it is that makes a database a model of reality rather than a data straight jacket.
Why people are reluctant to change the way they do things has puzzled me for a long time. We adapt to our environments in totally illogical ways. As George Santayana said, “Habit is stronger than reason.” Regardless of how much solid evidence there is that programs and databases aren’t working optimally, we continue to employ exactly the same methods. Most people don’t even want to consider that there are other ways of tackling these tasks. I hope to persuade readers that paying attention to the details does make a difference.
These blogs will take the form of anecdotal accounts of real-world situations and how I dealt with them. There will also be snippets of biographical detail to give the developments a context. Each blog will address a single issue and will illustrate an important principle. The title of each blog will be simple and descriptive so that readers might quickly find what they’re looking for. The best reading order is the order in which the blogs are posted.
For designing software my tool of choice is the decision table. I started using decision tables in the 1950s, refined them for a specific problem in the 1960s, and then helped formalize them in the 1970s. Decision tables, when used properly, can help you produce robust software. I used to draw decision tables by hand in pencil, but now I use the Prologa software developed at KU Leuven in Belgium. Prologa is freely available from this website. Dr. Jan Vanthienen and his colleagues have produced a viable tool that takes the effort out of drawing decision tables, and helps to identify where the problems in the tables are. Prologa also ensures that the problem is exhaustively explored. With a tool like Prologa it’s feasible that all software can be built robustly.
Regardless of which database product you choose to use, the design of the database schema is what is important. There are many database products available. Most are implementations of Ted Codd’s Relational Model. Recently some object-oriented database products have appeared. Just about any one of these pieces of software may be used to implement a database. How you define and lay your tables out, is much more important than the software tool you use. Database normalization and referential integrity are the two missing ingredients in most databases. I will explore what it is that makes a database a model of reality rather than a data straight jacket.
Why people are reluctant to change the way they do things has puzzled me for a long time. We adapt to our environments in totally illogical ways. As George Santayana said, “Habit is stronger than reason.” Regardless of how much solid evidence there is that programs and databases aren’t working optimally, we continue to employ exactly the same methods. Most people don’t even want to consider that there are other ways of tackling these tasks. I hope to persuade readers that paying attention to the details does make a difference.
These blogs will take the form of anecdotal accounts of real-world situations and how I dealt with them. There will also be snippets of biographical detail to give the developments a context. Each blog will address a single issue and will illustrate an important principle. The title of each blog will be simple and descriptive so that readers might quickly find what they’re looking for. The best reading order is the order in which the blogs are posted.
Subscribe to:
Posts (Atom)