A hybrid basis for the implementation of Language-Based Editors (LBEs), called relationally attributed grammars, is introduced in this paper. Information about the state of a source program is kept as a combination of attributes to a parse tree (rather standard) and database relations (the novel contribution). The advantages claimed include that database tables are more efficient because global information need not be passed through many levels of a parse tree as attributes. They also provide a systematic way of checking static-semantics, detecting anomalies, and responding to queries.

The paper presents algorithms for efficiently responding to queries and updating views. The essence of the algorithms is that a value at a node--representing either a query response or a view (which is an implicit query)--is a function of the subtree rooted at the node. A postorder traversal is used to evaluate relational operators (e.g., intersection) without materialization of the relevant relations and, in the case of views, by only evaluating incremental changes to the view.

The basis of the algorithms is the notion of Membership-Test and Selective-Retrieval functions applied to implicit and explicit tables. For example, union(A,B) may be computed by using Selective-Retrieval to obtain the elements of Table A and then using Membership-Test to determine if any are in Table B. The other standard relational operators may be similarly computed.

A prototype has been implemented (based on the Cornell LBE Synthesizer Generator) but no statistics are given for the effectiveness of the algorithms. Only the briefest numerical comparisons to other systems are given.

This paper is based on Horwitz’s PhD thesis [1]. Little background is given on editing environments or attribute grammars. Large parts of the paper read as if it were a tutorial on the relational model. For example, a grammar of condition is given and half-page figures are used to illustrate calculations which could be expressed in a few lines of SQL or the relational algebra. On the other hand, no explanation is given of a “link-cut data structure” which must be used if the algorithms are to be at all efficient.

Overall, the paper would be worth reading for someone who wishes to have an idea of one aspect of current work in LBEs. The experienced database worker would probably gain very little from it, particularly someone familiar with the INGRES QUEL decomposition algorithm.