A grammar-based approach towards unifying hierarchical data models

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

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

9 Citations (Scopus)
185 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 languageEnglish
Pages (from-to)1093-1137
JournalSIAM Journal on Computing
Volume23
Issue number6
DOIs
Publication statusPublished - 1994

Fingerprint

Hierarchical Data
Hierarchical Model
Grammar
Data Model
Data structures
Calculus
Computability and decidability
Decidability
Hierarchical Structure
Algebra
Semantics
Model
Operator

Cite this

Gyssens, M. ; Paredaens, J. ; Van Gucht, D. / A grammar-based approach towards unifying hierarchical data models. In: SIAM Journal on Computing. 1994 ; Vol. 23, No. 6. pp. 1093-1137.
@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",

}

Gyssens, M, Paredaens, J & Van Gucht, D 1994, 'A grammar-based approach towards unifying hierarchical data models', SIAM Journal on Computing, vol. 23, no. 6, pp. 1093-1137. https://doi.org/10.1137/S0097539790188168

A grammar-based approach towards unifying hierarchical data models. / Gyssens, M.; Paredaens, J.; Van Gucht, D.

In: SIAM Journal on Computing, Vol. 23, No. 6, 1994, p. 1093-1137.

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

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 -

Gyssens M, Paredaens J, Van Gucht D. A grammar-based approach towards unifying hierarchical data models. SIAM Journal on Computing. 1994;23(6):1093-1137. https://doi.org/10.1137/S0097539790188168

Access to Document