Mohammed K. Extending of the table algebra with multiple inheritance.

In the thesis, two goals were set. One goal was to formalize the algorithm for multiple inheritance of tables and study its properties. Another goal was to refine and further develop the table algebra of semantic functions of the SQL query language. Although many theoretical works are devoted to SQL semantics, they do not pay enough attention to object-oriented language extensions. These extensions were included in the standard of language and became an important part of modern relational databases. Such DBMSs are called object-relational DBMS. One of the characteristics of object-relational DBMS is the ability to inherit tables. They use single table inheritance. At the same time, there is a practical need for multiple table inheritance. This would make it possible to more adequately model the domain and describe the real world. With multiple inheritance, a name conflict problem occurs. It consists in the fact that in parent tables different columns can have the same names. In this case, the question arises which column to include in the child table. A similar problem, in its time, arose in object-oriented programming languages that support multiple inheritance. One way to solve the problem in object-oriented programming languages is to linearize the parent objects. In this method, a linear order is specified on the parent objects. Then the smallest object in the sense of this order is chosen. In other words, all parent objects are lined up. The attribute of the object that is located to the left of other objects that have attributes with the same names is selected in the child object. Numerous linearization algorithms have been developed. The most common among them was the MRO C3 algorithm. It was chosen as the basis for resolving name conflicts with multiple inheritance of tables. As it turned out, this algorithm was formulated at the semi-formal level, which made it impossible to formally prove its properties and correctness. In the thesis, the MRO C3 algorithm was modified to apply to tables and was specified strictly using a pseudocode. Formal proof of its ended is formally proven. As for the properties of the algorithm, we considered such important for linearization properties as monotonicity and preservation of the local order of inheritance. For these properties also there were no mathematical definitions, which made it impossible to prove their presence or absence in the algorithm. To formally define the properties of the algorithm, it was necessary to introduce the concept of a table inheritance hierarchy that describes both single and multiple table inheritance. Theorems about characteristic characteristics of single inheritance are formulated and proved. On the basis of the definitions introduced, the monotonicity of the algorithm MRO C3 was proved. The algorithm does not preserve the local inheritance order, which was shown in the corresponding example. As for the semantics of SQL, the table algebra of SQL semantic functions was improved. Note that this algebra has advantages over other ways of specifying SQL semantics. Namely, in table algebra two types of functions are distinguished: functions on tables, and functions on functions, which are called operators, as is customary in other programming languages. The semantics of complex SQL expressions in this algebra are naturally constructed from functions on tables and operators.