Hi Folks,
XML is a hierarchical data format. Can flat formats express hierarchy? Answer: yes
A hierarchical structure may be equivalently represented in a flat structure. And vice versa. Why is this important? Answer: If data is in one form, but the tools that are most suitable and efficient require the
data be in another form, then simply convert the data to the equivalent other form.
Below I demonstrate the equivalence of hierarchical and flat data formats.
1. Equivalence of lists of data
Below is a list of book data. A hierarchical data format (XML) is used to express the list.
<books>
<book>
<title>Compilers Principles, Techniques, Tools</title>
<authors>Alfred V. Aho, Ravi Sethi, Jeffrey Ullman</authors>
<publisher>Addison-Wesley</publisher>
<date>1986</date>
</book>
<book>
<title>Introduction to Compiling Techniques</title>
<authors>J. P. Bennett</authors>
<publisher>McGraw-Hill</publisher>
<date>1996</date>
</book>
<book>
<title>Economic Facts and Fallacies</title>
<authors>Thomas Sowell</authors>
<publisher>Basic Books</publisher>
<date>2011</date>
</book>
<book>
<title>Economics in One Lesson</title>
<authors>Henry Hazlitt</authors>
<publisher>Harper & Brothers</publisher>
<date>1946</date>
</book>
</books>
Below is an equivalent list of books, using a tab-delimited flat data format:
Compilers Principles, Techniques, Tools Alfred V. Aho, Ravi Sethi, Jeffrey Ullman Addison-Wesley 1986
Introduction to Compiling Techniques J. P. Bennett McGraw-Hill 1996
Economic Facts and Fallacies Thomas Sowell Basic Books 2011
Economics in One Lesson Henry Hazlitt Harper & Brothers 1946
We can use the XSLT tool to process the XML-formatted data. We can use the awk tool to process the flat data. Which tool is better depends on the availability of the tool, expertise with the tool, performance requirements,
size of the data, and other factors.
2. Equivalence of parent-child nesting
Some books have multiple authors, so let’s add a nesting level to the authors data. That is, in the list of books, each book has a list of authors.
Below is a hierarchical representation of the author nesting.
<books>
<book>
<title>Compilers Principles, Techniques, Tools</title>
<authors>
<author>Alfred V. Aho</author>
<author>Ravi Sethi</author>
<author>Jeffrey Ullman</author>
</authors>
<publisher>Addison-Wesley</publisher>
<date>1986</date>
</book>
<book>
<title>Introduction to Compiling Techniques</title>
<authors>
<author>J. P. Bennett</author>
</authors>
<publisher>McGraw-Hill</publisher>
<date>1996</date>
</book>
<book>
<title>Economic Facts and Fallacies</title>
<authors>
<author>Thomas Sowell</author>
</authors>
<publisher>Basic Books</publisher>
<date>2011</date>
</book>
<book>
<title>Economics in One Lesson</title>
<authors>
<author>Henry Hazlitt</author>
</authors>
<publisher>Harper & Brothers</publisher>
<date>1946</date>
</book>
</books>
The key to expressing parent-child relationships in a flat data structure is to put the parent list in one file and the children lists in a separate file; e.g., put the book list in one file and the authors lists
in another file. Then, for each parent, use a primary/foreign key to connect the parent to its child. This is shown below.
BookList.dat
Compilers Principles, Techniques, Tools AUT01 Addison-Wesley 1986
Introduction to Compiling Techniques AUT02 McGraw-Hill 1996
Economic Facts and Fallacies AUT03 Basic Books 2011
Economics in One Lesson AUT04 Harper & Brothers 1946
AuthorsList.dat
AUT01 Alfred V. Aho, Ravi Sethi, Jeffrey Ullman
AUT02 J. P. Bennett
AUT03 Thomas Sowell
AUT04 Henry Hazlitt
Notice that instead of embedding the authors in BookList.dat, a foreign key (e.g., AUT01) references the appropriate record in AuthorList.dat
Let’s add another level of nesting: add a grouping to the two compiler books and a grouping to the two economics books.
An XML representation is shown below.
<books>
<compiler-books>
<book>
<title>Compilers Principles, Techniques, Tools</title>
<authors>
<author>Alfred V. Aho</author>
<author>Ravi Sethi</author>
<author>Jeffrey Ullman</author>
</authors>
<publisher>Addison-Wesley</publisher>
<date>1986</date>
</book>
<book>
<title>Introduction to Compiling Techniques</title>
<authors>
<author>J. P. Bennett</author>
</authors>
<publisher>McGraw-Hill</publisher>
<date>1996</date>
</book>
</compiler-books>
<economics-books>
<book>
<title>Economic Facts and Fallacies</title>
<authors>
<author>Thomas Sowell</author>
</authors>
<publisher>Basic Books</publisher>
<date>2011</date>
</book>
<book>
<title>Economics in One Lesson</title>
<authors>
<author>Henry Hazlitt</author>
</authors>
<publisher>Harper & Brothers</publisher>
<date>1946</date>
</book>
</economics-books>
</books>
There are multiple ways to represent the new nesting in a flat data structure. Below is one way.
BookList.dat
Compiler Compilers Principles, Techniques, Tools AUT01 Addison-Wesley 1986
Compiler Introduction to Compiling Techniques AUT02 McGraw-Hill 1996
Economics Economic Facts and Fallacies AUT03 Basic Books 2011
Economics Economics in One Lesson AUT04 Harper & Brothers 1946
AuthorsList.dat
AUT01 Alfred V. Aho, Ravi Sethi, Jeffrey Ullman
AUT02 J. P. Bennett
AUT03 Thomas Sowell
AUT04 Henry Hazlitt
Clearly any nesting in a hierarchical data format can be equivalently expressed in a flat data format.
3. Equivalence of choice
Some books are hardcover while others are softcover. That is, there is a choice between hardcover and softcover.
In XML “choice” means alternative elements, e.g., <hardcover> or <softcover>.
In a flat data format “choice” simply means alternative field values, e.g., hardcover or softcover.
/Roger
P.S. Probably someone already proved this equivalence. Probably 50+ years ago. If you could point me to the proof, I would appreciate it. Nonetheless, it has been a useful insight for me.
Cart
