NFQL(ID:1504/nfq001)for Natural Forms Query Language, D. Embley, 1989 Structures: Related languages
References: Introduction The Natural Forms Query Language (NFQL) is a database query language in which retrieval requests and computation specifications are formulated by sketching ordinary forms that show what data are desired, and update operations are specified by altering data on filled-in forms. Forms are common and well understood in our modern society, especially in the office. They organize and structure communication according to well-established and longstanding conventions. NFQL attempts to take advantage of these features to provide a ?natural? communication language between computers and humans. Other systems [...] also make use of forms as a communication language, but none of these analyze and process forms in the same way as NFQL. To a greater or lesser extent, all these systems require procedural specification. NFQL is strictly nonprocedural, and in contradistinction to these other form systems is based on the universalrelation model [34, 451. Of these forms systems, NFQL is most like FORMANAGER [47], which permits a greater amount of nonprocedural specification than the other forms systems referenced. Both FORMANAGER and NFQL allow form designers to create forms with full-screen editors, specify search and display fields for database values, implicitly generate both retrieval and update queries for an underlying relational database, and cause computations to be performed. Both are relationally complete, although the claim of completeness in [47] is not supported by formal justification. They also both allow form users to update a database by altering data on filled-in forms, but FORMANAGER is functionally more restrictive because it does not permit deletion. Although FORMANAGER and NFQL both support hierarchical display of data, NFQL has some additional flexibility in data display and end-user update because of its use of a left-outer natural join. An important difference between the two systems is the extent of procedural specification required. In FORMANAGER, computations must be specified by giving an expression to compute a value, and joins between underlying relations must be specified by giving relation names and common attributes on which joins are performed. In NFQL, neither expressions for computations nor relations and attributes for joins need be specified. Another important difference is the extent to which view updates have been analyzed and incorporated into the system. Since NFQL is based on the universal relation, it also is closely related to the query languages PIQUE [31] and System/U [27], which are not forms systems. NFQL differs from these systems in its use of directed hypergraphs, in its use of subscripts derived from multiple occurrences of an attribute on a form, and in its use of multiple cooperating forms (queries). These features allow for a richer class of acyclic queries. In addition to allowing queries to be specified without direct reference to relations (as is typical in universal-relation query language), NFQL also allows queries to be specified without direct reference to attribute names, and thus provides additional freedom for a user. Since NFQL is relationally complete, includes computations, supports database update, and provides context through a forms-programming paradigm, it represents a more complete attempt to make universal-relation ideas usable and practical. To introduce NFQL, we show and briefly discuss the sample order form in Figure 1. Without much effort, we can see that if a customer wishes to place an order, it is only necessary to supply a customer number and for each item ordered a quantity and catalog number. An order clerk (or computer system acting as an order clerk) can supply the current date, order number, customer name and address, the sales-tax percent, and for each item the description and unit cost, and then compute the extended amount, subtotal, sales tax, and total. ?Encoded? within each of us is a substantial body of knowledge about forms (how they are laid out and filled in), about unique object identifiers and their relationship to object attributes (e.g., customer number and its relationship to customer name and address), and about concepts of time (e.g., the current date) and computations (which ones are expected and how to do them). These observations raise the following questions. How can we establish a knowledge base so that this knowledge we apparently have can be used by a computer system to also understand a form, having never seen it before? Then, understanding the meaning of a form, how can the system?s knowledge base be used to supply routines to read and validate data entered by a user, to generate queries to retrieve information from and make updates to a database, and to assemble code to do necessary calculations? Although these are the specific questions addressed in the NFQL project, their answers are more widely applicable. The broader objective of the investigation is to learn more about how to organize and manipulate knowledge information so that computer software can be generated from imprecise and incomplete specifications. Blank forms sketched by users are an example of one type of imprecise and incomplete specification. Code generated from a system?s interpretation of a form is executable software. An overview of some earlier work on the NFQL project can be found in [19]. In Section 2 of this paper, we define the basic semantic model for NFQL and detail the kinds of fundamental and composite facts implied by the model. In Section 3, we investigate the basic problem of generating queries to retrieve data given only the limited and somewhat sketchy information provided on a typical form. The problem of determining which fields of a form contain data that are updatable and what changing the data on a filled-in form means is discussed in Section 4. In Section 5, we further investigate the data retrieval problem and show that if we allow a set of NFQL forms to be specified, NFQL has the retrieval power expected of typical query languages. How computations implied by a form can be automatically discovered and coded is the subject of Section 6. Statements about what has been accomplished are contained in the conclusion, Section 7. Introduction The Natural Forms Query Language (NFQL) is a query language in which retrieval requests are formulated by sketching ordinary forms, such as the one shown in Figure 1 [6,9]. An NFQL query shows what data is desired, but does not procedurally explain how to retrieve the data. NFQL analyzes a form in the context of a given database scheme and generates executable code that allows the form to be filled in. The generated code for the SEMESTER GRADE REPORT form in Figure 1, for example, would accept a student ID# and semester (SEM) from an end user filling in the form, would retrieve and fill in the student's NAME and courses taken during the semester (COURSE#) along with each course's credit hours (CRHRS) and the GRADE received. If the form also had a entry for semester GPA, code would be generated that would compute the GPA and enter it on the form. "Encoded" within each of us, is a substantial body of knowledge about forms (how they are laid out and filled in), about unique object identifiers and their relationship to object attributes (e.g., identification numbers and their relationship to names), about concepts of time (e.g., the current date and the current semester), and about computations (which ones are expected and how to do them). In general, the NFQL project addresses the question of how to establish a knowledge base so that this knowledge we apparently have can be used by a computer system to also "understand" n a form, having never seen it before. Questions are also addressed about how the system's knowledge can be used to supply routines to read and validate data entered by a user, to generate queries to retrieve information from and make updates to a database, and to assemble code to do necessary calculations. These questions have been addressed and largely answered in [9] and other earlier publications [4, 8, 7, 5]. The question of retrieval power, however, has not been adequately addressed and is answered in this paper. We describe basic NFQL in Section 2, explain why it is not relation any complete, and introduce extensions to make it more powerful. We show in Section 3 that the extensions make NFQL relationally complete. Whenever a language is extended, the new features may have a negative effect on the usability of tire language. We therefore discuss the pragmatics of the extensions in Section 4 and suggest improvements. The implementation status of NFQL is included in the summary remarks of Section 5. Before continuing, we mention several other systems that also make use of forms as a communication language [5,10,12,13,18,20,19,22,24,26,27]. None of these forms systems analyse and process forms in the same way as NFQL. To a greater or lesser extent, all these systems require procedural specification. NFQL is strictly nonprocedural and in contradistinction to these other form systems is based on the universal-relation model [23, 17]. Additional and more-specific comparisons between these forms systems and NFQL are contained the cited literature on NFQL. Extract: Basic NFQL Basic NFQL For NFQL, we derive the relational database scheme from an Entity-Relationshlp (ER) model [2]. A sample ER diagram and derived database scheme for the examples in this paper are shown in Figure 2. In an ER diagram keys and key components are underlined and composite key components for an entity or relationship set are joined together with an arc. For simplicity, we assume that each of the attributes is unique. Relations for the derived database are assumed to observe key dependencies and referential integrity. NFQL forms consist of blank fields to be filled in and suggestive words or phrases that indicate what should be filled in. We call each suggestive word or phrase a keyword. For basic NFQL, keywords must be attribute names, and there must be no duplicate keywords on the form. Blank fields on a form may be either single. entry allowing at most one value, or multiple-entry allowing zero or more values. One or more multiple-entry blanks may be grouped together to form a multiple-entry group as are the multiple-entry blanks for COURSE#, CRHRS, and GRADE on the form in Figure 1. When a form is analyzed, we require that the form designer specify which blanks are to be filled in by an end user and which are to be filled in from the database or by computations. Blanks to be filled in by a user are called u-blanks, blanks to be filled in by the database are called d-blanks, and blanks to be filled in by computation are called c-blanks. To specify the type of blank, one of the source designators, "u", WTd"~ or %", is placed in the blank of an NFQL form. (We ignore c-blanks in the remainder of this discussion. See [4] for more information on NFQL computations.) Although attribute names and source designators are part of an NFQL query, there is never any mention of a relation. In this regard NFQL is like the query language of System/U [HI, like PIQUE [14], and like the "window functions" surveyed in [15]. The common and most important feature of these languages is that they relieve the user of the responsibility to navigate among relations. Thus, the intent of the relational model -- to relieve the user of the responsibility to navigate within the physical database -- is carried even one step further. NFQL differs from these no-navigation-among-relations query languages because they are not forms oriented. Since NFQL is a no-navigation-among-relations query language% it differs fundamentally from standard query languages such as QBE [25], SQL [1], and QUEL [21]. The analysis of an NFQL form yields an interpretation, which is an internal representation of a form that can be transformed into an expression template. An expression template is a relational algebra expression with "slots" for each of tile u-blank values (if any). When the u-blank values are provided at the time the form is filled in, the expression template becomes a relational algebra expression that can be evaluated to retrieve data from the database to fill in the d-blanks. Interpretations for NFQL forms are defined in terms of fundamental relationships derived from the ER model of the database. A fundamental relationship is similar to an object 116], which is a minimal, significant connection among a set of attributes. In preparation for the definition of fundamental relationships, we defined an alternate scheme for relations derived from relationships in the ER model. Let R be a relationship of tile ER model related to entities El, E2, ..., En. Let S be the set of all possible schemes for R given all possible choices for primary keys in El, E2, ..., En. For the derived database, one primary key is chosen for each entity, and thus one of these possible schemes $1 is chosen as the scheme for R in the derived database. Each of the remaining schemes in S - {S1} is called an alternate scheme. For example, IS_TAKING( NAME. ADDR. COURSEd) is an alternate scheme for IS_TAKING in Figure 2. We now define fundamental relationships. Let A and B be disjoint subsets of a scheme or alternate scheme S for scheme R such that AB includes a key for S. A may be empty, but B must not be empty; and A must not (by itself) include a key K of S unless A K. A fundamental relationship (FR) is a labeled, ordered pair R(A,B), written (R) A -: B, such that B is minimal (no attribute can be removed from B without violating some condition). Extract: Extended NFQL Extended NFQL As defined, basic NFQL is not relationally complete. It does not have any set operations, it has no renaming operation, constant relations cannot be defined independently of base relations, and its projection and selection capabilities are overly restricted. We extend NFQL by adding selection and renaming specifications, by permitting constant user-defined relations to stand by themselves, and by allowing queries to be specified by sets of forms. The set of forms in Figure 4 will serve to exemplify the extensions. This set of forms answers the query, "List the names of students repeating four- and five-hour courses tiffs semester and also list the information about these courses." The CURRENT ENROLLMENT form (see Figure 4) provides data on courses in progress during the current semester. The COMPLETED COURSES form provides data on courses already completed. When appropriately restricted, the intersection of the data on these two forms yields the answer to the query. The results are displayed on the REPEATED COURSES REPORT form. How this is done is explained in what follows. Selection. One or more selection operations may be specified for either single- or multiple-entry blanks. Each specification has one comparison operator op and one operand F that is either a constant or a keyword on the form. A selection specification "op P" for an entry blank with keyword K yields a boolean expression "K op P". All values mapped into the entry blank must satisfy this boolean constraint. Examples, "> 3" and "< fi", are shown in the CRHRS blank on the REPEATED COURSES REPORT form in Figure 4. When more than one selection specification appears in an entry blank, the resulting expression is a conjunction of the individual expressions. Thus, the meaning of these two operator-operand pairs is that only courses that have more than 3 and less than 6 credit hours will be displayed. Renaming. A keyword may be renamed. Each renaming specification consists of the renaming symbol ~ and an alternate name for the entry blank called a synonym name. The synonym name replaces the keyword renamed when the form is displayed for the end user, and thus the synonym name is the only name seen when the form is used. In Figure 4 NAME and CRHRS in the REPEATED COURSES REPORT form are renamed to be STUDENT_NAME and CREDIT_HOURS, respectively, and COURSE# in the CURRENT ENROLLMENT form and also in the COMPLETED COURSES form is renamed to be GOURSE_NR. At most one renaming operation for each single- or multiple-entry blank is allowed. Synonym names must not be database attribute names. Constant Relations. A template for a constant relation can be created at form-design time. The designer creates a form, gives it a title, chooses keywords that are not attribute names, and makes every entry blank a u-blank. Tuples for the constant relation are filled in by the user when the form is filled out. Observe that such a form would have no interpretation in basic NFQL. Interform Data Flow. Extended NFQL provides a way to use data from forms as intermediate results. This is called interform data flow. Interform data flow is specified by making a single- or multiple-entry blank an f-blank. An f-blank is marked with an "f" followed by a form title in parenthesis (e.g., f(CURRENT ENROLLMENT) in the NAME colmnn of the REPEATED COURSES REPORT form in Figure 4.) The form title in the f-blank specification references tile form from which data will flow into the f-blank. Form titles are unique identifiers of forms in NFQL. For correct specification of interform data flow, we require that an entry blank on the referenced form be identified as the supplier of the data values. This is implicitly specified as follows. If the entry blank supplying tile data has no renaming symbol, then the name of the f-blank keyword must be the same as the keyword for the entry blank supplying the data. If the entry blank supplying the data is renamed, such as COURSE# in the CURRENT ENROLLMENT form and in the COMPLETED COURSES form in Figure 4, then the f-blank keyword must be the synonym name (i.e, COURSE NR)~ not the name of the keyword (i.e. COURSE#) of the entry blank being referenced. This establishes, by transitivity, links that eventually lead to an attribute of the database. If for one entry blank of a form there is more than one set of transitive links to database attributes, we require that all sets of links lead to the same attribute (e.g., COURSE_NR is linked to COURSE# by the set of transitive links through both the CURRENT ENROLLMENT and the COMPLETED COURSES form). A mapping between keywords and attribute names is thus established. Although not strictly necessary, we assume for this paper that this mapping is bijective so that if keywords (which for a form are assumed to be distinct) are replaced by their corresponding attributes, the attributes of the form will also be distinct. A further requirement is that requests be structurally consistent. If an f-blank is a single-entry blank, then tile data that flows into the f-blank must come from a single-entry blank. If an f-blank is a multiple-entry blank, then the type of entry-blank from which data flows into the f-blank can either be a single- or multiple-entry blank. An NFQL form can reference no more than two other forms. If a form F references only one other form FI, the data that flows into the f-blanks of F is the set of tuples of the entry-blanks in F1 referenced by the f-blanks of F. The effect is equivalent to a projection on the intermediate results displayed on the referenced form. When two forms are referenced in one entry blank, the order of the form titles is insignificant. If every f-blank of a form F that references the first form F1 also references the second form F2, then after projecting to obtain the sets of tuples from F1 and F2, one of the operators union, set difference, or natural join is applied to the two sets of tuples before the data flows to the f-blanks of F. To give the expected results, the data that flows into the entry-blanks NAME and COURSE NR in the REPEATED COURSES REPORT form (Figure 4) must be operated on by natural join, which gives the intersection of the NAME-COURSE_NR-tuples in the CURRENT ENROLLMENT form and the COMPLETED COURSES form. If every f-blank of a form F that references the first form does not also references the second form, then as the data flows into the f-blanks of F, it is operated on by natural join. Given a form F, the set of forms referenced by F and all forms referenced recursively from forms referenced by F is called a set of related NFQL forms. We require that the referencing be acyclic. The form F of a set of related NFQL forms is called a root form. Observe that the referencing induces a tree structure on a set of related NFQL forms and a forest on the entire collection of forms known to the system. Since every form in the forest is the root of some subtree, every form is a root form of some set of related NFQL forms. |