<\/a>Logical Data Model<\/h2>\nBachman also made another contribution to databases. His Bachman diagrams<\/a> were an early attempt at systematically building logical data models. Before that, we wrote file layouts using code sheets provided by IBM and ANSI X3.5 program flowcharts. Flowcharts are one of the worst ways to define programs because you’re not sure what’s flowing; sometimes it’s data and sometimes it’s control. That is why that particular standard expired decades ago.<\/p>\nThe Bachman diagrams are made up of boxes and arrows. In fact, there was a small-circulation newsletter for DBAs and systems analysts who worked with IDMS and other older mainframe database products entitled \u2018Boxes and Arrows\u2019 based on the appearance of Bachman diagrams.<\/p>\n
The main structuring concepts in this model are \u2018records\u2019 and \u2018sets\u2019. Records essentially follow the COBOL<\/a> definition ordered sequences of fields of different types: this allows complex internal structure such as repeating items and repeating groups. There are no virtual or computed fields. The set concept should not be confused with the mathematical set that used in an RDBMS. A CODASYL<\/a> set represents a one-to-many relationship between records: one owner, many members. Unlike a strictly hierarchical data model, a record can be a member of many different sets. But unlike the set concept from RDBMS, these guys are ordered (so they are not really sets) and the records within a set are also in a sequence!<\/p>\nRecords have a locator represented by a value known as a database key<\/strong>. Did you ever wonder where Sybase got the idea of the IDENTITY<\/strong> table property when they first implemented SQL? In IDMS, as in most other CODASYL implementations, the database key is directly related to the physical <\/em>address of the record on disk, without regard to any of the values in the record. In short, it\u2019s not relational. Database keys are then used as pointers to linked lists and trees. This means that the logical model and the physical implementation look a lot alike. Here\u2019s the trade-off with this approach; Database retrieval can be pretty efficient because it\u2019s really fast to traverse lists. But loading and restructuring these linked lists can be very<\/em> expensive. Also, if a linked list was broken, you needed special utility programs to try and rebuild them. It was not always possible to do these rebuilds. Finally, if you needed to access the data in a particular order, which was not how the sets or records are physically ordered, then you have the overhead of sorting.<\/p>\nFlavors of Pointers<\/h2>\n
Many SQL programmers have never worked with pointers. When I explained the nested set model to programmers in some of my classes, the older programmers have a real hard time with it because they want to build tree structures with pointer chains. This is why you will see an organizational chart done with (emp_id<\/strong>, boss_emp_id<\/strong>) pairs to model the head and tail of a pointer chain link. This was so much a part of the mindset at the start of RDBMS, that the Oracle sample database (\u2018Scott\/Tiger\u2019 is the nickname it\u2019s gotten over the decades because of the user and the password in it) is built on this adjacency list model.<\/p>\nHowever, younger programmers look at this approach in SQL and see it as a badly denormalized table. The same employee identifier appears in multiple places in the same table, in violation of First Normal Form (1NF). It requires very complex constraints to prevents cycles ensure that the hierarchy is a proper tree.<\/p>\n
The nested set model doesn\u2019t have the normal form violations and redundancy. New programmers who didn\u2019t grow up with assembly language and low-level machine constructs look at it and say \u201cOh, this is XML tags written in a different language!\u201d instead.<\/p>\n
Simple Linked List<\/h2>\n
When people on SQL forums refer to a \u2018link table\u2019, they are using the term that refers to pointer chains. The simplest possible list structure is a single linked list, which would look something like this<\/p>\n
![](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2018\/02\/word-image-37.png\")
<\/p>\n
You enter the chain at a node and either pull out the data attached to it or get the address of the next link in the chain. Eventually will follow the path down to a \u2018nil\u2019 node (not to be confused with the NULL<\/strong> in SQL). You\u2019ll notice that the structure allows you to move in only one direction.<\/p>\nThis limitation on traversal is not as bad as you might first think. If you been working with SQL Server for a few decades, you will remember that the cursors in the very early versions of the product also could only read forward. The reason for this was very simple; the early tape drives from which model of cursors was developed could only read in one direction! This was not just on small machines, but pretty much on all the mainframe tape drives too. You just got in the habit of writing programs that would work with this limitation. Yes, we were very simple back in those days.<\/p>\n
If you really needed to go back to a prior record in the sequence, you had to close a cursor then reopen it, remember the count of record you had read, and begin rereading from the front of the cursor all over again. Yuck.<\/p>\n
Double Linked List.<\/h2>\n
The NDL Standard included next and prior commands. They could move up and down pointer chains in both directions. This obviously requires another part of the node to have the prior address as well as the next address. This reflects the way magnetic tapes work today. It\u2019s also pretty much how everybody thinks of linked lists today. It costs you one extra pointer per node and gives you quite a bit of control over your data navigation. Most of the time, a pointer\u2019s the same size as an integer; did you ever wonder why people traditionally use the integer datatypes for their identifiers when they\u2019re learning SQL? It is a rule of all advances in technology that a new technology will first imitate the old technology and then eventually find its own voice. This is why your cell phone’s camera makes a clicking sound like a mechanical shutter. This imitation is called a \u2018skeuomorph\u2019, and it’s a great crossword puzzle word. Thus, early skyscrapers tried to look as much like Greek and Roman temples as they could, until the fact that skyscrapers are tall finally sank into people\u2019s minds and we began to celebrate that fact.<\/p>\n
Junctions<\/h2>\n
The junction refers to a collection of pointers that go to various data nodes. You will see people referring to \u2018junction tables\u2019 in SQL forums, not realizing this concept is not relational at all. What they usually want to do in the relational model would be a multi\u2013table VIEW or query. When you did this with pointer chains, traversing it could be complicated. Each vendor had different implementations, but when we got to SQL, all we had was the REFERENCES clause.<\/p>\n
REFERENCES<\/h2>\n
In SQL we have the concept of a reference, and referential integrity. It has nothing whatsoever to do with any kind of traversal. It\u2019s derived from a data modeling concept of weak and strong entities. A weak entity is one that requires a strong entity in order to exist. For example, it doesn\u2019t make any sense to have order items unless you have an order. Strong entity can exist on its own; you might have an order with no items on it yet.<\/p>\n
In SQL we have referenced tables and referencing tables. Unlike pointer chains, they can be on the same table. Circular links in the pointer chain is usually a problem. Since pointers are based on traversals, you can wind up in an endless loop when you try to follow the chain.<\/p>\n
If you had a good algorithm\u2019s course, you might remember some of the tricks for detecting cycles in linked list structures (create two pointers, hold both on a node in the list, and advance one of them one node at a time; if the two pointers are ever equal again, you have a cycle. Otherwise, repeat the procedure on the next node in the list. If you go through all the nodes in your list, then there was no cycle). This is essentially how a recursive CTE (common table expression) works in SQL Server, but if it finds a cycle it continues running until it reaches an upper limit of repetitions.<\/p>\n
Self-REFERENCE Constraints<\/h2>\n
The best example of a self-reference is Kuznetsov\u2019s History Table SQL idiom which builds an unbroken temporal chain from the current row to the previous row. This is easier to show with code:<\/p>\n
CREATE TABLE Tasks\r\n (task_id CHAR(5) NOT NULL,\r\n task_score CHAR(1) NOT NULL,\r\n previous_end_date DATE, -- null means first task\r\n current_start_date DATE DEFAULT CURRENT_TIMESTAMP NOT NULL,\r\n CONSTRAINT previous_end_date_and_current_start_in_sequence\r\n CHECK (prev_end_date <= current_start_date),\r\n current_end_date DATE, -- null means unfinished current task\r\n CONSTRAINT current_start_and_end_dates_in_sequence\r\n CHECK (current_start_date <= current_end_date),\r\n CONSTRAINT end_dates_in_sequence\r\n CHECK (previous_end_date <> current_end_date)\r\n PRIMARY KEY (task_id, current_start_date),\r\n UNIQUE (task_id, previous_end_date), -- null first task\r\n UNIQUE (task_id, current_end_date), -- one null current task\r\n FOREIGN KEY (task_id, previous_end_date) -- self-reference\r\n REFERENCES Tasks (task_id, current_end_date));<\/pre>\nWell, that looks complicated! Let\u2019s look at it column by column. Task_id<\/strong> explains itself. The previous_end_date<\/strong> will not have a value for the first task in the chain, so it is NULL<\/strong>-able. The current_start_date<\/strong> and current_end_date<\/strong> are the same data elements, temporal sequence and PRIMARY KEY<\/strong> constraints we had in the simple history table schema.<\/p>\nThe two UNIQUE<\/strong> constraints will allow one NULL<\/strong> in their pairs of columns and prevent duplicates. Remember that UNIQUE<\/strong> is not like PRIMARY KEY<\/strong>, which implies UNIQUE NOT NULL<\/strong>.<\/p>\n
The Bachman diagrams are made up of boxes and arrows. In fact, there was a small-circulation newsletter for DBAs and systems analysts who worked with IDMS and other older mainframe database products entitled \u2018Boxes and Arrows\u2019 based on the appearance of Bachman diagrams.<\/p>\n
The main structuring concepts in this model are \u2018records\u2019 and \u2018sets\u2019. Records essentially follow the COBOL<\/a> definition ordered sequences of fields of different types: this allows complex internal structure such as repeating items and repeating groups. There are no virtual or computed fields. The set concept should not be confused with the mathematical set that used in an RDBMS. A CODASYL<\/a> set represents a one-to-many relationship between records: one owner, many members. Unlike a strictly hierarchical data model, a record can be a member of many different sets. But unlike the set concept from RDBMS, these guys are ordered (so they are not really sets) and the records within a set are also in a sequence!<\/p>\n Records have a locator represented by a value known as a database key<\/strong>. Did you ever wonder where Sybase got the idea of the IDENTITY<\/strong> table property when they first implemented SQL? In IDMS, as in most other CODASYL implementations, the database key is directly related to the physical <\/em>address of the record on disk, without regard to any of the values in the record. In short, it\u2019s not relational. Database keys are then used as pointers to linked lists and trees. This means that the logical model and the physical implementation look a lot alike. Here\u2019s the trade-off with this approach; Database retrieval can be pretty efficient because it\u2019s really fast to traverse lists. But loading and restructuring these linked lists can be very<\/em> expensive. Also, if a linked list was broken, you needed special utility programs to try and rebuild them. It was not always possible to do these rebuilds. Finally, if you needed to access the data in a particular order, which was not how the sets or records are physically ordered, then you have the overhead of sorting.<\/p>\n Many SQL programmers have never worked with pointers. When I explained the nested set model to programmers in some of my classes, the older programmers have a real hard time with it because they want to build tree structures with pointer chains. This is why you will see an organizational chart done with (emp_id<\/strong>, boss_emp_id<\/strong>) pairs to model the head and tail of a pointer chain link. This was so much a part of the mindset at the start of RDBMS, that the Oracle sample database (\u2018Scott\/Tiger\u2019 is the nickname it\u2019s gotten over the decades because of the user and the password in it) is built on this adjacency list model.<\/p>\n However, younger programmers look at this approach in SQL and see it as a badly denormalized table. The same employee identifier appears in multiple places in the same table, in violation of First Normal Form (1NF). It requires very complex constraints to prevents cycles ensure that the hierarchy is a proper tree.<\/p>\n The nested set model doesn\u2019t have the normal form violations and redundancy. New programmers who didn\u2019t grow up with assembly language and low-level machine constructs look at it and say \u201cOh, this is XML tags written in a different language!\u201d instead.<\/p>\n When people on SQL forums refer to a \u2018link table\u2019, they are using the term that refers to pointer chains. The simplest possible list structure is a single linked list, which would look something like this<\/p>\n You enter the chain at a node and either pull out the data attached to it or get the address of the next link in the chain. Eventually will follow the path down to a \u2018nil\u2019 node (not to be confused with the NULL<\/strong> in SQL). You\u2019ll notice that the structure allows you to move in only one direction.<\/p>\n This limitation on traversal is not as bad as you might first think. If you been working with SQL Server for a few decades, you will remember that the cursors in the very early versions of the product also could only read forward. The reason for this was very simple; the early tape drives from which model of cursors was developed could only read in one direction! This was not just on small machines, but pretty much on all the mainframe tape drives too. You just got in the habit of writing programs that would work with this limitation. Yes, we were very simple back in those days.<\/p>\n If you really needed to go back to a prior record in the sequence, you had to close a cursor then reopen it, remember the count of record you had read, and begin rereading from the front of the cursor all over again. Yuck.<\/p>\n The NDL Standard included next and prior commands. They could move up and down pointer chains in both directions. This obviously requires another part of the node to have the prior address as well as the next address. This reflects the way magnetic tapes work today. It\u2019s also pretty much how everybody thinks of linked lists today. It costs you one extra pointer per node and gives you quite a bit of control over your data navigation. Most of the time, a pointer\u2019s the same size as an integer; did you ever wonder why people traditionally use the integer datatypes for their identifiers when they\u2019re learning SQL? It is a rule of all advances in technology that a new technology will first imitate the old technology and then eventually find its own voice. This is why your cell phone’s camera makes a clicking sound like a mechanical shutter. This imitation is called a \u2018skeuomorph\u2019, and it’s a great crossword puzzle word. Thus, early skyscrapers tried to look as much like Greek and Roman temples as they could, until the fact that skyscrapers are tall finally sank into people\u2019s minds and we began to celebrate that fact.<\/p>\n The junction refers to a collection of pointers that go to various data nodes. You will see people referring to \u2018junction tables\u2019 in SQL forums, not realizing this concept is not relational at all. What they usually want to do in the relational model would be a multi\u2013table VIEW or query. When you did this with pointer chains, traversing it could be complicated. Each vendor had different implementations, but when we got to SQL, all we had was the REFERENCES clause.<\/p>\n In SQL we have the concept of a reference, and referential integrity. It has nothing whatsoever to do with any kind of traversal. It\u2019s derived from a data modeling concept of weak and strong entities. A weak entity is one that requires a strong entity in order to exist. For example, it doesn\u2019t make any sense to have order items unless you have an order. Strong entity can exist on its own; you might have an order with no items on it yet.<\/p>\n In SQL we have referenced tables and referencing tables. Unlike pointer chains, they can be on the same table. Circular links in the pointer chain is usually a problem. Since pointers are based on traversals, you can wind up in an endless loop when you try to follow the chain.<\/p>\n If you had a good algorithm\u2019s course, you might remember some of the tricks for detecting cycles in linked list structures (create two pointers, hold both on a node in the list, and advance one of them one node at a time; if the two pointers are ever equal again, you have a cycle. Otherwise, repeat the procedure on the next node in the list. If you go through all the nodes in your list, then there was no cycle). This is essentially how a recursive CTE (common table expression) works in SQL Server, but if it finds a cycle it continues running until it reaches an upper limit of repetitions.<\/p>\n The best example of a self-reference is Kuznetsov\u2019s History Table SQL idiom which builds an unbroken temporal chain from the current row to the previous row. This is easier to show with code:<\/p>\n Well, that looks complicated! Let\u2019s look at it column by column. Task_id<\/strong> explains itself. The previous_end_date<\/strong> will not have a value for the first task in the chain, so it is NULL<\/strong>-able. The current_start_date<\/strong> and current_end_date<\/strong> are the same data elements, temporal sequence and PRIMARY KEY<\/strong> constraints we had in the simple history table schema.<\/p>\n The two UNIQUE<\/strong> constraints will allow one NULL<\/strong> in their pairs of columns and prevent duplicates. Remember that UNIQUE<\/strong> is not like PRIMARY KEY<\/strong>, which implies UNIQUE NOT NULL<\/strong>.<\/p>\nFlavors of Pointers<\/h2>\n
Simple Linked List<\/h2>\n
<\/p>\nDouble Linked List.<\/h2>\n
Junctions<\/h2>\n
REFERENCES<\/h2>\n
Self-REFERENCE Constraints<\/h2>\n
CREATE TABLE Tasks\r\n (task_id CHAR(5) NOT NULL,\r\n task_score CHAR(1) NOT NULL,\r\n previous_end_date DATE, -- null means first task\r\n current_start_date DATE DEFAULT CURRENT_TIMESTAMP NOT NULL,\r\n CONSTRAINT previous_end_date_and_current_start_in_sequence\r\n CHECK (prev_end_date <= current_start_date),\r\n current_end_date DATE, -- null means unfinished current task\r\n CONSTRAINT current_start_and_end_dates_in_sequence\r\n CHECK (current_start_date <= current_end_date),\r\n CONSTRAINT end_dates_in_sequence\r\n CHECK (previous_end_date <> current_end_date)\r\n PRIMARY KEY (task_id, current_start_date),\r\n UNIQUE (task_id, previous_end_date), -- null first task\r\n UNIQUE (task_id, current_end_date), -- one null current task\r\n FOREIGN KEY (task_id, previous_end_date) -- self-reference\r\n REFERENCES Tasks (task_id, current_end_date));<\/pre>\n