A grammar-based approach towards unifying hierarchical data models

M. Gyssens, J. Paredaens, D. Van Gucht

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)
316 Downloads (Pure)


A simple model for representing the hierarchical structure of information is proposed. This model, called the grammatical model, is based on trees that are generated by grammars; the grammars describe the hierarchy of the information represented by the trees. Two methods for querying in this data model are given. The first, called the grammatical algebra, is based on a set of primitive grammar-oriented operators, the second, called the grammatical calculus, on local transformations on the trees. The semantics of both is formally defined. Decidability issues regarding the grammatical calculus are investigated. Finally, the two querying methods are proved to be equally expressive.
Original languageEnglish
Pages (from-to)1093-1137
JournalSIAM Journal on Computing
Issue number6
Publication statusPublished - 1994


Dive into the research topics of 'A grammar-based approach towards unifying hierarchical data models'. Together they form a unique fingerprint.

Cite this