A grammar-based approach towards unifying hierarchical data models

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

doi:10.1137/S0097539790188168

A grammar-based approach towards unifying hierarchical data models

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

Department of Mathematics and Computer Science

Research output: Contribution to journal › Article › Academic › peer-review

9 Citations (Scopus)

213 Downloads (Pure)

Abstract

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 language	English
Pages (from-to)	1093-1137
Journal	SIAM Journal on Computing
Volume	23
Issue number	6
DOIs	https://doi.org/10.1137/S0097539790188168
Publication status	Published - 1994

Access to Document

10.1137/S0097539790188168

Metis148719Final published version, 4.64 MB

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

Cite this

@article{719e13c0442b4b079db2f84fff9720f7,

title = "A grammar-based approach towards unifying hierarchical data models",

abstract = "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.",

author = "M. Gyssens and J. Paredaens and {Van Gucht}, D.",

year = "1994",

doi = "10.1137/S0097539790188168",

language = "English",

volume = "23",

pages = "1093--1137",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

number = "6",

}

TY - JOUR

T1 - A grammar-based approach towards unifying hierarchical data models

AU - Gyssens, M.

AU - Paredaens, J.

AU - Van Gucht, D.

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

U2 - 10.1137/S0097539790188168

DO - 10.1137/S0097539790188168

M3 - Article

VL - 23

SP - 1093

EP - 1137

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 6

ER -