Equivalence of hierarchical and flat data formats

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 &amp; 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 &amp; 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 &amp; 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.