An approach to the functionaldescription of an information
retrieval system based on a
generalized modelC J Crouch and R E Nance*

A high-level, functional approach to the description o f ageneralized information retrieval system is presented.
The description is based on the top-down decompositiono f the system into modules and processes and on an
appropriate data abstraction. The purpose o f this article
is to describe the behaviour o f the system in terms o f thecomponent processes and the interactions o f theseprocesses in terms o f inputs, outputs and the associatedtransformations. It allows one to view the system as acollection o f abstractprocesses, each o f which is concisely
defined via a notation that describes what is accomplishedbut not how such a process is to be implemented. Seman­tically irrelevant details are removed, thereby producing
a nonprocedural description which not only elucidates
system behaviour but serves as a basis fo r subsequent
formal specification.
Keywords: information retrieval, mathematical models,
generalized IR system, specification

IN T R O D U C T IO N
A primary concern in the design and development ofsoftware is the generation, integration and control ofcomplex systems. It has recently been noted that over
90% of the total cost associated with current systems
development is due to the cost of software1. Yet the
production of well-structured software, inherently difficult
Cornell University, 405 Upson Hall, Ithaca, NY 14853, USA‘ Virginia Polytechnic Institute and State University

168

by nature of the programming task itself, is madeincreasingly more difficult by the characteristics ofcontemporary software design. Specifically, most soft­
ware produced today is designed to function not as anindependent unit but rather as a part of a larger and moresophisticated complex system.
A critical issue in the design of complex systems now
surfaces, namely, how may the development of such
systems be guided and controlled? Two major approaches
to the problem can be identified. One approach deals
primarily with the proper methods of program develop­
ment. Stepwise refinement, modular coding, structured
programming, and the use of abstract data types typify
this approach. Another approach, which has received
increasing attention over the past ten years, is that ofsoftware specification.
Formal specification techniques allow the specification
writer to describe system behaviour without reference to
its implementation. On the basis of such a specification, itis then possible to determine that the implemented system
actually satisfies or is consistent with its specification.
Thus formal specification techniques permit verificationof the system (i.e., establishment of its ‘correctness’ withrespect to its specification). A number of formal specifi­
cation techniques have been discussed in the literature,including among others axiomatic, algebraic, denotationaland operational approaches. A discussion of these tech­niques is beyond the scope of this paper; the interested
reader is directed to the l i t e r a t u r e .
Formal specification techniques aim at producing an
abstract view of system behaviour. Yet the intelligibilityof the resultant specification is often questioned. Suchspecifications tend to be excessively detailed, entail

0144-817X /84/030168-12S03.00 © 1984 Butterworth & Co (Publishers) Ltd

information technology

considerable overhead, and may tend to obscure rather
than clarify the procedures being described. They areoften difficult to understand, couched in terms andformalisms unfamiliar to the person(s) charged with theirimplementation. Moreover, with these techniques,concern centres on the ‘mathematical tractability’ of thedescription rather than on giving a clear overall under­
standing of the system and its behaviour8. The complexity
introduced as a consequence of formalism detracts fromour understanding of the system.
Another major concern arises in dealing with thespecification of large, complex systems. In large system
specification, the domain of the specification methods
must be extended from (typically) stacks, symbol tables,and database views to entire systems. Efforts made in thisdirection include formal specification languages9 andautomated specification systems and tools 10,1 . Underlying
many of these automated support systems are databasemanagement systems based on the traditional formal
models.
Consider now the issues involved in the specification of
an information retrieval (IR) system — a large, complex
system encompassing such diverse activities as interactive
query processing, automatic indexing, and file manipu­
lation. In contrast to the database environment, there are
no formal models on which an intrinsic part of thespecification can be based. Moreover, although each method
has its proponents, no consensus of opinion exists as towhich method of specification is best suited to deal with thedescription of large systems. In fact, it would appear thatno one formal specification technique can describe such asystem (i.e., the information retrieval system) in an effec­
tive manner. (Some examples suggest that a combinationof techniques would be most effective12,13.)
Liskov and Zilles state that even if one is unable todescribe an entire system, ‘the ability to define some of themodules used in constructing a system in a precise, formal
way would be a major advance in the construction ofreliable software’2. In order to accomplish these goals in
an information retrieval environment, research must be
directed at• producing a clear, comprehensive view of the system,in terms of its components, processes and theirinteractions;• identifying the module(s) of the system for which
formal specification is most important; and• determining which method or combination of methods
is best suited to describe the behaviour of each
module.
Our focus in this paper is the first item above. We use
abstraction as a means of dealing with the system; ourpurpose is to describe the behaviour of the system in termsof the abstract objects (sets) being manipulated and theprocesses associated with them as the system operates
over time. Thus we present a high-level description whichis intended to elucidate and clarify the behaviour of the IR
system based on the decomposition of the system intomodules and processes. The decomposition is, in turn,based on a detailed study of the functional characteristicsof the system14. The resultant description is functional in
the sense of Ref 15, i.e., it states exactly what is done byeach process in terms of its input, its output, and thetransformations performed. The description specifies
what is to be done; the details of how to do it are left to theinterpretation of the functions.

vol 3 no 3 1984

The functional description of the IR system may beconsidered a formalization of its requirements definition.
It represents a link between the informal (natural language)
requirements definition and the formal specification of thesystem. With reference to Wasserman’s three views of a
specification (the user, design and verification views12),
the functional description represents a unification of theuser-design view (as opposed to that of the designverification view). From the functional description, aformal specification of each system component may
subsequently be produced, presuming an appropriate
specification technique has been determined. The
operational system which results may then be verified (atleast to the extent it has been specified) by verification of
its parts. Moreover, the functional description, althoughnecessarily detailed and precise, presents a view of systembehaviour which is much more easily understood than that
produced by formal verification techniques.
As a basis for our description, a model of a generalized
information retrieval system is proposed. The model
consists of six modules or subsystems: the logical processor,
selector, descriptor file, locator, document file anddocument analyser. These subsystems function in anenvironment defined by the user and datablocks, which
serve as points of input to the system. Proceeding froma discussion of the functional characteristics of thecomponents, a functional representation of each subsystemand the relationships existing between them is developed.
The description allows one to view the system as a collec­
tion of abstract processes or activities. Each process isconcisely defined via a notation that describes what isaccomplished but not how such a process is to be
implemented. The semantically irrelevant properties ofthe description are removed.

T H E G E N E R A L IZ E D M O D E L
The generalized model of an IR system proposed in an
earlier work by Crouch 14 is shown in Figure 1. The
structural similarity to models proposed by other authors,notably Vickery16, is acknowledged. This model is viewed
as generalized since most operational retrieval systems
are functionally compatible with it17. Salton’s SMART
system, with its emphasis on fully automatic content
Query
Response

Logicalprocessor
Q uery in te rm s o f
d e s c rip to rs o r index term s
D e s c rip to rs !--------- ;------------- *• D escriptor-----file
D escriptors

S e le c te d
( U ser } ■ specifications S elector

R e s u lta n t
s p e c u la tio n sDocument
analyser

Final s e le cte d
spe cification s

D ocum ents__ i

L o c a to r
in fo rm ­a tio nL o ca to r

Document
file

D ocum ent(su rrog ate)

D ocum ents

Figure 1. Model o f a generalized information retrieval
system169

analysis for query and document processing, is theoperational system which most closely resembles themodel. In developing the representation of the IR system,
we concentrate on the functions executed by or withineach subsystem as well as the interactions that occur
between the modules. A brief description of the model
follows.
The user (generally assumed to be unfamiliar withmechanized IR systems or computers) submits a query to
the system. The query is taken by the logical processor,
which operates on the query and outputs to the selector thequery in terms of systems vocabulary (i.e., descriptors orindex terms). The selector uses the descriptors to search
the descriptor file (or index). The resultant specifications,
i.e., pointers to those documents which have successfully
satisfied the search according to some pre-establishedcriteria, are returned to the selector. The selector, in turn,operates on these specifications to resolve the query andsends the final selected specifications to the locator, whichuses this information to search the document file. The
document surrogates themselves are returned via thelocator to the user.
The second point of input to the system is represented
by the component labelled data. All document-related
data enter the system through the document analyser. The
document analyser operates on the input to produce two
outputs — a representation of the document in terms ofdescriptors, to be stored in the descriptor file along witha pointer to the document in the document file, and a
representation of the document itself (i.e., a surrogate) tobe stored in the document file.
Note the three feedback loops involving the user:• from the user to the logical processor and back to
the user,• from the user to the logical processor and selector, thenback to the user, and• from the user to the logical processor, selector andlocator, then back to the user.
In the first case, the logical processor is asking the user toreformulate, clarify, or augment his query. In the second
case, the selector is requesting user approval of the selected
specifications, i.e., for the user to designate from amongst
the set those that most accurately describe his/her needs.
The third case represents the normal channel by means ofwhich the document surrogates associated by the systemwith the user’s query are returned to the user.
Note that dictionaries of various types (thesauri, stemand suffix dictionaries, phrase dictionaries, etc.), to theextent that they are used during content analysis, must beaccessible to both the logical processor and the document
analyser of the model. In the functional description of theIR system, we assume that such dictionaries are available
for system use but that the methods by which these
dictionaries are constructed are not of primary interest interms of the overall system behaviour.

D E S C R IP T IO N O F T H E E N V IR O N M E N T
The environment is described by the user and datablocks.
Our assumptions about this environment are limited. We
consider that the user is motivated by a need for inform­
ation and interacts with the IR system in an attempt tosatisfy this need. Thus he or she supplies a query in170

natural language form. The query is viewed initially as
consisting of a set of individual characters or one-character
strings. We designate the input query Y to be the set of all
such strings initially utilized to describe the user’s need for
information:

Y:: = (*!, a 2, . . .

= {a | asA}

where A is the finite symbol set recognizable by thesystem, i.e. the system alphabet.
Moreover, in conformance with conventional practicein information processing, we consider the query
formulation to be based on Boolean logic. Although theadvantages offered by the vector processing model overthe Boolean model are well known18,19, the most common
query format in operational systems is undoubtedly
Boolean.
The second part of the environment, the datablock,represents the raw material input to the IR system. This
input is assumed to consist of unprocessed textual
material in a form convenient to the system. Certain
conventions may be followed in compiling this material
for input, but no manipulation by trained personnel prior
to entry is assumed. Although the form of these data canundoubtedly affect system design, reducing the require­ment for automatic content analysis for example, for our
purposes this material is considered as a set of recorded
symbols recognizable by the document analyser. This setof recognizable recorded symbols is called a document, T,i.e.,

T:: = a u a 2, . . ., am = {a \ aeA}
where each document is composed of a finite number ofsymbols or characters a, which are members of the symbol
set A It should be noted that although the query and the
document are expressed in terms of the same alphabet,
there is not necessarily any other commonality; i.e., noterms or words are necessarily in common between thetwo.
We impose few requirements on the user and datablocks,
consequently forcing the IR system to accept an increased
responsibility at two points — the logical processor anddocument analyser. These modules necessarily become
more complex as a result.

A P P R O A C H TO F U N C T IO N A L
D E S C R IP T IO N
The symbols used in specifying the functional represen­tation are defined in the three tables in the Appendix.
Wherever possible we have attempted to follow theconventions employed in programming language definitionor the usual mathematical notation. Since no single set ofsymbols and no standard terminology are universally
accepted, we have taken the liberty of defining ourown where required. The operators used in the functional
representation are defined in Table A l. Basic definitions
used in the development of the representation are given in
Table A2. Additional notation is defined in Table A3 andintroduced within each section as necessary. The approachtaken is to ‘trace’ a query as it is processed by the system,with equal attention paid to each process rather thanemphasizing one aspect of system operation at theexpense of others.

information technology

The logical processor (L )We assume that the query is expressed in natural language
form; if desirable, a minor degree of restriction could be
imposed20. The primary task of the logical processor is toaccept the query as input and to produce a normalized
query, i.e., the query expressed in terms of systems
vocabulary, as output to the selector. Production of thisquery can be subdivided into the following tasks:• query formation — transformation of the individual,
single-character strings or symbols a, into tokens of theform [a], to create a token set Yp\• query reduction — removal of all grammaticalconstructs and tokens unrelated to the supposed‘information content’ of the query, thereby forming a
reduced query, YD;• query recognition — validation of the query, identifying
the (reduced) token set YD as a legitimate query. This
activity may entail performing a syntactic analysis of
Yd either independently or in dialogue with the user toenable modification according to system requirements.
The result is a syntactically valid query, YR;• query normalization — enhancement of YR by
dictionary reference in the process of translating thequery terms into [terms consistent with] systems
vocabulary. The resulting query Y n may now beprocessed by the selector;• presearch activities — utilization of the query formu­
lation resulting from the three previous tasks to allow
user feedback in further query modification.
We can represent the function of the logical processor by
beginning with the input query Y, which is initially viewed
as a set of characters or symbols comprised of members of
the IR system alphabet, i.e.,

Y:: = a u a2,= {a | ae^}

The alphabet^ is the finite symbol set recognizable by thesystem, A :: = {at, i= 1 , 2 , . . . ,This set can bepartitioned into two disjoint subsets, A T za&AN, where T r
is the subset of terminal symbols (e.g., blank) and AN thesubset of non-terminals. Set AN can also be partitioned
into two disjoint subsets, AR and A s. AR is the set of allalphanumeric characters, whereas A s is the subset of
non-terminals used to indicate the special character
symbols which are elements of A.

Query formation ( L F)
The constitution of a valid token is system and/or collection
dependent. (For example, one could imagine circumstancesin which the term ‘C02’ is either a valid or an invalid
token.) If the allowable query format consists of English
text, the individual tokens are usually separated bydefined terminators (elements o iA T orA s ). The query isgiven structure by a defined set of structural elements (forexample, parentheses) which is itself a subset of the set of
special characters,^5. We assume that all query processing
is performed in a left-to-right order.
The first function of the logical processor (L) is to forma token set. This is accomplished by concatenatingconsecutive elements in Y of type AR until either a terminal
character (an element of A 1) or a special character (anelement of A s) is encountered. The concatenated string
becomes a token [a],- of the transformed query set Yp, andvol 3 no 3 1984

the terminators are deleted. The transformations associatedwith the query formation function L F can be expressed
as follows:

Lp\ V a e Y(1) a — [a],i aeAs
(2) _L{a/} «- [a]to a, eAR(3) aA, aeAr
The process of query formation, L F, may now be
expressed as:

L f : YF = {[a], | a - [«];> ae.45;_L{a,} — [a]fo aieAR; a — X, a sA r ; aeY)
That is, the query formation function Lp, acting upon its
input F, produces a set of tokens YF. Yp consists of all
tokens of the form [a], where the [a], are produced via thespecified transformations and aeY. For simplicity, lety :: = [a],. The Yp = {[«],} = jy) and logical processor
activity in query formation may be expressed as
L f ( Y) = Yf . Thus query formation is analogous to
the lexical analysis phase of a compiler in that, in eachcase, statements are scanned to produce tokens.

Query reduction (Lp,)
Consider A s, the set of special characters. As can bepartitioned into two disjoint subsets, A v andAv, where/Iu
represents the set of all characters which are used todenote the structure of the query (i.e., ‘structural elements’such as parentheses in the Boolean query) and A v is theset of all non-structural elements/e.g., the usual symbols
of punctuation used in English text).
The query reduction phase of logical processor activity‘reduces’ the input query Yf by removing those tokens
unrelated to the ‘information content’ of the query. In a
Boolean environment, reduction implies the removal of all
non-structural special character tokens (elements of A v).
The resultant token set consists of alphanumeric tokens
and structural elements (single-character tokens such as
parentheses). It also includes the logical connectives ‘and’and ‘or’, which are used to express the relation between
terms in Yp. These terms are by convention represented
by the corresponding symbols ‘A’ and ‘V’, respectively.
For this reason, as well as to simplify subsequent
processing, transformations associated with query reduc­tion may be specified as follows:

L D:V y s Y F(1 ) y ~ \ y t A v( 2 ) y *- [A ],y = [and](3) y - [V],y = [or]Thus the query reduction function Lp, operating on the
reduced Boolean query Yp may be defined as:

L d : YD = {y \y - X ,yeA v; y - [A],y = [and];y[V],y = [or];yeYp]
Thus Lp, (Yp) = Yp), and Yp, now consists of query terms(tokens which are possible descriptors or index terms),
structural elements and logical operators.
Query recognition (LR)
During the query recognition phase, denoted by Lp, thelogical processor acts either to accept the query as is (i.e.,171to validate the query) if it is recognizable by the system or
to reject the query in the case of incomplete syntax. Thus

Yd if Y d is a valid query
if Yd is an invalid query0

In addition, the system could allow interaction with theuser in an effort to produce a revised query if YD cannot bevalidated at this point. This process may be described asfollows. If L r ( Yd ) = 0 , Yd is returned to the user. The
user can then submit a query T , which may be either atotally new query or a modified version of Y d- In
either case,L r (L d (L f (Y ))) =

Yr or

0

and the process is continued until L R ( YD) = YR, YR ^ 0 .
Thus query recognition is analogous to the syntactic
analysis phase of the compiler in that as a result of its
activity, its input is structurally or syntactically validated.
Of particular interest at this point is the process ofquery recognition for a Boolean query. Let U represent
the set of query terms which are elements of Yd- Then U
may be defined as:

U:: = (y \y z A u, yzo-,yeYD), where U C Y D
and o:: = {[A], [V]}.
Then B, the set of all (syntactically correct) Boolean
queries associated with YD (i.e., whose terms are query
terms of YD), may be defined as

B :: = {ib}, where b:: = u\ [(]£[)] Ibob.
I f Yd eB, then L R ( YD) = T * YR ^ 0 , and YR isrecognizable. Otherwise, L R ( YD) = 0 and a syntactic
analysis of the reduced query YD fails. Assuming theoutput of query reduction is non-null, the next task of thelogical processor is query normalization.
Query normalization (LN)
The query YR which is input to the query normalization
phase of logical processor activity has now been validated
syntactically. It consists of a token set composed of query
terms, logical operators, and structural elements (i.e.,
parentheses). Yet for this query to be processed by thesystem, it must be in terms of the system vocabulary, i.e.,each query term must be recognizable by the system. Thus
the tasks of query normalization consist of query term
validation and the transformation of each valid query term
into its appropriate representation in terms of descriptors
or index terms.
Consider U, the set of query terms which are elementsof Yr . If L r ( Yd ) = Yr , Yr ^ 0 , then YR = YD and
U = [y | y z A v ,yeo;yeY R}, where U C YR. Then in thegeneral case, the transformations associated with thequery normalization process L N may be defined quite
simply as

L N:V u eY R
(1) u — d, foru = d, de A(2) u *- X, for u d, A d eVQuery normalization is the activity during which thesauri
and/or phrase dictionaries might be employed in theattempt to normalize the query, i.e., to align the query(expressed in terms of the user’s vocabulary) with thesystem’s representation of the data. How may the com­172

position of A, the set of all descriptors, be determined?
Consider the frequency distribution of terms contained in
the documents stored in the document file of thegeneralized model.
Many experiments have dealt with the task ofrecognizing or choosing appropriate descriptors for a
document collection. It has been shown that the best terms
are medium frequency terms with positive discrimination
values; these terms may be used directly as descriptors(i.e., this criterion may be used to determine the composi­tion of A , the universal set of descriptors)21. The question
arises as to whether to include in the descriptor set narrow,
low-frequency terms with near-zero discrimination values
and broad, high-frequency terms with negative discrimi­
nation values. Omitting the former may result in a loss of
precision, whereas omitting the latter may reduce recall.
But transformations may be applied to these terms which
improve their discriminative properties. Specifically,
low-frequency terms can be ‘expanded’ by dictionary(thesaurus) reference and the set of high-frequency terms
can be ‘contracted’ via the use of phrase dictionaries18.
Consider the case of query expansion. For certain lowfrequency terms in certain environments, it may be desir­able to augment or replace these terms with an appropriate
thesaurus class. Logically, the query is expanded asfollows.
Let U represent the set of low-frequency query terms
which meet the specified criteria for expansion. Then foreach ueU’, U' C U, there exists a set N ( u ) (thesaurus
class) such that N( u ) C A. With reference to lowfrequency terms with near-zero discrimination values, thequery normalization function L N may be expressed as:

L n : VweU'(1) u - p[_L {[(],V tf(u), [)]}]
where the decomposition function p breaks the con­catenated token of descriptors, logical operators andstructural elements into separate tokens. Each ueU’ has
now been replaced by the corresponding set of thesaurus
class entries and the structure of the (Boolean) query has
been maintained. In practice, the thesaurus class identifiers
may replace each particular query term u, where ue U , inY r. Logically, however, YR has been expanded by the
replacement of a single query term u, ueU', by the set ofdescriptors which are considered ‘synonymous’ with it.*
Consider now the utilization of certain high-frequency
terms as descriptors. It may be decided to discard suchterms on the basis of their lack of discriminative power. If
not, such terms may be combined via dictionary reference
into appropriate phrases of lower frequency with higher
discrimination values.
Let U" represent the set of high-frequency terms whichmeet the criteria for normalization via phrase dictionaryreference, where U" C U C YR. Since YR is a syntacticallyvalid Boolean query, all query terms consist of individual
tokens, which are related via logical operators and(possibly) structural elements (parentheses). These
structural elements may be supplied by the user when the♦The use of this method in dealing with low-frequency terms in a
Boolean environment is largely dependent upon the thesaurus. If a highdegree of synonymy is exhibited between thesaurus class terms, theresults of query expansion by this method should be as desired. Other­wise an unacceptable loss of precision can occur. A more viableapproach might be to maintain the low-frequency term in the indexing
vocabulary and to expand only when an initial query involving that term
fails to produce an acceptable result. More research is needed toestablish a methodology for operating in this environment.

information technology

query is input to indicate that operations within parentheses
take precedence over other operations when die query is
processed (i.e., executed) by the selector. (Note that theorder of processing and the precedence of the logicaloperators is uniquely defined for each system). To simplify
the task when dealing with high-frequency terms, we
assume that the grouping of any two query terms m, and Uj
expressed in the form ‘u, A u f indicates that these twoterms are candidates for normalization via phrase
dictionary reference, where one of the terms, «,■or uj , is anelement of U". (In practice these requirements could be
modified, e.g., the number of terms related via the ‘A’operator could be extended, etc. It is clear, however,that only first-order conjunctive relationships should
be considered.)Consider the set of high-frequency query terms U"
associated with YR. Then there exists a set M , M C A ,all of whose members consist of tokens of the form
_L {mb ttij) = [mjTtij]. Then M serves as a phrase
dictionary whose entries are composed of individual
tokens which by virtue of their co-occurrence have a
specific meaning aside from that associated with eachtoken individually. Hence each element of M itself serves
as a unique descriptor d, an element of the set A. Thistransformation may be defined as follows:

L N: Y U(eU" 3 _L {uj, Uj} eM(2) _L {ub [A], Uj} - dSubsequent transformations, accounting respectively for'the medium-frequency terms with positive discrimination
values (elements of A ) and those terms meeting none of
the aforementioned criteria, may then be expressed as

L n : Y u 3 u = d, ds A
(3) u
d
and
L^: Y u 3 u 5^ d, Y d s A(4) u — \Thus in a generalized system in which document terms inall frequency ranges are recognized, the query normaliz­ation phase of logical processor activity may be expressed
as follows:

L n : Y n = {y | u - p [ JL {[(], V N(u), [)])], ue U';_L {uh [A], uj} «- d,
V UjEU" 3 _L \ub Uj} eM \ u *- d , u = d ,ds A ; u — \ u # d, Y d E A \ y E Y R}
Thus L n ( Yr ) Yjj and the normalized query Fjy,
expressed in terms of systems vocabulary (i.e., descriptors,
logical connectives and structural elements), is passed tothe selector.

One can visualize the function of the logical processor(L) to be defined in terms of the individual tasks as

L:: = < L n ( L r ( L d ( L f (.)))), L P{.) >where the angular brackets enclose the outputs producedby the module.

The selector ( S )The selector ( S), using the processed form of the query Yn
as input, retrieves from the descriptor file the set of all
document identifiers associated with each descriptord£ Yn . The indicated logical operations are then performedin the order specified (with precedence of operations
modified by parentheses). The result is a set of specifi­
cations, i.e., die set of all document identifiers associatedwith the initial query Y. In addition, selected specifications,e.g., a document file entry, the number of documents
associated with each descriptor, etc., may be returned tothe user. This may be termed postsearch activity.
Docum ent selection ( S $)In representing the function of the selector, we must
consider the relationship between this module and thedescriptor file. We represent the descriptor file as apassive entity acted upon by the selector and the docu­
ment analyser. Let T{d) denote the set of all documents
associated with the descriptor d, where T(d) C D , the setof all documents. Beginning with the first descriptorc/ey#,
all documents associated with this descriptor ( T(d)) are
identified and formed into a single token by application of
the concatenation operator (_L). The decomposition
operator (p) breaks the token into components, where acomponent is either a document identifier or a parenthesis.
This set of tokens replaces d in the query YN, and thesequence of operations is repeated beginning with the next
descriptor d, i.e.,

Ss--VyeYN( 1 ) y - p [ X { [ ( ] , T ( d ) , [)]}],y = d
Finally the logical operators ([A], [V]) are replaced by
the set union and intersection operators, ([fl], [U]),respectively, and the expression is evaluated to produce
the set ofdocument identifiers (loosely, the set of docu­
ments) D associated with (or relevant to) the original
query Y. This operation of the selector may be expressedasSs-YysYff( 2) y - [ n ] , y = [A](3 ) y - M , y = [V]Thus Ss, the action of the selector in document selection,
may be defined as

Presearch activities ( L P)
The function of the logical processor in presearch
activities would involve output from the previous phasesof reduction, recognition and normalization. At this point
the logical processor acts to return any information thatmight be of interest (i.e., YD, YR, and/or YN) to the user.
For the Boolean query, this activity can be expressedas:

L P\ User<={y lyel^} = YN.

vol 3 no 3 1984

S s : Ys = {y |y - p [ _L {[(], T(d), [)]}],y = d;y - [ n ] , y = [A];y «- [U],y = [v];ye Y dApplying fl, the operator which evaluates any valid set
expression, to Ys yields D, the set of documentsretrievedby the original query Y: Ys = {D\ D eD} —D. Henceselector activity_can be represented as Ss ( YN) = Ys,
where ClYs = D, and the original query Y has now
been resolved.

173

Postsearch ( SP)The second function (sometimes called postsearch
activity) of the selector is to operate on the document set
D in a manner so as to return some aspect of D to the user
via the route labelled ‘selected specifications’. The
information returned issystem dependent. In one case thenumber of elements in D (p{D)) might be sufficient whilein another the number of documents associated with aparticular descriptor ( T ( d ), where deYN) might beprovided. We represent the activity of the selector inpostsearch as follows:

SP: User <= n(D)Representing both functions of the selector requires theapplication of the document-selection function followedby postsearch activity, i.e.,

S:: = < S s ( . ) , S P( . ) > .
The descriptor file
Representation of the descriptor file begins with theassumption that the main concern in our generalized
retrieval system is single query processing (i.e., the queryof the individual user), rather than the batch processing ofmultiple queries. As previously noted, the descriptor file isviewed as a passive entity, acted upon by the selector andthe document analyser. We characterize it by representing
its organization rather than prescribing any active func­
tions performed by it.
We consider the system vocabulary to be changing(increasing over time) and largely determined by thecriteria invoked by the document analyser. The essential
task is to represent the process by which the set T(d) is
defined with reference to the organization of the descriptor
file. Although virtually all operational systems utilize
inverted files, we consider three principal file organiz­ations, namely serial, inverted and multilist.

That is, associated with every descriptor d is a setR ( d) of
documents Dj. Inverted file organization can be representedby:(1) T ( d ) : : = R ( d )(2) Q(D):: = {Dd: R ( d ) , V d £ A}

The multilist fileMultilist file organization is somewhat more complex
than the others, since it involves the use of an additionalfile, frequently called the directory. The directory isordered by key (i.e., descriptor). Each key has associatedwith it a pointer to a corresponding main file entry, which
represents that document in the system with which the key(descriptor) is first associated. For each descriptor
contained in the document, there is a pointer to the ‘next’
document which contains that descriptor. This organiz­ation permits the use of a reduced directory, which gives
access to a large main file in which the entries (documents)
under each key or descriptor are not individually accessible
but are linked. (For a discussion of multilist organization,
see Ref 22.) Multilist organization is pictured below.
Directory

Dj

Main FileDjd, ii Dj•'DJ

dj i D k

Dk

dt i A___ i

All main file entries are of the form ( dj,Dk ) wherev ( dj) = Dk. The diagram shows the directory entry
associated with some specified descriptor dj and thecorresponding main file entries. Thus multilist fileorganization can be characterized by:(1) T ( d ) :: = {dv(d): R (R(d))/ V (d) = X] UR (d)The serial file(2) Q(D):: = {Dd: T ( d ) , V d e A }A typical serial file entry is seen as follows:

dj

dj

dk

dm

Associated with each document D is a set R (D) of des­criptors dj. Recall that T(d) is the set of all documents
associated with descriptor d. Let Q ( D ) represent the setof all descriptors associated with (contained in) document
D. The serial file may then be characterized by:(1) T(d):: = {dD: R ( D ) , V D s D}
(2) Q ( D ) : : = R ( D )Thus T(d) is found by the following process. First d iscompared to every element of the set R (D). If d is anelement of JR(D), D (the associated document identifier)is returned. The comparison is made for allZ> contained in
the set D.
The inverted file
A typical inverted file entry is reproduced below.
Dj

174

Dj

Dk

Dm

In each search of the descriptor file by the selector, theobject of the search is the set T{d).

The locator (R )Just as the selector searches the descriptor file in order
to extract the document identifiers associated with each
descriptor in the normalized query, the locator (R)searches the document file to extract the record associatedwith each document in the set (D) passed to it by theselector. This record may consist of the document title andrelated bibliographic information, an abstract, or an
extract. In any case, the contents of the document file
entry associated with the document are returned to theuser under the heading of ‘located documents’. We
represent the function of the locator as simply:

R: User *={R(D)\DeD}
where R(D) is the entire datarecord (entry) associatedwith document D in the document file.

information technology

The docum ent file
The document file is composed of a set of entries of theformi? (D), De D, which are the system’s representationof the corresponding documents. The information
contained within R (D) is determined by the criteria
applied by the document analyser. We assume that inevery case a unique document identifier D is associatedwith the document record R (D). The document analyser
may leave the document (data) input virtually intact,
operating only to construct the corresponding document
representation for the descriptor file. Consequently, thedocument as originally input may be placed unaltered in
the document file.
The document file, like the descriptor file, is considereda passive entity. Similarly, the representation involves
defining the file organization which is assumed to be based
simply on document identifier D (i.e., accession number)or perhaps on an ordering based on frequency of use. In
either case, document file organization is represented
simply as R (D ), where De D.
The docum ent analyser ( A)
The document analyser constitutes the second port ofentry for input external to the ISR system (the other being
the logical processor). The function of the document
analyser is to process the incoming data in order toproduce two outputs:• some indication of the content of the incoming docu­
ment, to be stored in the descriptor file along with apointer to the document in the document file;• a representation of the document itself (i.e., the system’s
representation of the document), to be stored in the
document file.
Obtaining the description of document content iscommonly called indexing.
The importance of the indexing task has been noted bynumerous authors. Automatic indexing techniques fall
into the general categories of permutation indexing, citationindexing, statistical indexing, and syntactic and semantic
indexing procedures. While the application of the tech­niques in each category requires quite different assump­
tions and utilizes different aspects of the data, all operateon the data with the same objective: to construct a set ofdescriptors that ‘ . . . somehow indicate the information
content of the document. . . ,23.
The second major task of the document analyser is theconstruction and the storage of a document representationin the document file. This representation would include a
document identifier, usually all the elements of a biblio­
graphic reference (author, title, publisher, etc.), and might
include citations, an abstract, an extract, or conceivably
the complete document text.
The indexing task may be quite complex, whereas
determining the document representation may be almost
perfunctory. Considering the indexing function of the
document analyser, Vickery 16 recognizes three stages in
the assignment of document descriptors:• scan of the text to derive those words, phrases, and/or
sentences which best represent information content;• a decision as to which of the descriptors are worthy of
being recorded in the descriptor file, in view of the
purpose of the system;

vol 3 no 3 1984

• the transformation of the selected descriptors into astandard ‘descriptor language’, the resulting terms ofwhich serve as the entry or entries in the descriptor
file.
We describe these three processes by three functions, i.e.,the document term formation function (AF), the document
term reduction function ( A D), and the descriptor determi­
nation function ( A P).
Docum ent term formation (AF)
Recall that the textual entry T associated with document
D is defined as a set of characters or symbols, i.e.,

T:: = a u a 2, . . . , a m = {a \ aeA}
Then the task of the document analyser (A) in processing
the document text is basically identical to the task of thelogical processor in handling the query. Using the sets/4s,
Ar , and/4r (as previously defined) we apply the document
term formation function AF to T as follows (where normal
left-to-right processing is assumed):

Af :V a e T( 1 ) 0:*- [a]/, ae As(2)
cue A*(3) a «- A, a eA r
Thus the function of the document analyser in document
term formation (AF) may be expressed as

A f : T f = {[a], | a *- [aj/, aeA s ;_L{a,} — [a]*, a,-e/4*;
a *- X, <xeA t \ aeT)
Then AF( T) = TF, and the document text TF now
consists of the token set {[a],}. Let t = [a],. Then

TF = {[a]i} = {t}.
Docum ent term reduction ( A D)
LetG =:: = {[g]}, the set of all nonsubstantive o r‘stop list’
terms, each of which is a token. This is the set of tokens
which are nonmeaningful (which do not add to the‘information content’ of the text being processed) in thecontext of this system. The token set A F can now be
reduced by removing stop list terms (elements of G) andvarious special character tokens (elements of /4s ).
ThusAj)\ Vt eTp(1) f \ teG(2) t \ te /4s andA d - T d — {f 11 — \ teG\ t — \ teA s ; teT
Then AD(TF) = TD and all the tokens of the reduced
token set TD are possible descriptor terms. Note that in
reducing the set of document tokens, one need notnormally be concerned with special tokens (such as
parentheses and logical connectives) which characterize
the Boolean query. Nor is there an associated recognition
phase, for the document text consists of unstructured
natural language. However, the document text, like thequery, must now be normalized (expressed in terms of thesystem vocabulary). Thus each document term (token)
must be validated and each valid document term trans­
formed into its appropriate representation in terms ofdescriptors.

175

Descriptor determination ( Ap)

Descriptor file maintenance ( AM)The basic operation of the document analyser is Ap, thedescriptor determination function. This function operates
on the set TD to form Q(D), the set of all descriptors
associated with document D. These descriptors are theninserted in the descriptor file via the appropriate filemaintenance function.
The criteria used in the selection of descriptors (by Ap)
is system dependent since a number of alternative indexing
techniques could be used. The basic function, however,can be expressed as:

Two additional functions remain to be accomplishedby the document analyser, and these relate to the filemaintenance requirements (i.e., the addition of a new
document D to the document file, with corresponding
changes in the descriptor file). For the descriptor file thetasks required differ according to the file organization
employed. We denote the maintenance function required
for the descriptor file by AM and represent the activities asfollows:

Ap\ V tsTj)(1) t — d, for t = d, de A
(2) t — A, for 19^ d, Vd e A
If a fixed descriptor (controlled) vocabulary is used, thedetermination of whether a particular document token t isa descriptor is easily made. If a controlled vocabulary is
not used, other criteria may be applied to limit vocabulary(descriptor) growth based on the frequency distribution of
document terms. Specifically, as discussed previously,
low-frequency terms with near-zero discrimination values
may be normalized via dictionary (thesaurus) reference,and high-frequency terms with negative discrimination
values can be normalized via the use of phrase dictionaries.
The medium-frequency terms may be used directly as
descriptors18.
Let T' represent the set of low-frequency document
terms which meet the specified criteria for expansion,
where T ' C 7)> There for each teT', there exists a set
N(t) (i.e., thesaurus class) such that N(t) C A. Then

AP: V te T
(1 ) t - N ( t )Logically the set TD has been expanded by the replace­ment of the individual document terms t by the corres­
ponding set of thesaurus class terms, N ( t). In practice,each such t may be replaced by a single descriptor (thethesaurus class identifier) associated with N ( t).
Similarly, consider the set of high-frequency document
terms T" associated with TD which meet the criteria for
reduction, where T ' C To. Then there exists a set M,
M C A, all of whose members are word phrases of theform [m» mj\, where each element of M is itself a uniquedescriptor, d. Descriptor determination in dealing withhigh frequency terms may be expressed as
V t e r ' 3 i_ U;, tjUM(2) {tj, tj\ «- d, de A
Subsequent transformations may be defined as

Ap: V t 3 t = d, de A
(3 ) t ^ d
AP: V t 3 t 9 i d, V d e A(4) r — A
Thus in a generalized system in which document termsof all frequency ranges are recognized, the descriptor
determination function^/, of document analyser activity
may be expressed as:

AP: Tp = {t\t *- N(t), teT;{tj, tj\ «- d, de A, V t e T ' 3 _L {tj, tj}eM;t — d, t = d, de A; t*~ A t¥=d, V de A;
teTD]
Then Q( D) = TP and A P(TD) = Q ( D ).

176

The serial file
A M: R( D) = {d\deQ(D)}The inverted file
A M: R( d) = {D UR( d) , Vde Q( D) }The multilist file
A A: R (D) = {d\ v( d) = A, V deQ ( D )}R ( d ) = D , V d 3 d e { Q ( D ) n A c]v ( d ) = i f (d))/v(d) = X j v d 3 d e { Q ( B ) n A}
In each case the file maintenance function begins with theset Q(D) produced by A D. Note that the capability
for increasing the descriptor set is shown explicitly for themultilist organization.
The serial and inverted file maintenance functions are
simple. In the serial file the descriptor set is assigned to a
document record, while the inverted file requires the
addition of a document identifier to the set of document
identifiers referenced by each descriptor d. For the multi­
list file, the first operation refers to the formation of themain file record, the second describes the formation of a
new directory record, and the third describes the settingof the main file link. In all cases the universal set ofdescriptors A is considered to be dynamic, i.e.,
increasing over time. After each new document enters thesystem and the corresponding modifications have been
made in the descriptor file, A changes as follows:
A = A U {d\deQ(D)\ or A = A U Q(D).
Document file maintenance ( AN)Along with determining the descriptor set Q (D) and using
it appropriately in file maintenance functions, thedocument analyser operates on the original text input T to
construct and/or maintain the document file. This func­tion ( A n ) involves only the construction of the document
record/? (D) and the addition of the document D to the setof all documents D. The function of the document
analyser in document file maintenance may be definedvery simply as

An : R ( D ) = a u a 2, . . . , am = {a | aeA } = T
as defined originally and D = Z ) U D .
In summary, the function of the document analyser(A) can be represented as

A:: = < A M(Ap(AD(Ap(.)))),AN( . ) >where the angular brackets enclose the two outputs of
document analyser activity.
SUM M ARYIn this paper, the authors present a high-level, functional
approach to the description of a generalized information

information technologyretrieval system. This description is based on a functional
decomposition of the system into modules and processes
and on an appropriate data abstraction.
Using a small set of operators or primitives, we provide
a description of all the processes of a generalized IR
system, from submission of the query to the receipt of the
final selected documents by the user. By this means, acomprehensive overview of the system as well as athorough description of its behaviour is produced in termsof the component processes and the interactions of theseprocesses in terms of inputs, outputs and the associatedtransformations. This nonprocedural description provides
a necessary foundation for subsequent formal system
specification.
The authors believe that the effort expended inorganizing and developing a comprehensive, unified viewof large, complex systems is well worthwhile in terms of
the potential it offers for improved understanding of thesystem and its behaviour. Moreover, such a description
focuses attention on the system in its earliest stages ofdevelopment, when many crucial decisions are made.
Erroneous decisions made at this point can prove to be
most costly in the final realization of the system.

ACKNOW LEDGEM ENTS
The authors wish to express their appreciation toProfessors Gerard Salton, Dina Bitton and Donald B
Crouch for their suggestions and constructive criticism,
Professors Fred Schneider and Abba Moitra for theirmost helpful comments on specification, and thereviewers for suggestions which contributed measurably
to the final version of this paper.

REFERENCES
1 Booch, G Software Engineering with Ada Benjamin/
Cummings, USA (1983)
2 Liskov, B and Zilles, S ‘Specification techniques fordata abstractions’ IEEE Trans. Software Eng. Vol
SE-1 No 1 (March 1975) p p7-19
3 Berg, H K et al. Formal Methods o f Program
Verification and Specification. Prentice-Hall, USA(1982)
4 Bjorner, D and Jones C Formal Specification &Software Development Prentice-Hall, USA (1982)
5 Zave, P ‘The operational versus the conventional
approach to software development’ Commun AC M
USA Vol 27 No 2 (February 1984) pp 104-118
6 Wegner, P ‘Capital intensive software technology,
part 2: Programming in the large’IEEE Software Vol
1 No 3 (July 1984) pp 24-31

vol 3 no 3 1984

7 Balzer, R, Cheatham, T and Green, C ‘Software
technology in the 1990s: Using a new paradigm’Computer V ol 16 No 11 (November 1983) pp 39-45
8 Winograd, T ‘Beyond programming languages’
Commun AC M (USA) Vol 22 No 7 (July 1979)
pp 391-401
9 Ambler, A et al. ‘Gypsy; A language for specificationand implementation of verifiable programs’ Proc.

AC M Conf. on Language Design fo r Reliable
Software, AC M SIGPLAN Notices Vol 12 No 3
(March 1977) pp 1-10
10 Biggerstaff, T ‘The unified design specification
system (UDS2)’ IEEE Proc. Specifications o f Reli­
able Software (1979) pp 104-118
11 Wasserman, A ‘Information system design method­
ology’ J. Am. Soc. Inf. Sci. (USA) Vol 31 No 1
(January 1980) pp 5-24
12 Wasserman, A and Stinson, S ‘A specification
method for interactive information systems’ IEEE
Proc. Specifications o f Reliable Software (1979)
pp 68-79
13 Leveson, N G, Wasserman, A I and Berry, D M‘Basis: A behavioral approach to the specification of
information systems’ Inf. Syst. Vol 8 No 1 (1983)
pp 15-23
14 Crouch, C J Language relations in a generalized
information storage and retrieval system Doctoral
thesis, Southern Methodist University, (USA) (1971)
15 House, R ‘Comments on program specification andtesting’ Commun. AC M (USA) Vol 23 No 6 (June1980) pp 324-331
16 Vickery, B C On Retrieval System Theory Butterworths, UK (1965)
17 Crouch, C J and Crouch, D B ‘An analysis of
document retrieval systems using a generalized
model’ In: Information Systems, Vol 3 Tou, J (Ed.)
Plenum Publishing, USA (1975) pp 219-237
18 Salton, G and McGill, M G Introduction to
Modem Information Retrieval McGraw-Hill, USA(1983)
19 Salton, G The use o f extended Boolean logic in
information retrieval Technical Report TR 84-588,
Department of Computer Science Cornell Univer­sity (January 1984)
20 Rubinoff, M et al. ‘Experimental evaluation of
information retrieval through a teletypewriter’Commun. AC M (USA) Vol 9 No 9 (September1968) pp 67-71
21 Salton, G, Yang, C S and Yu, C T ‘A theory ofterm importance in automatic text analysis’ J. Am.
Soc. Inf. Sci. (USA) Vol 26 No 1 (January 1975)
pp 33-44
22 Salton, G Automatic Information Organization and
Retrieval McGraw-Hill, USA (1968)
23 Bar-Hillel, Y Language and Information Addison
Wesley, USA (1964)

177

A P P E N D IX
Table A l.

Operators used in the functional description

Operator

Description/definition

Use:

Comparison

Compares element on left side of operator to every
element of the set on the right side of the operator( ,)Parentheses

Alters the usual left-to-right execution of Boolean
expression by giving higher priority to operations to be
performed within innermost nested parentheses

U, Cl

Union, intersection

Set operatorsCl

Set evaluation

Operates on any valid set expression to resolve theexpressiono

Logical (A, V)o denotes either member of the set of logical operators(with the negation operator omitted for the sake ofsimplicity). The operators have an established priority,
modified by the presence of parenthesesoX

oX :: = [xxox2 . . . oxmOT]

Token formation. The application of the operator o to the
setX to form a token (where square brackets denote thatthe contents of the bracket is considered a single token and(i{X) denotes the number of elements in the set X)

pM

p[x 1X2 • • •Token decomposition. The application of the decomposi­tion operator p to the specified token M to form a set of
tokens which together compose [x]-L X_LX:: = [X1X2 . . . x^x)]

Table A2.

= (Mi, M2, • • •, M„)

Set concatenation. The application of the concatenation
operator _L to the set X, concatenating consecutive
elements of X to form a single token

Basic definitions in the functional description

Notation

DescriptionD

A document (more specifically the identifier associated with a document which
represents the document within the system)d

A descriptor (token)

D

Set of all documents in the systemD

Set of all documents associated with (retrieved by) a specific queryA

Set of all descriptors in the system*(x)Contents of record r corresponding to record identifier x, or a set of items
associated with identifier x, or a mapping which associates with an identifier x a
set of items R{x)

Q(D)
T(d )

Set of all descriptors associated with document D
Set of all documents (document identifiers) associated with descriptor d

G:: = M

Set of all nonsubstantive words or ‘stop list’ terms, all of which are tokens(GOA = 0)

A:: = {a* i = 1, 2 , . . . ,juM)}

The set of unique symbols recognizable by the system, the system alphabet

Yv. = «i, a 2, • • . ,a„ = {a | asA]

The input query, an ordered set whose elements are members of A

T:: = a u <*2, • • •, am = {«|a£^}The document (surrogate), an ordered set whose elements are members of A

x ,:/(z )t if x$f[z)0 otherwise
Note: t is the value returned

178

information technology

Table A2.

continued

Notation

Description

A x ) / y =zr —x|--------^ < - / ( r )Lfalse y = z
true return rr —xAx)/y=z)--------’/■ -/(/■ )return r-false 'y = z
trueTable A3.

Notation used in the functional description

Notation

Description;; =={a | conditions(s)}YcDefinition
Equivalence
Set of all a, for which the condition(s)holds(hold)Any setNull set
Is an element ofReturn (to the user) of set on theright
Replacement of token (set) on the leftby the token (set) on the right
A Boolean operator (A, V)
Names a function F which is defined
via the notation to the right
For all
Such that
Token representing the null field(X-[A])
The complement of set Y ( T0:: =KA)a

The number of elements in the set A
Any element of the system alphabet

{}
0
£
<=

*
O
F:
V
9
X

\y\ytY})

[«]

A*
An
As
Ar
Av
Av

vol 3 no 3 1984

A
Any token
Set of all terminal symbols
Set of all nonterminals
Set of all special characters
Set of all alphanumeric characters
Set of all structural elements
Set of common punctuation symbols

179