Database Reference
In-Depth Information
Let us define
y
∗
x
=
y
∗
x
y
&
x
. Let us show that for any
n
-ROI
M
,
M
∈
F
μ
, where
M
(x)
=
y
iff
M(
(x)
1
,...,(x)
n
)
=
(y)
1
,...,(y)
n
and
p
x
1
p
x
2
...p
x
n
,
y
p
y
1
p
y
2
...p
y
n
), and hence
l(y)
≤
n
(where
x
=
=
2
2
=
(x)
m
+
1
Res
M
(
x
)
=
Res
M
(x
1
,...,x
i
,...,x
n
)
M
=
x
1
,...,x
i
,...,x
n
m
+
1
.
M
The fact that
M
∈
F
μ
holds from the following structural induction on
M
:
...p
x
i
+
1
i
1
,...,(x)
n
=
p
x
1
···
p
x
n
;
2.1.
a
i
(x)
=
(x)
1
,...,(x)
i
+
(x)
1
,...,(x)
i
−
1
,...,(x)
n
=
p
x
1
...p
x
i
−
1
1
···
p
x
n
if
(x)
i
≥
1
;
2.2.
s
i
(x)
=
i
x,
otherwise
;
In
∗
E
(z)
2.3.
(x)
=
In
E
(z
∗
x)
=
(y)
1
,...,(y)
n
, such that for any 1
≤
i
≤
n
,
(y)
i
=
(x)
i
or
(y)
i
={
(z)
1
,...,(z)
m
}
,
m
≤
n
;
2.4.
M
1
M
2
(x)
=
M
2
(
M
1
(x))
;
2.5.
i
(M)
i
(x)
=
Iter(
M
)(x,y((Iter(
M
)(x,y))
i
=
0
))
, where
Iter(g)(x,k)
=
g
k
(x)
, i.e.,
Iter(g)(x,
0
)
=
x
,
Iter(g)(x,k
+
1
)
=
g(Iter(g)(x,k))
.
Thus,
F(
RMI
)
=
F(
RM
)
=
F
μ
, i.e.,
RMI
is a universal machine (like the Tur-
ing machine).
6.1.1 Major DBMS Components
The internal state of a DBMS is quite complex. From a high-level point of view,
however, it can be regarded as having just three major components, each of which
divides up into numerous subcomponents. The three major components are as fol-
lows:
1. The
system service
component, which supports system operation, operator com-
munication, logging, and similar functions.
2. The
locking services
component, which provides the necessary controls for man-
aging concurrent access to data.
3. The
database services
component, which supports the definition, retrieval, and
update of user and system data.
Of these three components, only the last is directly relevant to the user. That com-
ponent, in turn, divides into five principal subcomponents, which we refer to as
the Precompiler, Bind, the Runtime Supervisor, the Stored Data Manager, and the
Buffer Manager, whose functions are as follows (refer to Fig.
6.1
):
•
The
Precompiler
is a preprocessor for application programs that contain em-
bedded database statements. It collects those statements into a DBRM (Data
Base Request Module) replacing them in the original program by host language
CALLs to the Runtime Supervisor, both with the list of values used in SQL state-
ments INSERT and UPDATE (these initial values used in the original source pro-
gram may be successively modified by the program during its execution). The
host language is responsible for providing various non-database facilities such as
local (temporary) variables, computational operations, if-then-else logic, and so
