A GRAMMAR-BASED APPROACH TOWARDS UNIFYING HIERARCHICAL DATA MODELS

A simple model for representing the hierarchical structure of informat ion is proposed. This model, called the grammatical model, is based on trees that are generated by grammars; the grammars describe the hiera rchy of the information represented by the trees. Two methods for quer ying in this data model are given. The first, called the grammatical a lgebra, 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 iss ues regarding the grammatical calculus are investigated. Finally, the two querying methods are proved to be equally expressive.