\

An integrated fact/document
information system for officeautomation
Esen A Ozkarahan and Fazli Can*

After a review o f the needs o f office automation, an
integration model o f an experimental system fo r testing
various concepts is presented This system aims tosynthesize a relational database management system(DBMS) and document retrieval system (IR) capable o fcontext sensitive fu ll text searches. The IR system relies
on a clustering subsystem fo r database partitioning andrelation fragmentation. Conceptual data modelling,
forms interface, and query execution in the distributed
database constitute the support architecture o f theintegrated system. Underneath, the support architecture,
there is the integrated D BM S/IR datastructure andinstruction set Efficiency o f the integrated system is
discussed including a future extension that involves theR A P 3 database machine hardware. RAP3 combines theterm matcher and query resolver subsystems.
Keywords: computer networks, database management
systems, database machines, distributed databases,
document clustering, document retrieval, fu ll text
searching, integration o f D B M S/IR office automation

IN T R O D U C T IO N
The need to integrate various facilities of information pro­cessing is generally well recognized. This need isexpressed more profoundly as the advances of thepresent-day computer technology are making things that
could not be done in the past a reality today. The network
Department of Computer Science, Arizona State University, USA^Department of Electrical Engineering, Middle East Technical
University, Ankara, Turkey
Received: 12 March 1984

142

information system foreseen by Salton1 is described as a
network of different information facilities such as the
document (or information) retrieval (IR), databasemanagement (DBMS), data analysis, citation indexing,
and text processing systems. Van Rijsbergen2, in his
statement of the future research problems, foresees the IR
and DBMS integration and stresses the fact that such an
integration will be driven by the needs of officeautomation. Also, there have been various studies in the
DBMS area to augment a DBMS with some IR
functionalities3,4’5. In the IR area, there are commercial
and experimental systems such as DIALOG, STAIRS,
BRS, MEDLARS, M EDLINE, ORBIT, The
Information Bank, LEXIS, W ESTLAW , SMART, etc.,
which are surveyed in6,7, that display the past and present
state of the art in IR.
H ow to integrate IR and D B M S
As the users of the information processing community areprovided with more capabilities, we see that the informa­tion structures and data manipulation requirements ofapplications are getting more and more sophisticated.
This would mean that an information scientist responsiblefor data definition and creation will be faced with therepresentations of complex relationships of facts as wellas documents. We can immediately realize that pastefforts that simplified the integration problem by confining
one system within the framework of the other or simply
combining IR and DBMS in a semantically disjointmanner will not be sufficient, effective, or efficient within
the context of the requirements of present applications.
We cannot merely incorporate some string operations intoa DBMS data language or store keywords as an attributeof a formatted database. We cannot implement DBMS

0144-817X /84/030142-15$03.00 © 1984 Butterworth & Co (Publishers) Ltd

information technology

functionalities as file programs embedded within an IR
system. Such an effort would lack the advantages of
DBMS such as data independence, real time response,
and ad hoc query formulation capability. On the other
hand, the unique features of IR cannot be fitted into thedeterministic, non-iterative nature of DBMS data
manipulations.
The answer for the proper integration lies in a synthesisthat will combine IR and DBMS by preserving theirunique features in such a way that the advantages of both
systems can be shared. In such a general purpose system,
one would like to see conceptual data modelling,
relational algebra power (or equivalent) of DBMS, and at
the same time, automatic indexing and classification(clustering), partial and/or full text search, and query
feedback features of IR
O ffice autom ation
Office automation is a relevant target application that can
tap the resources of an integrated information system —not only relevant but also with immediate prospects for
exploitation in real life. We can define office automation
as the pioneer of a (relatively) paperless society. This isbecause, with office automation, we are not merely
automating manual systems of the present but introducing
a new model for the office of the future. In such a model,
we see electronic mailing, automatic forms handling, form
driven database manipulation including full text
processing. Because an automated office will embody
workstations distributed throughout an organization, we
can envisage a local network of workstations.
In the model of an automated office, we can describe
the following: on the user resource network level, we havevarious modem office equipment linked to workstations.
Workstations, in addition to their local intelligence, will
be tied to network servers. User’s interaction with thesystem will be via forms and electronic mail handlingfacilities. These facilities will be supported by a
distributed environment of integrated information system
onto which the forms processing system is mapped. Morespecifically, in this model, we see distributed databases inwhich DBMS and IR are integrated. For automatedoffices, besides formatted data of DBMS, processing of
unformatted data in the form of full text searching is very
important The latter would fall within the realm of IR in
which document classification, indexing and keyword
based retrieval would be supported by the databaseserver, whereas the full text processing capability would
rest in workstations. In hardware description, aworkstation can be a powerful microcomputer linked to
the network server through the local network. The
network server can be a powerful mini- or mainframe
computer. One can think of cascaded local networks ofsuch systems for larger environments.
The purpose o f this research
The purpose of our research is to define a model of an
integrated fact and document information system and to
implement an operational experimental system in which
various components of this model can be tested. We
believe that the benefits of such an integration would be
multifold. We cannot only gain insight into the integration

vol 3 no 3 1984

issues and problems, but also experiment with theindividual components of the system such as database
design, network query execution, forms interface, and fulltext processing in conjunction with cluster based retrieval.
Because full text processing is important for specialized
applications such as law, medicine, etc., we consider the
inclusion of context sensitive, full text processing in the
integrated information system model important This does
not preclude, however, keyword based document retrieval
incorporating clustering at the network server level. In
fact, in the proposed environment, the upper hierarchy of
the unformatted retrieval rests within the database server.
As a tool for DBMS in our system, we will utilize the
RAP relational DBMS (which will be introduced in thesequel) because of the following three important reasons:• RAP relational DBMS goes beyond implementing
string processing within DBMS. It supports
associative, context sensitive, text search operations
based on internal string processing as primitivecommands of the DBMS.
• Besides its efficient software implementation, which
can be compared with other existing systems, it has theoption of being mapped onto the hardware of adatabase computer.
• Third but not least, it is the available facility which
can easily be serviced and altered, if necessary, byourselves.
In the remainder of this paper, we will present themodel of the proposed integrated information system. In
this model, we will see the abstract view of the query
processing environment at various steps of processing
from the input to the delivery of results. This will befollowed by the description of the underlying support
system structure. This involves the distributed databasearchitecture, conceptual data modelling, and the handlingof unformatted structures. Because of space considera­
tions, we will try to keep the discussion at the descriptive
level.
The support system structure will be followed by thedescription of the operational system that runs on the
support system. The context sensitive full text operations
using RAP will be demonstrated.
In the performance section, we will address theefficiency of the proposed integration model. While theperformance of a pure software approach will reach a limit
at some point, the potential performance improvements oftext retrieval hardware will set the ultimate goal. This willbe the topic of the final section.
IN T E G R A T IO N M O D E L
In the integrated information system, a common
framework has been established for the physical datastructure so that both formatted and unformatted data canbe manipulated together under an instruction set that
embodies DBMS as well as context sensitive, full text
processing power. A given user request such as
On the documents written by the authors who arereferenced by the papers written by JO H N DOE after
1970, search for those with the phrase SEMANTICDATA M ODEL and AG G REG A TIO N
would require both DBMS and IR specific operations in
an interrelated sequence of processing steps (see below).

143

In the notation that will follow, a user query such as theone quoted will be denoted as Q, whereas the subsets of it
dealing with DBMS and IR will be indicated by QR and
Qt respectively. QT is the portion of the request that deals
with the context sensitive search such as the SEMANTICDATA M ODEL and A G G R EG A TIO N in the samesentence. While QT will be preserved for final processingin the workstations, a query called the system query Qs
will be derived from QT to initiate a search of the relevant
clusters in the database. This search is carried out by the
database server on the network in an effort to narrow the
search space, before the full text search can be conducted.
In simple terms, a Qs query will include those terms ofQ t that are included in the set of index terms of thecollection with a possible inclusion of certain othercomponents to increase system precision and/or recall.
Figure 1 shows an abstract view of the query processing
environment With Qs, a hierarchy of clusters will besearched and the corresponding data DQS will be returned
when the cluster search is optimally terminated. The two
resulting sets of data, DQR and DQS, corresponding to
DBMS and IR operations, respectively, will be jointly
processed by the integrated system to produce the user’s
response. The user, screening this response, may ask thesystem to repeat the operation by providing an indicationof the relevant/irrelevant documents. With this informa­tion, Qs will be modified and the previous cluster selection
will be refined.

among themselves and/or with those of R also will bepresented in the conceptual datamodel.
Q is a set of user queries. A given query, Q, isdefined as

Q = {Qt Qr }where QT is the part of the query that holds the context
sensitive, document search specification.
Qr is the part of the query that holds search specifica­tion on the (R, D) set operable by the DBMS instruction
set As can be seen, the simplistic implication of QR -*(IR on D) and/or (DBMS on R) is not always true. As
shown in the example of the previous section, a searchnavigation threads through bothi? andD several times in
an interrelated manner. This is an important point thatshows that the integration is not achievable by a simple
coexistence of two different systems in a semanticallydisjoint manner.
C is a hierarchical structure of clusters for D.
E is a mapping function, called the evaluation function,
E:Q -» 2°, used to find the relevant documents to a query.
In reality, a subset of the range of this mapping is reachedthrough the complex operations of clustering, building
hierarchies of clusters, implementing search functions forthese hierarchies, and using feedback. All these opera­
tions will be briefly discussed in the following.
T represents the terms used for the description of
documents.

M athem atical m odel o f query processing
The integrated information retrieval system, IS, consistsof a set of hierarchies and is described by a 6-tuple:

IS = <R, D, Q, C, E, T>
where R represents a set of relations which containstructured data about the documents or document entities.
The nature of the interrelationships among the structured
entities will be described by means of a conceptual
datamodel.
D represents the set of documents stored as unstructured
entities. The relationships of these unstructured entities

Creation o f system queries
As shown earlier, a query Q consists of two parts Qt and
Qr where QR is the relational DBMS operable subqueryand Q t corresponds to the context sensitive, document
retrieval subquery. Related with QT, there are a set ofwords, T q , such that:T q n T C Tu T2, . . . , Tn where n = |7’| > 0
We cannot expect all of T q to appear in the filteredsearch query (system query) for the simple reason that not
all of the words would be included in T since there areconditions for a word to be an (index) term8,9. In QT, someterms will be used in the positive context, some others in
the negative context, and some in both. For the reason thatwill be clear in what follows, QT, therefore, will be
expressed as:

Q t = Qtp U Qtn
where QTp and Q tn correspond to the parts of Qt thatdeal with the terms specified in the positive and negative
context respectively, andQ tp
IT tp = T\, T2, . . . , Tk\ k > 0
Q tn
I TTn = T\, T2, . . . , 7) | l > 0, k, l < nand k = l is allowed.
In the filtered search query for Q t , which will be called asystem query Qs, there may be positive and negative term
specifications. If a term T{is a member of both sets, that is:
Tj (z T tp and 7/ (z T tn
Figure 1. Abstract view o f the query processing environ­
ment

144

then Ti appears as a positive term in the system query.
This selection is due to the fact that the information pro­vided by the appearance of a term rather than its non-information technology

appearance is more important10. Therefore, a system
query, Qs, is:Qs = Qsp U Qsn where
Q sp = Q tp

Qsn = Q tn — ( Q tn H Q tp)
Hence, for the respective terms:\TSP\ = \Ttp \, |7 sat| < | 7W | and \Ts\ ^\Tt \This is reasonable since, as stated earlier, one cannot
expect all the words used in a context sensitive searchrequest to appear in the terms used for indexing.

called cover coefficient8, 9. The starting point is adocument ( m ) by term (n) matrix, D, of m by n for m
documents { d \,d 2, . . . , dm) in the collection; n is the total
number of terms assigned to describe the collection. The
vector entries can be binary or can use a weighting
scheme. The process will produce p cluster partitions p ={Ci, C2, . . . , Cp} where C, will be a non-empty cluster andC, n Cj — 0 for i 7+ j,l < i, j < p (i.e., no overlap). Eachcluster C, will have /,■documents C, = (d(1, d,2, . . . , d(/)
such that li > 1 andp
E /, = m/-I
The properties of the D matrix are:Context sensitive B oolean query structure
The user query Q will be processed as follows:• The query Q will be converted into a disjunctive
normal form, i.e.,

Q = ( Q u A Q l2A . . . A Q lni) V . . . V ( Q mlA Q m2A■■■A QmnJ
where each Qij(i — 1, . . . , m \j = 1, . . . , nm) may be asingle word or a context sensitive, document retrieval
operation of one of {(A B) in Sentence, A . .. B, A.n.B,<A, B>n, A1V.B, A *B , . . . } as will be discussed later.
Furthermore, each Qy may be either in a positive or
negative context (e.g., —» (A, B) in Sentence implies(A, B)

in Sentence.)• From the resulting query, a list of subqueries will be
generated such that they will be in an ordered
quadruple < QR QT Qs, Qsr> where QR and QT are
as explained before and Qs and Qsr are obtained in thefollowing steps.
• The words used in QT will be searched in the thesaurus
corresponding to the terms used in the clusters. Non­matching words will be dropped and the query, now left
with only the terms, will be a system query Qs.
• Concept hierarchies, continuous word phrases, and/or
citation linkages will be the possible candidates ofadditions to Qs if expansion due to recall and precision
will be necessary in the course of the experiments.
• Qsr, referring to Figure 1, is a further retrieval opera­tion on DQ r and DQs and the answer set returned by it
can be expressed as:

A Q sr) = ft^lDQxfQiiDQs))
In other words,A Q sr) is the data returned by a further
retrieval function operating on the product of thedatasets DQR &ndfQi{DQs), which correspond in turnto the data returned by QR and the context sensitive
operations of QT executed on the dataset returned by
the hierarchical cluster system search.
• Qsr is repeated through the feedback loop (if necess­ary) until the user and/or certain performanceindicators are satisfied.
In the above procedures, A Q sr ) QD will be always
true.
Clustering subsystem *The clustering subsystem uses a seed oriented,
partitioning type classification based on the new concept*The reader may like to omit this section on first reading.

vol 3 no 3 1984n•

2 dr, > 1 1 < / < m, i.e., each document is desj= icribed by at least one term.

•

E djj > 1 l < j < n, i.e., each term describes atmi— 1

least one document.
The D matrix is mapped into a cover coefficient matrix,
C. The C matrix indicates the extent with which the docu­
ments of the collection cover each other. If a document isalone (i.e., unique in the collection), there will only be a
diagonal entry for it in the C matrix. The C matrix is m by
m, a document by document matrix. Each diagonal entry
in this matrix is the decoupling (uniqueness) coefficient,whereas the sum of the off-diagonal entries yields thecoupling coefficient of a document, corresponding to a
row in the matrix, with the other documents in thecollection. The coupling coefficient enables us to estimate
the number of clusters needed for the collection andcalculate the cluster seed power for the documents.
Clusters start with the seed documents and the otherdocuments are assigned to the seeds in such a way that adocument joins the cluster whose seed covers it
maximally.
The C matrix is formed as follows. Two matrices S and
S' are defined from the D matrix as follows:rtm

Sij = dij/ ( E dik), s'ij = dfj/ ( E dk) for 1 < / < m
k= 1

k= 1

J

and 1 < j < nThese normalizations can be interpreted as:
Sij\ significance of term-/ (tj) for document-/(d,)
Sjj: significance of dt for tj
The C and C' matrices are then obtained as:
C = S x S' T and C' = S ' r x S
where r is the matrix transpose operation. The C and C'
matrices are m by m and n by n, respectively. An elementof C is obtained as:nn
Ca= E sikx ski'T= E (significance of tk in d,) x
k=\

k=\

(significance of d, for tk)
Each Cy is a cover coefficient that produces, as indicatedearlier, the decoupling and coupling coefficients. The
properties of the C matrix are:• 0 < cy < 1, c„ > 0: a document may or may not becovered by other documents, it is certainly coveredby itself.

145

m
E Cjj = 1 for all / 1 < i < m : each row sum is equalj= i
to 1 and the sum of all row sums gives the total docu­
ments, m, of the collection.
• For all i, j, 1 <i, j < m, c„ > cy if the D matrix isbinary; c„ can be less than cy in a weighted representa­
tion. If di is unique, then cy = 0 and Cy = 1 (or w„
weight). A document is covered mostly by itself, others
can cover it as much as itself.
• Cjj = 0 implies Cy, = 0 , and cy > 0 implies Cy, > 0 .
However, in the latter case, it is generally cy X Cjj.
Coverage is mutual, however generally, not symmetric.
•

The decoupling coefficient 5, of c?, is Cy; 1 < / < m, andmthe coupling coefficient is t/y = E cy = 1 - 8 , where/= li t* j. A document that shares a large number of termswith the other documents will have a large ipj, but a low 8,
value. Coupling and decoupling can be computed for theentire collection as:m(m m \
8 = E 8j / m, i//= E E cy / m = 1 - 8 where,-=iv = iy=i/i ^ J '■The values of 8 and i[/ range between 0 and 1.
By using the C' matrix, we can cluster terms andproduce the measures 5/, ip(, 8, i]/ in thesaurus con­struction.
The theoretically implied number of clusters, nc,
needed for the collection can be produced as:
nc = (decoupling coefficient of the collection) x(number of documents)“m= 8 x m = E 8,i= 1
(Similarly, the number of term clusters, n'c is S' x n)
The average number of documents per cluster, d c, isgiven by dc = m / { 8 X m) = 1/5.
The cluster seeds are determined by a new concept
called the cluster seed power. The cluster seed power, pj,
nof document-/ is obtained as p, = 5, ^,-r, where /, = E dyi= 1
is the number of terms in the document description
vectors. In pj, 5, contributes to the separation of clusters,i[/( contributes to the connection among the members of acluster, and provides normalization.
The documents are assigned to the cluster seeds withrespect to either a single pass or a multi-pass algorithm. In
the single pass algorithm, what is done mainly is:• Determine the first n c cluster seeds from the firsthighest py• Repetitively do: if d, is not a cluster seed then find thecluster which maximally covers it, i.e., max(efs) where
Sj, 1 < j < nc, is the seed documents.
• For the remaining unclustered documents, either forma ragbag (common) cluster or compare the documentswith the documents of the clusters already formed tofind a maximal cover for each document and add the
document into the respective cluster.
In this clustering process, the estimated number of docu­
ments in cluster-/ initiated by the seed ds. is «, which is
given by:"c= (Pi/ 2 Pk)*m for 1 < / < nc

k =l

146

In the forming of centroids for the clusters, a centroid
Gy = (giugn, ■■■,gin), 1 < / < nc, is constructed byapplying the state of existence rule for each^,y This rulestates that a centroid entry will be 1, iff]8j > fjavg8' holds,
otherwise 0 where:f j is the frequency of tj within the document vectorsof cluster-/.
fjsyg is the average number of occurrences of tj within
the cluster containing it It is the document frequency
mof tj (ie., E dy) divided by the number of clusters/= 1
whose document vectors contain tj.
8'j is the diagonal entry of the C' (i.e., S ’TX S) matrix
for tj, which indicates the uniqueness of tj.
8 is the overall decoupling coefficient of all the terms.
The existence rule can be made to emphasize term
uniqueness in a varying manner by introducing a multiplierr into the condition (i.e.,/-5y > r/)avg8 ).
In this clustering scheme, we have the advantage ofknowing the number of clusters needed for the collection.
The document distribution in the clusters is rather uniform
and clustering is order independent This is because thecover coefficient has no dependence on the arrival of
documents. The complexity, similarity and stability
analyses of the clustering scheme can be seen in otherdetailed publications8,9’1 .
Cluster hierarchy
Once the clusters are formed, the database server cansearch them by comparing the centroid vectors with thatof Qs returning DQS for the full text search. If, however,there are a very large number of clusters making the linear,
single level, cluster search prohibitive we can construct a
hierarchy of clusters (tree), HCT for a sublinear
search. Also, in dynamic environments of very large
databases where clustering becomes a bottleneck, we canselect a sample of documents and construct a HCT of coreclusters as discussed in10,12. The remaining documents
can be assigned to the nodes of this HCT by using thesame search strategy applied for user queries.
In our case, we can easily compute the theoretically
implied number of clusters, nc, for the collection with aprocedure of 0 (mnavg) complexity9, where «avg is theaverage number of terms in the documents. In the searchof the HCT, we may stop at an intermediate node, as will
be seen in the search strategy to follow. However, weshould get to the lowest level (leaf) cluster under that node
to add the document being processed. In such cases, we
can pick the cluster with the maximum cluster seed
power for the seed document.
In the mathematical model, C represents a hierarchicaltype cluster structure forD with / levels. This is shown in
Figure 2. In this structure, if a node c, has n children
Cn, c/2, . . . , c,„, then the documents contained in c,are:

D C = D CXU D c . U . . . U D cFurthermore,

D cy Pi D cik = 0 (null) for j ^ kwhich leads toD ci Cl Dcik

D cik

information technology

Accordingly, in this search, we may send multiple
nodes from different branches of the tree to full text
search.
M atching function

Figure 2.

Hierarchical clustering

These properties hold for all levels because the clustering
algorithms used are non-overlapping.
As to the terms, if Tci is the set of terms used for thedescription of the centroid of cluster c* then
TciJ D Tcik = 0 is not necessary true for j ^ k since agiven term can also be used in the description of docu­
ments in a different cluster. Similarly, Tcii U Tci2 U . . .
U Tein = Tci is not necessarily true for any i where1 < i < l for an l level hierarchy because we cannot
assume that all documents on both sides of therelationship are isomorphic.
The hierarchical document cluster implies a partial
ordering relation. Assume R is a generalization relation
for all the documents related with node-i R will be thegeneralization of both the documents of the node as well
as all the documents contained in the descendants of that
node since the following conditions of reflexivity,
antisymmetry, and transitivity will be applicable:• Every node c, is a generalization of itself by reflexivity,

CjRcj.
• If CjRcj and CjRci then this implies that c, = Cj (anti­
symmetry).
• If CjRcj and CjRc^ then this implies that(transitivity).
Cluster search
The nodes of the cluster hierarchy and the system query,Qs, will be represented as vectors equal in length to that ofthe document definition vectors. In the query definition
vector corresponding to Qs, each element can have one of
the three possible values of 1, —1, and 0 corresponding to
the use of the related term in the positive context, negative
context, and non-use of it, respectively. As stated earlier,terms appearing in both contexts are assumed to be in thepositive context The search process will employ a top
down search on a search tree. Depending upon the valuesof nc and dc, and the required precision/recall levels, thefollowing two search strategies will be experimented with:• Narrow search: at each node, the descendant that gives
the highest value for the matching function is taken.
The search terminates when none of the descendants ofthe processed node can exceed in match function valuethat of the node10. With this strategy, we always take asingle branch out of a node.
• Broad search strategy: from a node, descend tochildren nodes that satisfy the match criterion (e.g., asimilarity threshold). Stop when no child satisfies thematch and send the parent to full text search.

vol 3 no 3 1984

Two measures are being investigated for the matching
function. One is the coupling function and the other is asimilarity measure. The coupling function comes from theidea of the coupling coefficient in our clustering scheme.
Accordingly, we can start with an m by n matrix D qc
whose first row would be the query vector and theremaining m- 1 rows would correspond to the centroid
vectors of the lower level subclusters of the node(s)identified in the search of the HCT. By obtaining the covercoefficient matrix Cqc corresponding to the D qc matrix, we
can produce the coupling values. A query would be coveredby itself (i.e., cqCj. > 0 ) and the centroids identified as aresult of the HCT search. Those cac..
H'-tj that exceed athreshold would identify the centroids of the target
clusters.
The second measure would be a similarity function of
the following form:' SIM(Q& C) = ^ i i F 1(qj, c ; ) J / ^ § i (F ,(?> cj)+ F 2(qj, cj)) |where
if qj > 0
{Vi x Sj
if qj = 0
F M j. cj): 0( abs(<7y) X ( |c| - g j ) if qj < 0(1)

f « / x ( M - gj) if qj > 0
if qj = 0
Filqj, cj): 0( abs(^y) x g j
if qj < 0

(3)

(2)

(4)

In (1), we are saying that if a query term, qj, position is a
1, then F\ gives the number of documents containing thatterm under that centroid; gj is the centroid entry. In (2),| c | indicates the number of documents under the node,
abs means absolute value and F\ gives the number of
documents that do not contain the negative query term. In(3), F2 gives the number of documents in the nodes that do
not contain the query term. In (4), F2 gives the number of
documents in the nodes that contain the query term. The
S I M function is the conditional probability of hitting a oneon the centroid vector of the HCT node given that a one
was given in the query vector and hitting a zero on thecentroid vector of the HCT node given that a minus one
was given in the query vector.
Q uery feedback
The query feedback to be explored in this research differs
in some respects from the other studies. This difference
is motivated by the very fact that the integrated system
will be concentrated on the context sensitive, search
specifications of the type discussed in this paper. Accor­
dingly, in this feedback scheme, the user query is kept
fixed, but the system query, Qs, is modified. There­
fore, after each feedback process, a new cluster is chosen,
which would be most related with the modified Qs,
and the documents are processed with respect to Qr(and Q sr later). The feedback process will depend on the147user choice although various measures of performance
also will be employed. The user will have the choice of
accepting the results or triggering the feedback loop by
giving an indication of the relevant and irrelevant
documents. In the refinement procedure of the feedback
subsystem, the terms appearing in the relevant documents
will be emphasized while those in the irrelevant
documents are de-emphasized. The following criteria canbe used for this purpose. If | qlx | denotes the number of
appearances of term-/ in set x where x can be one ofsystem query, relevant documents (R L ), or non-relevant
documents (NR), then if

Itf/sl + \<Ur l \ >\<]Fn r \• AUTHOR and DOCU M ENT entities are related
through the DOC-REF relationship in a many-tomany manner. That is, an author can reference several
documents and can also be referenced by several docu­
ments.
• A specific journal is published by one publisher, yetthat publisher can publish several journals.

jthat is, if the sum of term -fs used in the positive context inthe system query and those that appear in the relevant
documents is greater than the number of positive context
term-z’s that appear in the non-relevant documents, thenwe would keep term-/ in the refined query, otherwise wewould drop it (or reduce its weight). Also, if+| qwR\ > \<1 w l \ . that is, if the sum of tertn-z’s used in
the negative context in the system query and those thatappear in the non-relevant documents is greater than thenumber of negative context term-/’s that appear in therelevant documents, then we would drop term-/ (or reduce
its weight) in the refined query.
The main goal of this feedback scheme is to preserve
the context sensitive nature of the user query so that theadvantages of full text search can be properly exploited.

S U P P O R T SY ST E M ST R U C T U R E

Figure 3. Conceptual representation o f the integrated
application environment

C onceptual m odelling and an example application
The universe of discourse of an integrated DBM S/IR
application will be defined by means of the enhanced
entity/relationship (E/R) model13, which will allow
representation of aggregates and generalizations as wellas documents. These concepts of E /R and its
implementation in a generalized environment are coveredin our earlier studies14, 15. Presently, a data definition
facility for an E /R interface is available that generates
various system dictionaries. The diagrammatic
representation of the E /R model uses rectangles torepresent entities, diamonds for multidimensional
relationships among entities, labels to indicate the type of
relationships or mappings (e.g., one to many, many tomany etc.), double lined rectangles for weak entities (orrelationships), etc. In our case, an entity will correspondto a conceptualization whose representation will be interms of formatted structures (i.e., a record type or
specifically a relation) or a document whose representa­tion will be in terms of unformatted structures. In thelatter, the rectangle will be marked by an asterisk. For
each datamodel, there corresponds a data definition
language (DDL). Figure 3 shows the conceptualization of
the example application environment To give anappreciation of the information conveyed by this diagram,let us list some important relationships:• AU THOR is a weak entity, for him (her) to exist in
the document database, he (she) should either havewritten a document or be referenced by at least one
document148

H ow to support unformatted data in databasearchitectures
In the contemporary full text storage structures that store
genuine text without inversion, sectors or page blocks areused as the units of storage of document files. We canthink of tuples of normalized relations, 1024 bytes or
longer, as the equivalent of those units in a stored relation.
In fact, there is almost one-to-one correspondence
between a (flat) file and a normalized relation. Therefore,in our system, we have made the following changes in therelation data type of the RAP. 3 database computer so thatboth the formatted and unformatted structures can besupported. The main change allows a literal data type tobe as long as a tuple itself (i.e., resulting in a unary
relation). This provides us with a variable length literal
data type, within a fixed length tuple, that stores the
unstructured document attribute. The following is theformat specification for text representation in the RAP. 3
relations16:• Each tuple contains one (or more) complete sentences.
• The first tuple of each document starts with a blank• As with standard typing rules, at least one blank should
follow a punctuation m ark• At the end of a sentence an end-of-sentence (EOS)
marker is placed following the period. EOS must be
followed with at least one blank• The last tuple of the document terminates with an endof-document (EOD ) character.

information technology

The following is the layout of a RAP. 3 tuple:
D

F

Mark
Bits

A
Long text
attribute(variable
length)

AD!

ad2

D4

A

Accordingly, a document file corresponds to a RAP. 3
relation. This relation can hold one or more clusters of
documents, or for large clusters also can be horizontally
split. The associated storage overhead is the sameas in file representations with the exception of one or twowords per tuple reserved for tagging (marking) of data.
Complete sentences from the documents are mapped into
the D1 attribute of consecutive tuples.
The AD i and AD 2 attributes of the integer domain areneeded for the internal use of the context sensitive, text
retrieval operations. D 4 is the key attribute, which is aunique document identifier (DOCID). D 5 through D„ arethe attributes reserved for formatted data. That is, in one
relation, we can store both the formatted and unformatted
data if they are needed for the convenience and efficiency
of processing. Figure 4 shows the relational representa­tion of the example application conceptualized in Figure
3. This relational representation conforms with the RAP. 3
format specifications. According to Figure 4, the
DOCU M ENT entity is mapped into four tabular
structures DOCUM ENT, CITATION, ABSTRACTS,
and SUB-HEADING. The rest of the mapping is one toone. In the list of relations, the key attributes are in boldcharacters. The ABSTRACT attribute holds the full textof the corresponding document’s abstract As shown in
Figure 4, each tuple holds one or more sentences of thecorresponding document and the TU PID attribute links
multiple sentences (tuples) of one document The unary
relation DO CU M ENT is added into the representation toincrease the speed of database navigations (i.e., chain of
mappings by semi-join). In this way, large unformatted
data need not be kept in the system for the sake of the link
attribute (i.e., DOCID).
Language for the integrated D B M S and IR system
The language for the integrated system is the RAP. 3
relational DBMS data language. This language isassociative and high level (i.e., self-iterative). It contains
the power of relational algebra and, in addition, there arecommands for select and arithmetic update, select andcompute aggregate function, etc. This language is also
provided with the instructions for associative full text
search.
To summarize, the following presents the main features
necessary for integrating IR with DBMS:(a) Domain type must support literals.
(b) Domain length must be variable for literal types.
(c) Efficient string search primitives must be incorporated.
(d) Sentence structure and adj acency must be recognized.
(e) A way of processing unformatted data with formatted
structures must be found.
(f) Resolution capability must be added to the operations
supported in (c) and (d).
We have been discussing items (a) and (b) so far andwith regard to (c), (d), and (f), we will detail, in the follow­

vol 3 no 3 1984

DOCUM ENT < D O C ID >C ITA TIO N <D O C ID , TITLE, DATA, JCO DEN ,VOLUME, PAGES, A D I, A D 2>
A B STR A CT<D O C ID , TU PID , ABSTRACT,A D I, A D 2>
SU B-H EA D IN G <D O C ID , STITLE, A D I, A D 2>
A U TH O R<A U TID , NAM E, N PA PER >D O C -A U T<D O C ID , A U T ID >D O C -R E F<D O C ID , AUTID, N R E F >K EYW ORD<KEY ID, KEY, K FR E Q >D O C-K EY <D O CID , KEY ID , W E IG H T >CATEG ORY <CATID , CATCODE, C F R E Q >D O C -C A T<D O C ID , C A TID >JO U RN A LCJCO D EN , JNAM E, N PA PE R >D O C -JO U R <D O C ID , JC O D E N >PU BLISH ER<PU BID , PNAM E, N PU B>
JO U R-PU B <JC O D EN , PU B ID >Explanations of the abbreviated attribute names
DOCID= Document identifier, uniquely identifies
a document
JCO D EN = Journal code
TUPID
= Tuple identifier
STITLE = Subtitle
N PA PER = Number of papers written by an author
N R EF= Number of times an author is referenced
in a document
AUTID= Author identifier, uniquely identifies anauthorKFREQ = Number of times a keyword is used in the
documents (keyword frequency)
CFREQ = Number of times a category is used in the
documents
N PA PER = Number of pages in a published journal
NPUB= Number of journals published by the
publisher of a journal
A D I, AD2 = Full text search attributes

Figure 4.
structure

A relational representation o f the conceptual

ing, the syntax and semantics of the IR related instructions
as well as query resolution for the context sensitive, fulltext search operations. Item (e) has already been discussed
in datastructure and the language aspects will be includedin the following discussion.
As can be seen from the RAP. 3 text mapping scheme,
an important problem of text retrieval is the need tomaintain text contiguity both in string searches andcontext resolutions. This problem has been solved, to agreat extent, by the variable length text attribute feature of
RAP. 3. By this feature, some context resolution
problems, such as splitting a text word between tuples(called term overflow) and passing overflow status anddata to subsequent tuples to finalize the search, areinherently solved. However, there still remains the pro­blem of context resolution for the text retrieval operationsof the type A . .. B and <A, B >n, which correspond tovariable adjacency in number of words and proximity,
respectively. This is because the specified context might
not be satisfied within a tuple. The necessary information
for context resolution is passed from tuple to tuple by afeature referred to as link passing. The following gives thesyntax definition of the new RAP. 3 DBMS/IR Assembler

149

commands needed to perform the text search, and linkpass operations:
M ATCH (tc)[rel(atrl{,atr2{,atr3}}):qual]{[lit]}
M ATCH _ WS (tc)[rel(atrl{,atr2}):qual]{[lit]}
M ATCH _ WW C (tc)[rel(atrl{,atr2{,atr3}}):qual]{[lit]}{[int]}
L IN K _ PASS (tc\, tc2)[rel({atrl,}atr2)]
where

tCj

1 < i < 13 are the tag (mark) bits,
is the relation name of the document.
1 < i < n (maximum tuple length is 1024 bytes)
are the attributes of the relation corresponding to
D\, N D i, N D i, L>4, . . . , D n in the RAP.3 tuplelayout shown earlier.
qual Boolean qualification expression, examples ofwhich can be found in the operations section,
int is a positive integer.
{}indicate options.
lit
is the literal constant corresponding to the searchpattern. The examples of search pattern are:
‘AA'TBB ’, *‘A ,V.‘B B \* iA A ,V.‘B B ’V.‘C’ where *and ? correspond to variable length don’t care
(VLDC) and fixed length don’t care (FLDC)
character respectively, and int? indicates therepetitions of ?.
rel
atr;

The first match instruction searches for the equality ofthe search pattern, in the text stored in ah-! and tc marks all
the qualifying tuples within the cells storing the document;
atr 2 gives the beginning search offset within the text string(i.e., atri). If atr 2 is not specified, then the search offset istaken as 0. If atr 3is specified, all occurrences of the searchpattern within atr 3 are determined and the total number ofoccurrences is stored in atr3, within each tuple. The
difference of the second match instruction is that the firstoccurrence of the search pattern is found within thesentences of atri. The entire match should be contained
within a sentence. The third match instruction finds thefirst occurrence of the search pattern, bypassing at mostint number of words of the text. The value of int can be
specified explicitly, or implicitly by atr3.
During execution of the third match instruction, if thesearch pattern is not found and the search context
specified by the word count is not satisfied within a tuple,
then the tl 4 mark bit of that tuple is set This specific caseis called an overflow condition and can occur only during
the execution of the M A T C H __WWC instruction, since
the context of a match is always satisfied in the other typesof the match instructions. The L IN K __PASS instruction
takes one memory cycle to execute and resolves theoverflow condition in those tuples marked for overflow.
The resolution requires resetting the fl4 mark bit (tc2 in
the instruction syntax) of the tuples marked for overflow,
setting tc\ bits of the subsequent tuples, and passing theunprocessed (i.e., remaining) count values into thepredetermined attributes of the subsequent tuples.
In the other use of the L IN K __PASS instruction,
when the literal attribute atrt is specified, if a tuple is tc2
marked and its atrj does not contain an end-of-text
character, then the following tuple(s) of this document
will be tc 1 marked and their atr 2 is se to zero. This featureof the L IN K __PASS instruction is used to set the searchcontext of the text retrieval operation A . . . B.
It is assumed that the don’t care character will notmatch an end-of-sentence character. This semantic

150

property of search patterns prevents the occurrence ofan overflow during term matching.

Q uery resolution in R A P.3
In the RAP.3 text retrieval system, a great proportion of
the context dependent query resolution takes place in theoperation of the new text retrieval commands the basic
task of which is term matching. As seen in the semantics of
the instructions described above, sentence structure andadjacency are recognized as an integral part of theoperations. Such resolution operations constitute a totally
separable task in most other text retrieval systems. For the
execution of the context sensitive, text retrieval
operations of the more complex nature, however, moresophisticated resolutions are required. These operationsare:

A and Bin sentence (specified context)<A. n. B > (directed proximity)<A, B > n (undirected proximity)
AV.B(fixed length don’t care)
A . .. B(immediate adjacency or variable
number of words in between)
A* B(variable length embedded don’t care)
The resolution for these operations requires that small
RAP.3 programs be written using both the DBMS and IR
instructions of the RAP.3 language. In other words, theseresolutions are embedded in the logic of RAP.3 programs
in which M ATCH and L IN K __PASS operations are
directed10. To aid the user, all these programs are madegeneral purpose, full text retrieval macros running underthe macro processor RAPMAC. Appendix 1 presents alist of these macros, which also gives an idea of the type ofcontext sensitive, full text operations supported in thesystem. Appendix 2, shows the algorithmic expansion ofthe ‘Search (Match) A and B in sentence macro, which
demonstrates resolution on the entire document relationlevel. More details on these can be found in reference16.
One important note here, however, is that in a RAP
instruction qualification, there is no practical limit on thenumber of predicates in a Boolean expression. This meansthat we can have a large number of terms specified for atext search. However, in terms of the macros listed inAppendix 1, this applies, at the present, to macros # 3 and# 4 only. The limitation on the number of predicates isdetermined by the buffer and parameter storage space set
for the implementation of the RAP.3 DBMS.

D istributed database architecture
As we indicated at the beginning, a local computer
network consisting of a network server and several
workstations is the basic hardware architecture. Morecomplex configurations can be obtained by cascading
such networks. In the software counterpart, we canenvision the centralized DBM S/IR as the basic softwarearchitecture. In this architecture, the network server acts
as the central node. When local networks are cascaded,
however, the software architecture can be expanded into a
distributed D B M S/IR
Figure 5 depicts the local computer network facility
used for the experimental DBM S/IR integrated system.

information technology

IntelNDS-II*JOB/*Creation of two relations*/A U T H O R IZ E < ‘U 101’>
RELATION <LOCATION (20)
DEPARTM ENT: LITERAL, 12, KEY
FLOOR: INTEG ER, 1 X G R A N T __READ>
RELATION <EM PLOYEE (500)NAM E:LITERAL, 25, KEY
DEPARTM ENT LITER A L, 12
IN D EX ED
SALARY IN T E G E R , 4 > <PR IV A TE>LOCK <LO C A TIO N >c r e a t e <L o c a t io n > r e l e a s e<LO C A TIO N >LOCK <EM PLO Y EE>
CREATE <EM PLO YEE > R EL E ASE<EM PLO Y EE>
eqq

*DATA

Figure 5.

& L O C A T IO N <‘PERSO N N EL’ 1>< ‘SALES’ 2 > & EN D
& EM PLOYEE/*3 tuples follow*/< ‘K IN G ’ ‘PERSON NEL’ 4500>< “ L’H O M E” ‘SALES’ 1500>‘JO N ES’ ‘SALES’ 25000> & EN D

Local computer network

In this system, the Intel equipment is used. There is an
NRM wih the three workstations (two SYSTEM-4’s anda SYSTEM-2) in a star network based on Ethernet. In
addition, on the same network, there is a single board
computer attached to SYSTEM-2 and a transaction
processing computer (iTPS). Currently, the RAP. 3
DBM S/IR software and the RAPNET distributed
database query execution monitor are operational on all
the processors of the network. As a core application, acentralized DBM S/IR based on NRM with the threeworkstations is being carried out. The second phase will
include iTPS as the network server with which ahomogeneously distributed DBM S/IR system will bemade operational. The third phase will include the
networking of one VAX 11/780 Unix based system into
the configuration. The Unix-C based versions of RAP. 3
DBM S/IR and RA PNET software are nearing comple­
tion.
The distributed database (DDB) versions of RAP
software were published earlier15,17. In the homogeneous
RAP DDB, RAP query programs are decomposed into
subqueries and network execution is monitored withrespect to a dataflow driven query graph17. In this way,parallelism inherent even in a single query program can be
exploited. The RA PNET software is the monitor written
for the homogeneous DDB. It is responsible for query
decomposition, query graph construction, and distributed
query execution on the network.
O P E R A T IO N A L SY ST E M
D atabase creation and query execution
The RAP.3 DBM S/IR language can be used either as astand-alone query language, or as a data sublanguage
embedded in PLM /86 for the Intel based network
processors or in the C language in the VAX 11/780
version. The simple example shown below defines andcreates two relations and performs two simple retrievals,
using the stand-alone version.

vol 3 no 3 1984

*JOB/*Query-A = Employees on 2nd floor*/A U T H O R IZ E < ‘U101’>
MARK(T1 )<LOCATION: FLOOR
= 2>

*JOB

CROSS _ M A RK(Tl)<EM PLO YEE:DEPARTM ENT = LOCATION.
D E P A R T M E N T <M K ED (T1)>
EQQ/*Query-B*//♦Employees in the SALES department,
and the one with the highest salary*/A U T H O R IZ E <‘U101’>
MARK(T1 )<EM PLOYEE:DEPARTM ENT 1= ‘SALES’>
READ<EM PLOYEE(NAM E):
M KED (T1)>
M AX<EMPLOYEE(SALARY):M K ED (T1)> < R E G F _ 4>
READ<EM PLOYEE(NAM E):
SALARY = R E G F _ 4 >EQQAs can be seen from the RELATION command defining
a relation, the user can declare a primary key by the KEY
keyword, which is repeated for compound keys. Also, theIN D EX ED option is used for directing the system to build
a secondary key index for the attribute being declared(e.g., DEPARTMENT). GRANT _ READ, PRIVATE,etc. are for security/integrity control. The CREATE
command populates the database with respect to the
RELATION declaration by inputing the data following♦DATA (or from a disc file). We see examples of tagging
selections, by the MARK; semi-joins, by the
CROSS__MARK; associative and set oriented selectionin the MARK, M AX (maximum), and READ instruc­tions. Up to this point, we have not seen the use of full text
retrieval. Let us point out that if we are interested insimple keyword based retrieval by using inverted indices
we can use this formatted version of RAP. All we have to
do is to declare a binary relation POSTINGS with the151

KEYW ORD and DOCADDRESS attributes and use a
READ <POSTIN GS(D OCA DD RESS): KEYWORD= ‘DATABASE’> instruction to retrieve document
addresses of documents containing the term DATA­BASE from the POSTINGS relation. For merging and/orintersecting indices, we can either define an rc’ary relationand say READ <POST(DOCADDRESS): KEYW ORDI = ‘A ’ & (OR) KEYW ORD2 = ‘B ’>, or
equivalently, write the following program between the twobinary relations, POST1 and POST2:
M ARK (tl)< P O S T l: KEYW ORD = ‘A ’>
CROSS _ MARK(t2)<POST2: DOCADDRESS =PO ST l.D O C A D D R ESS> < P O S T l.M K E D (d )>READ<PO ST2(DO CA DDRESS): KEYW ORD =‘B ’ & M KED (t2)>The second operation is a semi-join through the match­ing document addresses and the READ combines thismapping indicated by M KED (t2) with those tuples
containing the keyword B. The result is a chain of
selection, semi-join, and output using conjunctive selec­tion (restriction). This scheme can be extended to include
the concepts of weighted Boolean retrievals18, 19 andranked output20 by using all the capabilities of the RAP
instruction set.

D B M S /I R integrated retrieval
At this point, we can go back to the example application
presented at the beginning. Based on Figures 3 and 4 andthe query statement given at the beginning of theintegration model, a possible execution sequence can begiven as follows (using the relations of Figure 4 and withno regard to semi-join optimization):
1.
2.
3.
4.
5.

SELECT AU THO R with name JO H N DOE
SEMI-JOIN AU THOR to DOC-AUT via AUTID
SEMI-JOIN DOC-AUT to DOC-REF via AUTID
SEMI-JOIN DOC-REF to DOC-AUT via DOCIDSEM I-JOIN DOC-AUT to ABSTRACT via
DOCID
IR search for‘SEMANTIC DATA M ODEL’AND‘A G G R EG A TIO N ’
SEM I-JOIN ABSTRACT to DOCU M ENT via
DOCID
READ DOCU M ENT

6.
7.

8.

As can be seen in this query, operations 1 through 5,
and 7, 8 are DBMS operations and 6 is an IR operation,and yet everything is linked and consequence of eachother in the execution sequence. Although operation 6 is asingle item in the list, it corresponds to a set of operations
implemented as a RAP macro call which uses DBM S/IR
instructions. To follow these, let us refer to Figure 1,
which is the abstract representation of the integrated
system. In this figure, Q represents the query program
shown above (i.e., operations 1 through 8), g*
corresponds to DBMS operations (operations 1 through
5 ,7 ,8 ) and QT to IR operation 6 . In terms of the datasetsand data manipulation functions, the following corres­
pondences can be seen:

DQr: ( D O C -A U T )* DQS: (ABSTRACT)* —subscript R indicates restriction — f(D Q R): step 5,f(D Q s): step 6 , QSR: step 7, (DOCUM ENT)* =A Q sr)

152

The following is another example of a DBM S/IR
operation at the RAP program level:*JOB/ * . . . * * 1 -) Give the DOCID of the documents that
contain RAP and DATABASE M ACHINE within
the same sentence. */%MATCH$A$AND$B$IN$SENT‘RAP’, ‘DATA­BASE M A CH IN E’, ABSTRACT, ABSTRACT*N D 1, 7T, T3, T4
CROSS _ M A R K (ri) [DOCUMENT: DOCID =ABSTRACTS. DOCID][MKED(7T)]
READ[DOCUM ENT(DOCID): M K ED (Tl)]
EOQForm s interface
Presently, there is a basic forms interface that creates
forms, retrieves, updates, and deletes form instances.
Specifically, a form corresponds to a RAP. 3 relation. A
form instance corresponds to a relation tuple. By enteringvalues and parameters at the specified columns of anaccessed form frame, the user can specify: selection andoutput corresponding to MARK and READ; semi-joincorresponding to CROSS MARK (with a form destina­tion); arithmetic updates ADD, SUB, M UL or DIV; andthe scalar aggregates SUM, COUNT, M AX, MIN,
and AVERAGE.
It is the goal of the experimental system to enhance theforms interface with the functionality of context sensitive,
full text operations, which would link to RAP macro
generation, and user query feedback.

PERFO RM AN CE A N D THE FU TU R E
Efficiency o f integration
The proposed integration, apart from its effectiveness andgeneral purpose utility, which offers several importantfunctionalities, is expected to be efficient because of thefollowing main features:• It uses an efficient implementation of a relational
DBMS.
• IR features are integrated with DBMS at the primitive
level.
• The IR primitives are based on the efficient string
search operations and the context sensitive, full text
instructions carry out query resolution.
• Clustering is used as an efficient IR index in addition
to the secondary key indexing of the RAP. 3 DBMS.
• Integration of DBMS and IR at the primitive level
results in minimum layers of software, which con­tributes to overall system efficiency.
• There is no need for a separate computer for query
resolution and the necessary communication of term
matches since all of these functions are handled in the
RAP. 3 system.
To elaborate some of these further, we can point out
the following. The RAP. 3 DBMS system is a software
emulation of a database computer on the present-day
computers. This implementation is transparent to the user
since the language is what the user sees and uses. This
language is implemented in the emulator by using efficient

information technologymeans of file organization. Relations are stored as hashaddressed files based on keys. In addition, secondary key
indices are constructed on the frequently needed
attributes, as directed by the user.
As mentioned earlier, mapping of full text into longtuples where a long variable length literal attribute isallowed is not much different from the flat file
implementations that use sector or page based indexing
and storage. The document relation can be horizontally
fragmented for access efficiency in much the same way as
flat files are partitioned. In the distributed system archi­
tecture, fragments can be distributed according to user
profiles.
In addition to secondary indexing, as directed by the
IN D E X E D attribute, clustering is used as an effectivemeans of document indexing. As opposed to indexing
techniques such as E-trees, the indexing based onclustering uses semantic information, that is, coupling
among the documents of a collection. A cluster can be a
RAP. 3 relation or a horizontal fragment of a larger
relation. In the former, the relation can be further
fragmented depending on the size of data. In any case, one
can define a secondary index within a cluster because acluster is a relation for which the IN D E X ED attributed
can be declared.
As can be seen in the way the system is integrated,clustering is essential for the efficiency of the overallsystem. We will come back to this issue in the future
hardware solutions for text retrieval.
The semi-join construct of the RAP.3 system (i.e.,
CROSS_MARK) is an important operation. In an inte­
grated system where formatted and unformatted data arecross selected, the join operation must be implemented
efficiently. The semi-join operation does not create a new
relation to store the result and transmits a minimum
amount of data between relations. The advantage of semi­
join comes into the picture more importantly in distributed
databases. As we have indicated earlier, officeautomation uses DDB as the underlying architecture.
We have also indicated the way of handling simple
inverted file based keyword indices. Because indices arenothing but relations, one does not need to resort to an
additional system to have a simple IR for certain
applications.

D ocu m en t retrieval hardware o f the future
For a survey and analysis of various hardware proposals
for document retrieval, one can start from the recently
published summary21. In this section, we want to present
the latest assessment of the work covered in the referenced
survey with the addition of the RAP.3 database computer
solution, which is not covered in that survey.
Text (document) retrieval related hardware varies frompartial to reasonably complete solutions to the problem.
In the partial category, we can mention the proposals on
constructing fast index processors to speed inverted list
intersection and merge. As can be realized, this approachis a component solution without altering the basic
characteristics of conventional text retrieval.
In the complete system category, we see two major
system components specialized for text retrieval, they are
the term matcher and query resolver subsystems. Because
the query resolver does not require much novel hardware

vol 3 no 3 1984

and the system bottleneck rests in the term matcher, various
proposals have concentrated on the term matcher. The
following are the techniques used by the various proposals
made to date:• parallel comparators,• associative memories,• cellular arrays,• finite state automata.
We can consider the first two together. In the parallelcomparators approach, the term detector sits in series
with the datastream, which is read off a mass memory
such as disc. The data, in passing, are buffered in awindow and simultaneously made available to a numberof parallel comparators. The associative memory
technique is a more advanced version of the former.
Search terms are stored in an associative memory, whichacts as a term matcher synchronous with the data. The
advantage of this is the ability to store a large number ofsearch terms, each of which corresponds to a comparator
in the former approach. In reality, one uses a fast random
access memory that emulates an associative memory. The
majority of commercial systems of text retrieval hardware
use this associative memory approach. Two points torealize in this approach are: the difficulty of implementing
context sensitive, full text operations, especially thoseusing fixed and variable length don’t cares, and the serial
nature of the system.
The cellular arrays approach aims to dynamicallyconstruct search patterns by using cells capable ofcomparing a particular character or pattern. The system isserial with data, and cells operate by communicating with
their immediate neighbours so that when a match occurs anumber of logically consecutive cells produce match
signals. This approach requires too much dynamism and alarge number of cells. The dynamic interconnection
problem and data streaming for a large number of cells are
non-trivial and costly issues.
The finite state automata (FSA) approach has been
implemented in various experimental systems21. The
clarity of the FSA abstraction and its efficient
implementation do not go together. There have beenvarious optimizations for FSA implementations ranging
from constructing separate FSA ’s for the starter, sequen­tial, and index states to efficient addressing of the state
blocks. Recently, a partitioned FSA (PFSA) has been
proposed with the aim of synchronizing with the data­
stream at disc speed using a minimum amount of buffer
memory. A PFSA can be at more than one state at a timeand a non-conflicting partitioning scheme of the statetable has been found so that a PFSA can be cast modularly
into VLSI. From this point on, we will refer to the VLSI
based FSA or PFSA as the FSA filter. One needs astructure consisting of a ring of FSA filters and a match
controller for each serial datastream21. For a complete
system, the query resolver microcomputer, in addition to
the standard I/O system, and the host computer are
needed.
In the RAP.3 database machine/computer app­roach22, 23, the entire integrated DBM S/IR systemdescribed thus far is supported with the RAP.3 databasemachine. As far as the user is concerned, there would be
no difference between the software version running on theemulator, and the hardware version running on the actualmachine, with the exception of further efficiency
introduced by the specialized hardware.

153

The RAP. 3 database machine uses parallel cells andparallel microprocessors in each cell. Each micro­
processor executes firmware of query routines
implementing DBMS and IR instructions. The entire
device memory, which is equal to the union of cell
memories, is made to work like an associative memory.
The microprocessors of each cell execute query routines
on the tuples of the cell memory in parallel. The difference
between the associative memory approach discussed
earlier and the RAP.3 (associative) database machine
approach is that in the former, search terms are placed in
the associative memory and the text is streamed throughit, whereas in the database machine the text is stored in thedevice memory which is a quasi associative memory sothat it can be large to accommodate bulk data. In the
microprocessors of each cell, efficient string search is
performed16. The complexity of this operation is of theorder O(m) character comparisons where m is the lengthof the literal text attribute in a RAP. 3 tuple. The increasein efficiency due to hardware will be by a factor (k x n)
where n is the number of parallel cells in the device and kis the number of parallel microprocessor (subcells) withineach cell.
The advantage of the RAP. 3 database machine
approach is the ability to provide both a relational DBMS
and the IR system in an integrated manner in the basicarchitecture and the integration of the query resolver
which is an important component in the other systems.
To maintain a steady flow of data into the databasemachine, a disc cache, as in the Japanese fifth generation
computer’s database machine, or an alternate cell
memory, as in the RAP virtual memory architecture, isneeded.
In cases where physical device dimensions reach alimit, partitioning of very large databases into multiple
discs so that each disc can be connected to a dedicatedspecial purpose hardware would be a viable solution. This
is what the datastreaming techniques discussed earlier
and the FSA filter rely on for performance. There will be afactor of difference between the point where one
duplicates an FSA filter and a database machine becauseof the difference in the cut-off points as determined by thesizes and speeds of the respective devices.

IR system are described. In the language, we have seen
the context sensitive, full text primitives of the RAP. 3
system that are associative and perform sentence andadjacency related query resolution. These structures andoperations are embedded into RAP. 3 relations andDBMS language, respectively.
The distributed database architecture is the next levelof architecture when an office grows out of the bounds andcapabilities of a single local area network that is managed
centrally with a database server. In such a case,
distributed query processing of the DBM S/IR system
becomes necessary. The RAPNET software is the
distributed query execution monitor of the RAP. 3
DBM S/IR language. RAPNET constructs and executes
a dataflow graph for distributed query execution.
In the operational system, we have seen how to create
relations and to process simple inverted file based
systems. Following that, the integrated DBM S/IR
retrieval example is continued and the forms interface isoutlined.
In performance, the efficiency of integration is
discussed. Besides the effectiveness and utility of the
proposed system, a better efficiency is achieved by
reduction in software, lowering the integrated functionality
towards the primitive hardware level, and combining thequery resolver and text matching subsystems into a single
system.
Clustering is used as an index at the semantic level andas a means for database partitioning and relation
fragmenting.
In the discussion of hardware approaches, the RAP. 3
database machine approach is indicated as a viable
alternative to other current research such as the FSA
filter. In the case of the RAP. 3 hardware solution, all thatneeds to be done is to replace the underlying DBM S/IR
RAP. 3 software emulator with the actual RAP. 3
hardware to further boost the performance of theintegrated system. The sizes of fixe databases would
dictate the issues such as database partitioning, using
multiple hardware, and distributed databases. These are
the common problems to all future hardware regardless ofthe specific organization of a given architecture.

ACKNOW LEDGEM ENTS U M M A R Y A N D C O N C L U S IO N S
We have presented an integrated fact/document
information system for office automation. We started with
the need to synthesize DBMS and IR into a complete andgeneral purpose system, in such a way that no one system
would be reduced into the other, by losing its uniquefeatures and advantages. We have seen that the offices ofthe future will need and use services of DBMS and IR
extensively, in a distributed computing environment.
An integrated model of the proposed experimental
DBM S/IR system is presented with respect to query
processing. In that model, the execution of Boolean
queries of context sensitive, full text operations and theirrelationship to document clustering and query feedback
are discussed. The clustering subsystem and its searchstrategy are introduced.
In die support system structure, conceptual data
modelling, ways of supporting formatted and unformatted
data together, and the language for the integrated DBMS/

154

We gratefully acknowledge the computer network grant of
IN TEL Corporation of Arizona which made the con­figuration of Figure 5 a reality.

REFERENCES
1
2
3
4

Salton, G ‘Some research problems in automatic
information retrieval’ Proc. A C M SIGIR Conf.
(1983) pp 252-265
Van Rijsbergen, C J ‘Information retrieval: New
directions: Old solutions’ Proc. AC M SIGIR Conf.
(1983) pp 264-265
Crawford, R G ‘The relational model in information
retrieval’ J. Am. Soc. Inf. Sci. (USA) Vol 32 N o 1(1981) pp 51-64
Scheck, H J ‘Methods for the administration of
textual data in database systems’ Proc. Joint BCS
and A C M Symp. (1980) pp 218-235

information technology

Stonebraker, M et al. ‘Document processing in a
relational database system’ A CM Trans. Office Info.
SysL Vol 1 No 2 (1983) pp 143-158
6 Salton, G and McGill, J Introduction to Modem
Information Retrieval McGraw Hill Book Company,
USA (1983)
7 Lancaster, F W and Fayen, E G Information
Retrieval On-line Melville Publishing Company,
USA (1973)
8 Can, F and Ozkarahan, E A ‘A clustering scheme’
Proc. A C M SIGIR Conf. (1983) pp 115-121
9 Can, F and Ozkarahan, E A ‘Two partitioning typeclustering algorithms’ J. Am. Soc. Inf. Sci. (USA)Vol 35 No 4
10 Van Rqsbergen, C J Information Retrieval (2ndedn) Butterworths, UK (1979)
11 Can, F and Ozkarahan, E A ‘ Similarity and stability
analysis of the two partitioning type clustering
algorithms’ J. Am. Soc. Inf. Sci. (USA) Vol 35
No 5
12 Van Rijsbergen, C J ‘Further experiments withhierarchical clustering in document retrieval’ Info.
Storage and Retr. Vol 10 (1974) pp 1-14
13 Chen, P P ‘The entity relationship model — toward a
unified view of data’ AC M Trans. Database SysLVol 1 No 1 (1976) pp 9-36
14 Dogac, A and Ozkarahan, E A ‘A generalized
DBMS application in a database machine’ Proc.
AC M SIGMOD Conf. (1980) pp 133-143
15 Ozkarahan, E A and Kerschberg, L ‘A heterogeneous
distributed database system architecture incorporat­ing data semantics and a relational database machineinterface’ Dept. Computer Science, Technical Report
TR82-06, Arizona State University
16 Ozkarahan, E A and Can, F ‘Integration of fact/
document retrieval systems within a databasemachine’ Dept. Computer Science, Technical Report
TR -82-02, Arizona State University (1982)
17 Ozkarahan, E A, Tansel, A U and Smith, K C‘Database machine/computer based distributed
databases’ Proc. 2 n d ln t Symp. Distrib. Databases(1982) pp 61-79, North Holland, The Netherlands
18 Waller, W G and Kraft, D H ‘A mathematicalmodel of a weighted Boolean retrieval system’ Info.
Process, and Manage. Vol 15 (1979) pp 235-245
19 Buell, D A and Kraft, D H ‘A model for a weighted
retrieval system’/. Am. Soc. Inf. Sci. (USA) (1981)
pp 211-216
20 Noreault, T, Koll, M and McGill, M J ‘Automatic
ranked output from Boolean searches in SIRE’/. Am.
Soc. Inf. Sci. (USA) (1977) pp 333-339
21 Hollaar, L A ‘Hardware systems for text informa­tion retrieval’ Proc. AC M SIGIR Conf. (1983) pp
3-9
22 Ozkarahan, E A ‘Desirable functionalities of
database architectures’ Proc. IFIP World Congr.
Paris (1983)
23 Ozkarahan, E A ‘The implementations of therelational associative processor (RAP) and its system
configurations’ D ep t Computer Science, Technical
Report, TR82-05, Arizona State University
5

A P P E N D IX 1
The text retrieval applications in the RAP system areprogrammed with the use of the RAP instruction set andvol 3 no 3 1984

nine available text retrieval macros that are listed in thefollowing:• MATCHSA: Finds any document that contains theword A.
• MATCH$ALL$A: Finds any document that contains
the word A. Different from MATCHSA because it
searches for all occurrences of A.
• MATCHSASORSB: Finds any document that con­tains the word A and the word B.
• MATCHSASANDSB: Finds any document that con­tains the word A and the word B.
• MATCHSASANDSNOTSB: Finds any documentthat contains the word A but not the word B.
• MATCHSASANDSBSINSSENT: Finds any docu­
ment that contains both the word A and the word B
within the same sentence.
• MATCHSASANYWORDSSB: Finds any documentthat contains the word A (either immediately or afteran arbitrary number of words) followed by the word B.
• MATCHSASNWORDSSB: Finds any documentthat contains the word A followed by the word B
within n words of the former.
• MATCHSTHRESHOLDSOR: Finds any documentthat contains at least n of the m distinct words:
A i, Ai, . . . , A m; where n < m .
In the following, the meanings of the macro parameters
are explained together with their actual use in the two
example macro call statements.
STRING, (z < 2): the strings to be matched (e.g., A
and B) in the text
the relation name containing the
REL:
text to be searched,
the literal attribute of relation REL
LA:that corresponds to the literaldomain that holds the text to be
searched.
the number of attributes of relation
NAj (i < 2):
REL that are needed during theexecution of the macro body,the distinct mark bits of relation
Ti(i<5):
REL that are needed for the
execution of the macro body. Before
calling a text retrieval macro, all of
the mark bits specified in the macrocall statement should be cleared.
After execution of the macro body,the first mark bit indicates (shownas Tx in the call statements) the
qualified tuples for the text retrieval
operation.
QUAL:
the tuples for text retrieval are
selected with respect to this qualifier
which is a literal constant andcontains a RAP qualification
expression. If all the tuples ofrelation REL are to be considered,this parameter is omitted. A typical
QUAL specification would be:MKED (71).
The two macro call statements for the text retrieval
operations corresponding to macros number 1, and 9
above are demonstrated in the following:
For Macro MATCHSA:
MATCHSA STRING, REL, LA, T u QUAL

155

For Macro MAT CHS A$ AND$B$IN $ SEN T:
M ATCH$A$AND$B$IN$SENT STR IN G h
STRING 2, REL, LA, N A b
T u T2, T3, T4, QUAL
After the execution of the macro body, the mark bits T2
through T3 remain clear.

A P P E N D IX 2
Search for A and B in sentence
In this text retrieval operation, a tuple containing the firstterm ( e . g A) may be considered more than once; for thecurrent occurrence of A, the second term may not occur inthe specified word proximity. In that case the unprocessed
portion of the tuple will be considered for the occurrenceof A again and, if found, the tuple will be re-examined forthe occurrence of the second term within the samesentence. The algorithm is as follows:

156

Mark all the tuples of the text relation for an A
match.
2. Set the search offset for the term A to zero in all thetuples.
3. Test if there are tuples to be considered for a pending
A match, if not, go to step 11.
4. Reset the mark bits which were set in a previous A
match operation.
5. Perform a match operation for term A on the tuples
that may be eligible. If there is no match, go to step 11.
6 . Discard the unqualified tuples at the end of the match
operation, so that they do not take part in the possible
re-executions of step 5.
7. Perform a match-within-sentence operation for thesecond term B on the tuples that were selected instep 5.
8. Test if any B match exists, if not go to step 3 (note thatin a tuple, there might be more than one sentence andany one of these sentences may contain term A).
9. Mark all the tuples of the qualified documents and do
not process them for an A match again.
10. Go to step 3.
11. Exit.
1.

information technology