5.2. Relational calculus

Suppose that we work with a database that has an EMPLOYEES scheme (COTR_NOM, COTR_NAME, COTR_ZARP, OTD_NOM) and DEPARTMENTS (OTD_NOM, OTD_KOL, OTD_NAC), and we want to know the names and numbers of employees who are head of departments with more employees, who have more employees, who have more employees, who have more employees.

If relational algebra were used to formulate such a query, we would get an algebraic expression that would be read, for example, as follows:

• join the relationship EMPLOYEES and DEPARTMENTS by the condition COTR_NOM = OTD_NACh;
• to limit the resulting relationship on the condition DEPT_COL> 50;
• project the result of the previous operation on the attribute COTR_IMA, COTR_NOM.

We have clearly formulated a sequence of steps to execute a query, each of which corresponds to one relational operation. If we formulate the same query using the relational calculus to which this section is dedicated, then we would get a formula that could be read, for example, as follows: Issue COTS_NAME and COTS_NOM for employees such that there is a department with the same value OTD_COL value greater than 50.

In the second formulation, we indicated only the characteristics of the resulting relation, but did not say anything about the method of its formation. In this case, the system should decide for itself what operations and in what order the EMPLOYEES and DEPARTMENTS should perform on the relations. It is usually said that the algebraic formulation is procedural, i.e. specifies the rules for executing a query, and the logical one - descriptive (or declarative), since it only describes the properties of the desired result. As we indicated at the beginning of the lecture, in fact these two mechanisms are equivalent and there are not very complicated rules for the transformation of one formalism into another.

5.2.1. Tuple variables and well-constructed formulas

Relational calculus is an applied branch of the formal first-order predicate calculus mechanism. The basic concepts of calculus are the concept of a variable with a defined range of permissible values ​​and the concept of a well-constructed formula based on variables, predicates and quantifiers.

Depending on what is the domain of a variable, the calculus of tuples and the calculus of domains differ. In tuple calculus, the variable definition areas are database relations, i.e. the valid value of each variable is a tuple of some relation. In the domain calculus, the variable definition domains are the domains on which the database relationship attributes are defined, i.e. The valid value of each variable is the value of a certain domain. We consider in more detail the calculation of tuples, and at the end of the lecture we briefly describe the features of the calculation of domains.

Unlike the section on relational algebra, we will not be able to avoid using some specific syntax in this section, which we, however, will not be formally defined. The necessary syntax will be entered as needed. In aggregate, the syntax used is close, but not completely identical to the QUEL database language syntax, which has long been the main language of the Ingres DBMS.

To define a tuple variable, use the RANGE operator. For example, in order to define an EMPLOYEE variable, the domain of which is the relationship EMPLOYEES, you need to use the construction

  RANGE EMPLOYEE IS EMPLOYEES 

As we have said, it follows from this definition that at any moment in time the variable EMPLOYEE represents some tuple of the relation EMPLOYEES. When using tuple variables in formulas, you can refer to the value of an attribute of a variable (this is similar to how, for example, when programming in C, you can refer to the value of a field of a structural variable). For example, in order to refer to the value of the attribute COTR_NAME of a variable EMPLOYEE, you need to use the construct EMPLOYEE COMPLETE_NAME.

Properly constructed formulas (WFF - Well-Formed Formula) are used to express the conditions imposed on tuple variables. The basis of WFF are simple comparisons (comparisons), which are the operations of comparison of scalar values ​​(attribute values ​​of variables or literally defined constants). For example, the construct "EMPLOYER. CONF_NOM = 140" is a simple comparison. By definition, a simple comparison is WFF, and a WFF enclosed in parentheses is a simple comparison.

More complex WFF variants are built using the logical connectives NOT, AND, OR and IF ... THEN. So, if form is WFF and comp is a simple comparison, then NOT form, comp AND form, comp OR form and IF comp THEN form are WFF.

Finally, building WFF using quantifiers is allowed. If the form is a WFF in which the var variable participates, then the EXISTS var (form) and FORALL var (form) constructs represent wff.

Variables included in WFF may be free or bound. All variables included in the WFF, the construction of which did not use quantifiers, are free. In fact, this means that if for some set of values ​​of free tuple variables, when calculating WFF, the value is true, then these values ​​of tuple variables can be included in the resulting relation. If the variable name is used immediately after the quantifier when constructing a WFF of the EXISTS type var (form) or FORALL var (form), then in this WFF and in all WFF constructed with its participation, var is the associated variable. This means that such a variable is not visible outside the minimum WFF that linked this variable. When calculating the value of such a WFF, not one value of the associated variable is used, but its entire scope.

Let COTP1 and COTP2 be two tuple variables defined on the relation EMPLOYEES. Then, WFF EXISTS COTP2 (COTP1.COPP_ZARP> COTP2.COPP_ZARP) for the current tuple of the variable COTP1 is true if and only if there is a tuple (associated with the variable COTP2) in such a relation that its attribute is CETP_ZARP satisfies the internal comparison condition. WFF FORALL SHARP2 (COTP1.COTP_ZARP> COTP2.COPP_ZARP) for the current tuple of variable COTP1 is true if and only if for all tuples the relation EMPLOYEES (related to variable COTP2) of the attribute COTP_ZARP satisfy the comparison condition.

In fact, it is more correct to speak not of free and bound variables, but of free and bound occurrences of variables. It is easy to see that if var is bound in the WFF form, then in all WFFs that include this, the variable name var can be used, which can be free or bound, but in any case has nothing to do with the entry of the variable var in the WFF form. Here is an example:

  EXISTS COTP2 (COTP1.COTP_OTD_NOM = COTP2.COTP_OTD_NOM) AND
     FORALL СОТР2 (СОТР1. СОТР_ЗАРП> СОТР2. СОТР_ЗАРП) 

Here we have two related occurrences of the variable COTP2 with a completely different meaning.

5.2.2. Target lists and expressions of relational calculus

In summary, WFF provides the means of formulating the condition of a sample from a DB relationship. In order to be able to use calculus for real work with the database, another component is required that defines the set and column names of the resulting relation. This component is called the target list (target_list).

The target list is built from target elements, each of which can have the following form:

• var.attr, where var is the name of the free variable corresponding to the WFF, and attr is the name of the relation attribute on which the variable var is defined;
• var, which is equivalent to having a sub-list var.attr1, var.attr2, ..., var.attrn, where attr1, attr2, ..., attrn includes the names of all attributes of the defining relation;
• new_name = var.attr; new_name is the new name of the corresponding attribute of the resulting relationship.

The latter option is required in cases where several free variables with the same definition domain are used in WFF.

The expression for relational calculus of tuples is called a construction of the target_list type WHERE wff. The value of the expression is a relation whose body is defined by the WFF, and the set of attributes and their names is the target list.

5.2.3. Relational Domain Calculus

In domain calculus, the domain of definition of variables is not relations, but domains. With regard to the database EMPLOYEES-DEPARTMENTS, we can speak, for example, of domain variables NAME (values ​​are valid names) or HANDLING (values ​​are valid employee numbers).

The main formal difference in the calculation of domains from the calculation of tuples is the presence of an additional set of predicates, allowing to express the so-called membership conditions. If R is an n-ary relationship with attributes a ₁ , a ₂ , ..., a _n , then the membership condition is

  R (ai1: vi1, ai2: vi2, ..., aim: vim) (m <= n), 

where v _ij is either a literally given constant or the name of a tuple variable. The membership condition is true if and only if there is a tuple for R containing the specified values ​​of the specified attributes. If v _ij is a constant, then a hard condition is set to the attribute a _ij , independent of the current values ​​of the domain variables; if v _ij is the name of the domain variable, then the membership condition can take on different values ​​for different values ​​of this variable.

In all other respects, the formulas and expressions of the domain calculus look similar to the formulas and expressions of the calculus of tuples. In particular, of course, free and related occurrences of domain variables are different.

For example, using the calculus of domains, we formulate the query "Issue numbers and names of employees who do not receive the minimum wage" (for simplicity, we assume that we defined domain variables whose names coincide with the attribute names of the relationship EMPLOYEES, and in the case where several domain names are required) variables defined on one domain, we will add numbers at the end of the name):

  COTS_NOM, COTS_NAME WHERE EXISTS COTP_ZARP1
      (EMPLOYEES (COTR_ZARP1) AND
       EMPLOYEES (SOTR_NOM, SOTR_NAME, SOTR_ZARP) AND
       SOTR_ZARP> SOTR_ZARP1) 

The relational domain calculus is the basis of most query languages ​​based on the use of forms. In particular, this calculus was based on the famous Query-by-Example language, which was the first (and most interesting) language in a family of languages ​​based on table forms.