Re: Equivalence of hierarchical and flat data formats

You could find a format capable of expressing losslessly all of the
semantics of the XML (perhaps OWL-DL) and then convert to XML to that
format and from there convert that format losslessly to your flat data
format.

On Tue, 26 Jul 2022 at 21:02, Roger L Costello <[email protected]> wrote:

> 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.
>
-- 
----
Stephen D Green