{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:32:30Z","timestamp":1787340750830,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1994,12]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/s0097539790188168","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:39:46Z","timestamp":1109227186000},"page":"1093-1137","source":"Crossref","is-referenced-by-count":11,"title":["A Grammar-Based Approach Towards Unifying Hierarchical Data Models"],"prefix":"10.1137","volume":"23","author":[{"given":"Marc","family":"Gyssens","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Paredaens","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dirk","family":"Van Gucht","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, N. Bidoit,  Non first normal form relations to represent hierarchically organized data,  Proceedings 3rd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, ACM Press, New York,  1984,  191\u2013198","DOI":"10.1145\/588011.588038"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/32204.32205"},{"key":"R3","volume-title":"Data structures and algorithms","author":"Aho Alfred V.","year":"1983"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"C. Beeri, S. Naqvi, R. Ramakrishnan, O. Schmueli, S. Tsur,  Sets and negation in a logic database language (LDL1),  Proceedings 6th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ACM Press, New York,  1987,  21\u201337","DOI":"10.1145\/28659.28662"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(87)90019-5"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Ashok K. Chandra, Philip M. Merlin,  Optimal implementation of conjunctive queries in relational data bases,  Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977), Assoc. Comput. Mach., New York,  1977,  77\u201390 58:8576","DOI":"10.1145\/800105.803397"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/320434.320440"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320109"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"P. Dadam, F. Kuespert, F. Andersen, H. Blanken, R. Erbe, J. Guenauer, V. Lum, P. Pistor, G. Walch,  A DBMS prototype to support extended NF2 relations: An integrated view on flat tables and hierarchies,  Proceedings ACM SIGMOD International Conference on Management of Data, ACM Press, New York,  1986,  356\u2013364","DOI":"10.1145\/16894.16889"},{"key":"R10","volume-title":"The mathematical theory of context-free languages","author":"Ginsburg Seymour","year":"1966"},{"key":"R11","unstructured":"G. H. Gonnet, F. W. Tompa,  Mind your grammar: A new approach to modelling text, Technical Report, University of Waterloo,  1988"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/319587.319588"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/828.832"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"G. Jaeschke, H.J. Schek,  Remarks on the algebra on non first normal form relations,  Proceedings 2nd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, ACM Press, New York,  1982,  124\u2013138","DOI":"10.1145\/588111.588133"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(80)90038-9"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"G. M. Kuper, M. Y. Vardi,  A new approach to database logic,  Proceedings 3rd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, ACM Press, New York,  1984,  124\u2013138","DOI":"10.1145\/588025.588026"},{"key":"R17","volume-title":"The theory of relational databases","author":"Maier David","year":"1983"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69956-6"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/319540.319561"},{"key":"R20","first-page":"269","volume-title":"Advances in Computing Research III: The Theory of Databases","author":"Thomas S. J.","year":"1986"},{"key":"R21","volume-title":"Principles of Database and Knowledge-Base Systems, Vols. I and II","author":"Ullman J. D.","year":"1988"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539790188168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:46:36Z","timestamp":1787337996000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539790188168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":21,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["10.1137\/S0097539790188168"],"URL":"https:\/\/doi.org\/10.1137\/s0097539790188168","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}