Relational approach DBTG CODASYL proposal allow us to use better features of each component. We propose some supplementary operations over the data sets - the main construction of DBTG CODASYL proposal, which can be more effective in some cases, at least due to the fact that relational databases use mostly symbolic addressing, and databases with complex structures - mostly relative. As a result, user may choose among different types of data connections concerning the speed of their processing: slow but flexible, or fast but complex.
As well-known, the relational approach [
However, the transition from more complex structures to relationships means (at least for simple
queries) an impairment in processing efficiency, at least due to that relational databases use mostly
symbolic addressing, and databases with complex structures - mostly relative. Nowadays many
applications need to use BIG Data [
The selective Dribas algebra was proposed a few years after the appearance of Codd's relational algebra. Relational Codd algebra is more focused on theoretical aspects, and Dribas algebra is more convenient in sense of implementation and practical use. It borrowed set-theoretic operations of Codd relational algebra (union, intersection, and difference), as well as the Cartesian operation and project. In addition, 4 filtering operations were added. The operation of β-filtering Fβ (R, condition) is very similar to the Codd operation of -restriction, but in Dribas algebra the condition is an arbitrary formula without quantifiers with the attributes names from the relationship R and constants, which in practice is much more convenient than in the Codd case (comparing values of different attributes, but with the same sign and are combined only by conjunction).
The next filtering operation F (R1, R2, condition) is also similar to the Codd operation of -join. The difference is that the result of this operation is a relationship, the scheme of which is a copy of the relationship R1, and not the Cartesian product of two relationships, as in the classical case. In fact, the result is only those tuples from R1, for which there is at least one tuple in R2 that satisfies the condition. Again, we get a practical gain compared to the classic case. The operation F(R1, R2, condition) has no direct equivalent in classical algebra, but can be expressed through other operations and was added for practical reasons. As in the previous case, the result of the scheme is the copy from R1, and is filled with those tuples from R1, for which the condition is equal TRUE for all tuples from R2. For some queries, this operation is very convenient, and its implementation largely repeats the implementation of the previous operation. The most interesting and complex in terms of execution operation FS(R1,R2,A, BaC) is also a filtering operation, the result of which is some subset of tuples from the relation R1; A, Ba - lists of attributes from R1, and C - list of attributes from R2; is a binary predicate of set comparison: , , , , =, . First, R1 is grouped by the same values of the sub-tuples from list A, then R2 is projected by the list of attributes C; then each group of tuples, more precisely sub-tuples according to the list Ba, is compared (as a sets) with R2 [C]; if the condition is TRUE, then the corresponding group of tuples from R1 passes into the result.
The data set (DS) (after DBTG CODASYL [
Two data sets are of the same type if their owner records and all member records from both data sets are of the same type. The set of the same type of data sets forms the type of data set. Some datasets have only one Owner and an empty set of Member records. There can also be records outside of any data set, then we assume that such records are a Members of some DS, the Owner of which is a special SYSTEM record. Classical relationships can be formed from the same type of records with the SYSTEM owner, over which all operations of both Codd relational algebra and Dribas relational algebra are defined. Therefore, our proposed data model can be considered as an extension of the relational model, and the data selection language - as an extension of the relational algebras of Codd and Dribas. Records may or may not have a field similar to the primary key. Database key (DBK) for written records always exists, but it can be formed on the basis of the several fields, or calculated. Although firstly it seems that the DS has less expressive power than the hierarchical or network structure, but in fact each record can be part of several different DS both as owner and as a member, forming a data structure such as "network".
Consider an example of a subject area. First, we give its text description and ER-model (Fig. 1)
[
Now we give a description of the data domain according to the relational approach, i.e. each entity and relationship (type “many-to-many”) are represented by tables with the corresponding attributes:
We construct a supplement algebra based on DS, i.e. the arguments of the operations of this algebra will be DS, and the result will also be DS. Note that DS can be thought of as a function that matches each instance of Member (uniquely, but not mutually uniquely) to the instance of OWNER to which it is subordinate. Operations are focused on actions within the database, aspects of the interface will be considered separately. Data sets DS1 and DS2 must be the same type, the resulting DS will be of the same type. DS3. OWNER = DS1. OWNER U DS2. OWNER (without duplicates), Member sets are also combined without duplicates, but with subordination, i.e. if there are levels (matching DBK) records in DS1. OWNER and in DS2. OWNER, then in DS3. OWNER includes only one record, and many of their subordinate Member records are combined (without duplicates) and are subordinate to a common OWNER. This operation can cause problems: suppose that DS1 has an instance (O1, M1) and DS2 has the instance (O2, M1) then after reunion in DS3 we get the situation that M1 has two owners, which is forbidden, because it is not tree-structure; so in such situations UNION operation will leave only instance (O1, M1) in DS3.
Data sets DS1 and DS2 must be the same type, the resulting DS will be of the same type. DS3. OWNER is an intersection DS1.OWNER ∩ DS2.OWNER, in particular it may be empty, then the entire resulting DS will be empty; Member sets also intersect, but only those for which there are instances of OWNER; instances of DS with empty sets Member can be formed.
Data sets DS1 and DS2 must be the same type, the resulting DS will be of the same type. DS3. OWNER = DS1. OWNER \ DS2. OWNER, in particular it may be empty, then the entire resulting DS will be empty; for Member subtraction is performed on subsets subordinate to one OWNER.
TIMES(DS1, DS2) -> DS3;
This operation is defined everywhere and there is no requirement on types of data sets. DS3. OWNER = DS1. OWNER DS2. OWNER, instances of Member also multiply among themselves, but only within the limits of subordination to their OWNER.
Olist is a list of fields for OWNER, and Mlist is a list of fields for Member. Obvious limitation: Olist must be a sublist of fields DS1.OWNER, and Mlist - a sublist of fields DS1.Member. The expression [ ] means an empty list of fields, and the expression [*] means that all OWNER or Member fields are in the list, depending on whether the expression is in the 2nd or 3rd place. In the future there will be deviations from the classical algebraic style, but this is only for more convenient use; this technique was used by E. Codd when he introduced relational algebra operations. Besides the overall case of the PROJECT operation we’ll also use some special cases: PROJECT-OWNER(DS, [Olist]) > R; and PROJECT_Member(DS, [Мlist]) -> R; For both operations their result is not DS, but relationship; if a member of a data set is a DS, the result of such operation will be a relationship (according to the list Mlist), which is a Member of the last DS. 5.1.
β-filtration ВFilter(DS1, condition) -> DS2;
DS2 has the same type as DS1 and is populated with data from DS1 that satisfies the condition. The condition is a formula with fields from both OWNER and Member, constants, and some unary predicates, for example: EmptyMember (NotEmptyMember) returns TRUE (FALSE) if there is at least one instance of Member for the current OWNER instance. The condition verification is valid within one instance of the data set.
DS3 has the same type as DS1 and is populated with data from DS1 that satisfies the condition if there is at least one such instance in DS2. The condition is defined in the same way as in the previous operation, but fields with DS2 may also be present in the formula. Condition verification is valid within one instance of DS1.
DS3 has the same type as DS1 and is populated with data from DS1 that satisfies the condition if it is executed for all instances of DS2. The condition is determined in the same way as in the previous operation. Condition verification is valid within one instance of DS1.
- it is the operation for set comparison. DS1, DS2 and DS3 are data sets, and the resulting data set DS3 has the same type as DS1;
AOlist and BOlist are attribute lists from DS1, and AOlist is attribute list from DS1.OWNER and BOlist is attribute list from DS1.Member; COlist - list of attributes from DS2. Member; is a binary predicate of set comparison: , , , , =, .
The order of actions is such: a) a set of instances of DS1.OWNER is grouped by AOlist; b) DS2.Member is projected by C; c) from the groups {R1AOlist} are selected those instances for which the condition BOlist COlist is fulfilled;
d) into the resulting DS3 passes only those instances of DS1 that meet the specified condition. 5.2.
This operation joins two data sets DS1, DS2, which are neighbors on the hierarchical path. D (DS1. OWNER) = D (DS3. OWNER) – this means that their domains are equal; D (DS2.Member) = D (DS3. Member) and D (DS1.Member) = D (DS2.OWNER). Namely, from the 2 two-level trees is constructing three-level tree with subordination saving, then the intermediate level is removed and again we get a 2-level tree; by means of a condition the necessary copies are selected; the condition may include constants and fields of all records from DS1 and DS2.
Such type of operation will be appropriate when there is another DS on the hierarchical path between DS1 and DS2; its OWNER will be the same type as DS1.Member, and its Member will be the same type as DS2.OWNER, then we will get DS3, such as D(DS1.OWNER) = D(DS3.OWNER), and D(DS2.Member) = D(DS3.Member).
Another one specific type of connection, oriented on the situation when DS1 and DS2 have a common Member, which implements a connection between two objects of the type "many-to-many" (ER-model). The result will be a relationship that is DS1.OWNER and satisfies the condition.
For this operation DS2.OWNER = DS1.OWNER, but instead of the DS2. Member for each OWNER the corresponding quantity of elements is substituted.
REC1 and REC2 are the records (or more exactly relationships) from which DS1 is formed, REC1 is forming the OWNER of the data set and REC2 is forming its Member. REC2 must have an attribute (or group of attributes) that is a foreign key, and for REC1 it is a primary key. Symbolic addressing between such relations will be transformed to more efficient relative. The condition is required to specify such attributes.
adds a REC record to the DS as a Member; condition is used for specification as in previous operation. This operation is convenient when we need to add some record to the data set and connect it with some particular owner; such connection is specified by condition.
Let us consider a few examples of queries in the subject area, which was described earlier (Table 4 – Table 10). Each query will be presented in natural English, in terms of the original Dribas algebra (left column) and by means of proposed supplement algebra (right column).
The proposed extensions to classical relational algebra allow us, on the one hand, to increase the efficiency of query execution, and on the other hand, to reduce the gap between DML and SQL. From the given examples it is seen that the notation of some queries in terms of the proposed algebra looks more compact.
Find hospital names and address for the hospitals with rank = “xxx”.
Fβ(Hosp, Rank = “xxx”) -> R1; BFilter(HD, Rank = “xxx”) -> DS1; R1[Hname, Hadress] -> res; PROJECT-OWNER(DS1,[Hname, Hadress]) -> res; For such simple query proposed algebra has no benefits in comparison with traditional relation algebra.
Find department names and hospital number in the hospitals with rank = “xxx”.
Fβ(Hosp, Rank = “xxx”) -> R1; BFilter(HD, Rank = “xxx”& NotEmptyMember) -> F( Dep, R1,Dep.h# = R1.h#) -> R2; DS1; R2[Dep.h#, Dname] ->res; PROJECT (DS1, [h#], [Dname]) ->res Supplementary algebra uses one operation less than relational algebra.
Find the chamber names from hospital №1, where there are no patients with a temperature > 37 (Fβ(Pat, temp >37)) -> R1; BFilter(CP, temp >37) -> DS1; (Pat \ R1)[c#] -> R2; F(Ch, R2, Ch.c#=R2.c#) -> CP \ DS1 -> DS2; R3; R3[Cname] -> res; PROJECT(DS2, [Cname], []) -> res; Relation algebra has 4 operations while proposed algebra needs 3.
Find the patient names consulted by Dr. Sidorchuk.
Fβ(Ph, Pname = “ Sidorchuk ”) -> R1; JOINMember(PCon,PhCon, PCon.Con.r# = F(Con,R1,Con.p#=R1.p#)->R2; PhCon.Con.r# & PhCon.Ph.Pname = “ Sidorchuk F(Pat,R2, Pat.t#=R2.t#) ->R3; ”) -> R1; R3[Tname] -> res; R1[Tname] -> res; This query is performed on the base of connection of “many-to-many” type.
Find the patient names who are consulted only by those physicians who consulted the patient “xxx” by name. (Fβ(Pat, Tname = “xxx”))[t#] -> R1; Join*(PatPh, PhPat) -> DS1; F(Con,R1,Con.t#=R1.t#)->R2; OnlyFilter(DS1,Member.Tname=”xxx”) R2[p#] -> R3; Con[p#,t#] -> R4; Fs (R4, R3, t#, R4.p# R2.p#) -> R5; F(Pat,R5, Pat.t#=R5.t#) ->R3; R3[Tname] -> res; This query is performed on the base of connection of “many-to-many” type. OnlyFilter operation is the special case of the SetFilter operation; it is equivalent to SetFilter (DS1, DS1.Owner, DS1.Member, , condition). Its running algorithm may be the follows: firstly we mark such memberrecords for which the condition is FALSE and then for each owner-record its subordinate records are verified while marked one is appeared. If it will be no marked records among the subordinate records then such owner-record should be added to the result.