Use of Data Representation Mapping in Automatic Generation of Data Base Access Procedures
Proceedings of the Seventh International Joint Conference on Artificial Intelligence. Automatic Programming. Pages 1010-1014.
© 1981 International Joint Conferences on Artificial Intelligence
Abstract
Formal definitions of data structure mappings are given and are used to transform relational algebraic formula into data base access procedures which search a formally defined data structure. Especially, a hierarcical data structure is introduced to represent a set of relations which are inherently hierarchical. A retrieval procedure using data accesses along a two level hierarchy is obtained from an original formula on flat relations by applying equivalence transformation rules and data representation mappings.
- Backman, C. W. "Data Structure Diagrams", DATABASE (ACM SIGBDP Newsletter), 1, 2, 1969, 4-10. 2.
- Codd
- Codd, E. F. "Relational Completeness of Data Base Sublanguages", In Data Base Systems (Ed .
- R. Rustin), Prentice-Hall, 1972, 65-98. 3.
- Furukawa, K. Access to . Data Bases", ETL 804, 1979 (in Japanese). "On Intelligent Research Report No. 4.
- Hansson 79
- Hansson, A. and Tarnlund, S. A. "A Natural PrograiDIDing Calculus", Proc. Sixth IJCAI, 1979, 348-355. 1015 5.
- Hoare
- Hoare, C. A. R. "Proof of Correctness of Data Representations", Acta Informatica 1, 1972, 271-281. 6.
- Reiter, R. "On Closed World Data Base Systems", In Logic and Data Bases (Eds. H. Gallaire and J. Minker), 1978, 55-76.
- Yonezawa
- Yonezawa, A. "A Method for Synthesis of Data Base Access Programs", Research Report No . C-30, Department of Information Science, Tokyo Institute of Technology, 1980.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. INTRODUCTION
During the latest decade, data base theories and data structure theories have been developed independently. In data base area, much research has been concentrated on relational data base theories. As far as query processing is concerned, many logical query languages as well as deductive query evaluation systems have been proposed. Query optimizations and processing based on relational algebla have also been investigated by many
researchers.
On the other hand, theoretical researches on data structure have been developed in the field of program correctness studies (Hoare 72]. Recently, (Hansson 79] developed a framework to formally define data structures and prove correctness of programs manipulating them.
In this paper, we will combine the above two theoretical approaches and put them in a framework of data abstraction theory. Namely, we regard relations as objects of an abstract data type and relational algebra as its associated operations. Furthermore, we formally define data structures and represent relations by them. Our final goal is to transform relational algebraic query formulas into data base access procedures which search the defined data structures. Especially, we consider to represent a set of relations which are inherently hierarchical by a hierarchical data structure. We show that a retrieval procedure using data accesses along a two level hierarchy can be obtained from an original formula on flat
2. ~i2n ~ Relational Algebra
First, we define the relational data base formally.
Definition Let Dl, ... ,Dn be n domains (not necessarily distinct) of elements and Al, ... ,An be n identifiers which are associated with Dl, ... ,Dn respectively. A relation R on the set of identifiers {Al, ... ,An} is a subset of the cartesian product Dl x ... x On . Ai is called an attribute of the relation R. The relation R on the attribute set {Al, ... ,An} is denoted by R(Al, ... An).
We use A, B, ... for a single attribute and X, Y,... for a set of attributes (including the null
set).
Definition A relation type ~(A1, ... ,An) on the attribute set {Al, ... ,An} is a set of all relations on the set {Al, .·. ,An}.
A relation R(Al, ... ,An) is an element of the relation type ~(A1, ... ,An). A conceptual schema which determines the logical data structure is defined by a set of relatioR types. In this paper, we regard hierarchical data organizations to be matters of internal schema, which determine the physical data structure.
Fig. 1 shows an example of a relational data base where the conceptual schema is the set {EHP(emp, loc), ROOH(room#, sect)}.
Next, we define the relational operations ( (Codd 72], [Reiter 78]). algebraic
~~ Let R(A,X) be a relation . Then, the oro1ection 1T of R with respect to A is a relation given by the equation
Tf (R) = {x:Ez[<z,x> E R]} A
where x represents the sequence of values corresponding to the attribute set X and z the value corresponding to a chosen attribute A.

Definition Let R(X) be a relation, ~nd ¥ be a variable which corresponds to X. Let f be a logical function X-> {T,F} . Then, the selection of R with respect to f(¥), denoted by <1. (R), is f(X)
a set of ¥ values given by the equation
The selection operation ~J(.X)(R) is an associative retrieval of the relation R under the condition that f(x):T.
Definition Let Rl(A,X) and R2(B,Y) be and f(A,B) a logical function. Then, R1(A,X) and R2(B,Y) with respect to denoted by R1(A,X) ~ R2(B,Y), and relations, the ..1Q1.n. of f(A,B) is is given by
f(A,B)
If the join condition f(A,B) is given by an equality formula such as [loc = roomH], then a= b always holds in the above set expression and the answer becomes redundant. In this case, we remove one of the two attributes from the result . This modified join is called the natural join.

3. ~ TRANSFORMATION lHIQ HIERARCHICAL QAIA ~lZAIIQN
Fig . 2 displays the logical structure of the data base given in Fig. 1. This diagram is a Backman diagram and uses arrows to indicate one-to-many mappings ([Backman 69]). One-to-many mappings correspond to hierarchical relations and the arrows represent the access paths in hierarchical data bases; namely, subordinate data are retrieved by specifying the superordinate data and the access path between them .
Fig. 3 shows an example of a concrete tree structure which has the logical structure given in Fig . 2. Traversal from the root node in Fig. 3 corresponds to retrieval along access path "a" in Fig . 2. Given a piece of section information, we select an appropriate arc and follow it to reach the set of room#'s which belong to the section.
Let us assume that each set of room#'s forms a relation distinctively. We denote a set of room#'s under the selector "sect = ai" as ROOM . ai(room#) . This relation c~n be defined by a selection followed by a projection as follows:
ROOM. a 1( room/1)
~bove If we regard ai to be a formula defines any selector. variable, relation then the under any Next, we define a hierarchical data organization for the EMP relation similar to that which was defined for the ROOM relation. Let us denote EHP.bj(emp) to be a relation which comprises the employees who are located at bj. Then, the formula corresponding to (3.1) is given by:
Let us now consider the example query "Get all employees who belong to INFO section":
It has been shown in [Furukawa 79] that Q is equivalently transformed to:
The evaluation of formula (3 . 4) proceeds as follows: first, compute ROOM.INFO(room#) according to the definition (3 . 1); then retrieve EMP.bj(emp) for all bj in ROOH.INFO(room#); finally collect them together. This procedure is exactly the structural retrieval along access path comprising "a" and then "b" in Fig. 2. However, this access method is somewhat different from that of the hierarchical data bases. In order to retrieve all of the employees who are working in room bj, the above method relies upon the use of associativity rather than a pointer to access EHP.bj relation. Although associative retrieval can be realized very efficiently with hashing techniques and/or specialized hardware, it is still less efficient than the pointer access method. We will show further transformation of expression (3.4) based on the data stucture mapping to realize the exact access method of the hierarchical model.
4. IQHMAL DEFINITION Qf DAIA STRUCTURES .Alm f.RlM.~ FUNCTIONS
In this section, we formally define a hierarchical structure and its related primitive functions to manipul~te the structure. In defining a data structure, we adopt a framework developed by [Hansson 79].
First, we define a arbitrary components. list consisitng of
Vw{list(w) <--> w:NIL v ExEy[w:x.y & list(y)]}
Then, we define a selection list (slist) to represent a set of subrelations such as {EMP.r : r ~ roomf}.
Vw{slist(w) <-->
where~ is a membership predicate for slist and will be defined later.
This axiom defines a list of pairs whose first components differs from each other. We introduce the following useful lemmas concerning to the slist.
~ ~ slist(NIL).
VsVxVw{slist(<s,x>.w) <-->
Next, we define a membership predicate ~ as follows:
VeVw{e ~ w <-->
slist(w) & EhdEtl[hd=e v e ~ tl]}.
Like Axiom 2, we also introduce the following lemmas:
VeVw[e~e.w <-- slist(w)].
VeVhdVtl[ e + hd. tl <--
We are interested in representing using slists. The following axiom hierarchical data structure called slist structure or simply mls-structure slist. hierarchy defines a multi-level in terms of
Vw{mls-structure(w) <-->
Finally, we define a double list (dlist) whose components are all lists .
Vw{dlist(w) <-->
w:NIL v EhdEtl[w:hd.tl & list(hd) & dlist(tl)].
Now, we introduce primitive predicates and their corresponding functions for manipulating slists and/or dlists.
ill assoc(s.w.x)
"assoc(s,w,x)" corresponds to a LISP ASSOC function and is equal to "x ASSOC(s,w)". A formal definition of assoc is given as follows:
- Vs[assoc(s,NIL,NIL)].
- VsVxVw[assoc(s,<s,x>.w,x) <- slist(<s,x>.w)].
- VsVs'VxVx'Vw[assoc(s,<s' ,x'>.w,x) <- slist(<s' ,x'>.w) & s%s' & assoc(s,w,x)].
assoc(s,w,x) is very similar to <s,x> ~ w. They differ only when w is an empty list, where assoc(s,NIL,x) is true for x:NIL, but <s,x>~ NIL becomes false. Relations between assoc and ~are stated by the following two theorems.
Theorem 1
VsVxVw[<s,x> ~ w --> assoc(s,w,x)].
Theorem Z.
VsVxVw[-(<s,x> ~ w) --> assoc(s,w,NIL)].
12l prolect-sublist(w.w')
project-sublist(w,w') corresponds to a projection 1T of a relational algebra. It projects out first components of each pair of w and obtains w· consisting of all of the second components of the pairs. Formally, it is stated as follows:
Axiom l
- project-su~list(NIL,NIL).
- VsVxVwVw'[project-sublist(<s,x>.w,x.w') <--
- slist(<s,x>.w) & project-sublist(w,w')].
We denote a function corresponding project-sublist(w,w') as PRSUBL(w). to
ill prolect-selector(w.w')
project-selector(w,w') project-sublist(w,w'). The components and the second interchanged. is similar roles of components to first are
- project-selector(NIL,NIL).
- VsVxVwBw'[project-selector(<s,x>.w,s.w') <- slist(<s,x>.w) & project-selector(w,w')].
- A corresponding function PRSEL(w). is denoted by
1!1 dunion(w.w')
dunion(w,w') is a predicate which manipulates dlists and makes a list w' consisting of all elements of all components of w.
- dunion(NIL,NIL).
- VxVwVw'[dunion(x.w,APPEND(x,w')) <- dlist(x.w) & dunion(w,w')].
- A corresponding function DUNION(w). is denoted by
5. MIA ~\I.U MAffia!~. W FURTHER ~ T.RA.fi.Sf.Qii_liAIIQti
In order to represent ROOH.s and EHP.r using an mls-structure, we need to associate each room# in ROOH.s relations with EMP.r. We introduce a pseudo relation called HROOM.s(room#, Emp) where Emp is a pointer to an EMP.r relation. The original ROOH.s(room#) relation is obtained from HROOM.s(room#, Emp) by
ROOM.s(room#) = TT (HROOM.s(room#, Emp)) Emp (5.1)
We organize HROOM.s and EMP.r in a ROOM-FILE as shown in Fig. 4, where ROOM-FILE satisfies the following assertion:
Assertion 1 mls-structure(ROOM-FILE).
The mappings from ROOM-FILE to HROOM.s and EMP.r are given as follows:
Mapping 1 For any section s,
if Ex[<s,x> ~ ROOM-FILE] then HROOH.s Repr(ASSOC(s,ROOM-FILE)) else HROOH.s = ?·
From that any selection function relation. Assertion 1 and Mapping 1, it is shown non empty HROOM.s is represented by a list. Namely, the representation ~epr maps a selection list to a pseudo
Each EMP.r is then represented by a second component of some element of the selection list corresponding to an HROOM.s such that r belongs to s.

For any room# r,
- Vw{EsEx[<s,w> ~ROOM-FILE & <r,x> ~ w] -->
- -EwEsEx[<s,w> ~ROOM-FILE & <r,x> ~ w] -->
From Mapping 1 and 2, it is shown that the following equations holds:
Happing ~ For any section s, HROOM.s is obtained from
HROOM.s = ~epr(ASSOC(s,ROOM-FILE)).
Maoping ~ from For any room# r, EMP.r is obtained
We are now able to construct a mapping from ROOM-FILE to each ROOM.s:
rcpping ~
For any section s, ROOM.s is obtained from
ROOM.s = ~epr(PRSEL(ASSOC(s, ROOM-FILE))).
Now, let us consider how to transform the query (3.4) into a program which searches the ROOM-FILE mls-structure.
By applying Mapping 1" and 2' to (3.4), we obtain
Since the functional dependency room# --> section holds, r belongs to only one section (in this case, INFO), and "r t PRSEL(w)" becomes false for any other sections. Therefore, (5.2) is reduced to
(5.3)
Generally, a reduction theorem from (5.2) to (5.3) is stated as follows:
Theorem 1 Let M be an mls-structure, S be a constant corresponding to a first level selector of M and f be an arbitrary function. Then,
Since the range of r covers the entire set of all first components of pairs in HROOM.INFO, we do not need to search HROOM.INFO list for each r, but simply union all second elements of pairs in HROOM.INFO. The following theorem suggests us to use a DUNION function to compute the above union.
Theorem ~ Let W be an slist. Then,
~epr(DUNION(PRSUBL(W))).
By applying Theorem 4 to (5.3), we· obtain the following simple program to compute Q:
Axiom 6, 7 and 9 define ASSOC, PRSUBL and DUNION respectively. These axioms can be considered to be PROLOG program segments and can be executed directly. It is also possible to generate LISP programs by adding a suitable set of transformation rules and applying the same transformation methods as above.
6.CONCLUDING REMARKS
In this paper, we have represented a set of subrelations by a formally defined list structure and generated a data retrieval procedure which manipulates the structure given a higher level relational algebraic query formula.
The idea that we represent relations instead of tuples or values in tuples is closely related to the data abstraction concept. We do not care the detailed structure of each relation, which is another lower level problem to be solved separately.
We also have shown that during the transformation of relational algebraic formulas into data structure manipulation procedures, simplifications due to the structure are performed. We think this simplification process is very important in data abstraction theory.
[Yonezawa 80] has attacked a similar problem to ours in the frame of first order logic. Yonezawa has achieved a very neet method to generate recursive procedures for recursively defined queries.
Further consideration is needed to see whether our methods can be applied to the recursive case or not. We also plan to apply our methods to the
network case.
ACKNOWLEDGEMENT
The auther is grateful to Drs. Osamu Ishii and Akio Tojo for the opportunity to make the present study and to the staffs of the Information Systems Section and especially to Dr. Akinori Yonezawa of Tokyo Institute of Technology for their stimulus and helpful discussions.
REFERENCE
- [Backman 69] Backman, C. W. "Data Structure Diagrams", DATABASE (ACM SIGBDP Newsletter), 1, 2,
- 1969, 4-10.
- [Codd 72] Codd, E. F. "Relational Completeness of Data Base Sublanguages", In Data Base Systems (Ed . R. Rustin), Prentice-Hall,
- 1972, 65-98.
- [Furukawa 79] Furukawa, K. Access to . Data Bases", ETL 804, 1979 (in Japanese). "On Intelligent Research Report No.
- [Hansson 79] Hansson, A. and Tarnlund, S. A. "A Natural PrograiDIDing Calculus", Proc. Sixth
- IJCAI, 1979, 348-355.
- [Hoare 72] Hoare, C. A. R. "Proof of Correctness of Data Representations", Acta Informatica 1, 1972, 271-281.
- [Reiter 78] Reiter, R. "On Closed World Data Base Systems", In Logic and Data Bases (Eds. H.
- Gallaire and J. Minker), 1978, 55-76.
- [Yonezawa 80] Yonezawa, A. "A Method for Synthesis of Data Base Access Programs", Research Report No . C-30, Department of Information Science, Tokyo Institute of Technology, 1980.
@inproceedings{ijcai1981p193,
title = {Use of Data Representation Mapping in Automatic Generation of Data Base Access Procedures},
author = {Furukawa, Koichi},
booktitle = {Proceedings of the Seventh International Joint Conference on
Artificial Intelligence, {IJCAI-81}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Patrick J. Hayes},
pages = {1010--1014},
year = {1981},
month = {8},
note = {Automatic Programming},
url = {https://ijcai.org/proceedings/1981/193},
}
TY - CPAPER TI - Use of Data Representation Mapping in Automatic Generation of Data Base Access Procedures AU - Furukawa, Koichi T2 - Proceedings of the Seventh International Joint Conference on Artificial Intelligence, IJCAI-81 PB - International Joint Conferences on Artificial Intelligence PY - 1981 SP - 1010 EP - 1014 UR - https://ijcai.org/proceedings/1981/193 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: