POL: An interactive system to analyze large data sets

Computer Physics Communications 16 (1979) 147—157 © North-Holland Publishing Company

POL: AN INTERACTIVE SYSTEM TO ANALYZE LARGE DATA SETS N. ARMENISE and G. ZITO Sezione INFN di Ban, Istituto di Fisica di Ban, Italy

A. SILVESTRI Sezione INFN di Ban, Istituto di Matematica di Palermo, Italy

E. LEFONS, M.T. PAZIENZA and F. TANGORRA Scienze dell’Informazione, Istituto di Fisica di Ban, Italy Received 12 July 1978

This paper describes an interactive system to analyze large samples of collected data. The first application has been developed to ensure a significant improvement in the efficiency of data management in recent high energy physics experiments (ri-project). However, the system is also suitable in all experiments treating large volumes of experimental data. The relevant features of the system are: — the possibility to select a subsample of experimental data in real time with a response time smaller (by an order of magnitude) than other programs used at present; — the possibility to display data in monodimensional distributions and scatter-plots; — the possibility to store in real time selection procedures to be used later. Editing facilities are provided. A few different terminals (video or teletype) can interact with the system, that has been designed for a multi-user environment.

1. Introduction In high energy physics a major aid to experimental data comes from observation of monodimensional distributions and bidimensional correlations between relevant variables. In fact most of the computer time is spent for this analysis. The plotting technique cornmonly used implies two main operations: a) sequential read-in of ‘events’ (elements of the experimental dataset); b) selection procedures to analyze only ‘significant’ events (which satisfy the conditions). The response time to obtain one or more plots is essentially due to operation a) while the CPU time is strictly related to operation b). For analysis of very large volumes of data a reduction of the redundancy can be obtained by data compression techniques and this reduces the I/O time also. The input time can be further reduced if the input data are restricted to ‘useful’ data only, that is to the variables required 147

for the selection purpose only. The basic idea of the POL system is to attempt the most complete splitting of the data: the data used for selection purposes only and the data to be displayed. A fast sequential search algorithm, based on a three valued logic (see appendix), allows also a drastic reduction of CPU time in selection procedures. These are the main facts in achieving the short response time (the order of magnitude is 10 s for 1OES events) of the POL system.

2. POL description Fig. 1 shows the structure of the POL (Plotting On Line by direct access) system. The system has the following facilities: a short response time (10 s/10E5 events for an IBM 370/158); the possibility to define selection procedures at run

—

—

N. Arinenise etal. /POL: an intenactive system

148 query

creation database

Fig. 1. Structure of the POL system.

—

—

—

—

time using the Boolean form with parenthesis and logical operators as in the FORTRAN language; independence from the terminal used;

where n

the possibility to obtain mono or bi-dirnensional plots in a character representation, when a teleprinter or an alphanumeric terminal is used, or in a graphic representation for graphic-video or plotter; editing functions (creation of new procedures and implementation of the library, display or deletion of catalogued procedures and predefined conditions); the possibility to save the information in case of power failure; a large adaptability to different computers (the basic program is in the FORTRAN ANSI language).

(In the majority of experiments homogeneous datasets have to be considered: in this case each event has the same attribute set.) To avoid any loss of information, it would be necessary to transfer n X m data in the memory. The transfer implies a long time for a large sample of events (n 1 0E6). In order to minimize n X m, it is possible to use some kind of index; in this way the amount of data effectively transmitted can be reduced to ~ielements, for a certam ~i.This method is not effective in the case of very large values of n and i~ when, for instance, ~ 0.1. On the contrary, it can be more effective to take the in-reduction into account. Two ways are practicable: a) the mere transfer of the most widely used attributes, and the possible computation of missing attributes under user’s request; b) the grouping of the m attributes in sub-relations thus creating an exhaustive number of partial datasets; each one has degree r (r < m) and contains r attributes, which are interesting to analyze as correlated variables in a scatter-plot. The POL system works under the second condition, creating direct access data sets of degree r (called MULTIPLOTS), which are predefined by the user (fig.2).

3. Database organization The organizatioi~of the database is important to minimize the response time. The method used in the POL system, which is described in this paper, has been proposed in refs. [1] and [2] to be used for experimental data analysis. Experimental data can be represented as a set of ordered m-tuples: (a11, a12,

...~

aim)

is the number of elements (events) in the dataset, m is the number of attributes for each event and a11 is the ‘value’ of the attribute! of the event i.

N. Armenise etal. /POL: an interactive system *MPL 1 790 FIRST MULTIPLOT *MPL 2 900 SECOND MULTIPLOT Fig. 2.

114

15

16

17

901

902

903

9014

Commands used to build MULTIPLOTS.

Each attribute can be also inserted in different

(l)

x1~)variables, for which the hth variable is the logical TRUE if Ph 1S verified (p~is a simple condition, including one or two variables and/or external constants). The variables x1’s are called TEST. Fig. 3 shows a list of a few control statements (TESTS). The system’s logic requires that all single conditions should be defined during the creation of the database; the Boolean functions can be performed too during the dataset enquiry. The set of single conditions defined by the user is computed once for all for each

Xfl~,

event and then it is memorized as a Boolean vector in

...,

MULTIPLOTS. In order to introduce a proper description of the other dataset (the dataset of conditions, called TEST), it is useful to make use of an example. A typical request-command to the database can be seen as the codified form of a wide sentence: “Display the values of variables aki versus ak2 for the events for which the condition (Pi, P2~ P1) is true ‘

.

The ‘condition’ is a Boolean function of (x11, TEST

20

149

13

...,

ICT

EXISTANCE OF PRIMAPY VEPTEX TEST 8 iS BTW —135. —105. X RANGE FOR ‘PRIMARY VERTEX TEST 9 16 BTW —1.5 1.5 V RANGE FOR PRIMARY VERTEX TEST 10 17 8Tl~ —1.5 1.5 Z RANGE FOR PR WARY VEP IEX TEST 43 8 AND 9 X—’V BOI..NDARIFS FOR PRI~ARY VERTEX TEST 44 43 AND 13 X—Y—Z PCUNr~RIES FER PRIMARY VERTEX TEST 1 44 AND 2) EXISTENCE flF PRIMARY VERTEX IN TARE,ET REGION TEST U 14 1F3 2. I PRONG EvEN) TFST 12 16 119 3. 2 PRONGS EVFNT TEST 13 14 IrE 4. 3 PRONGS EVENT TEST 14 14 lEE 5. 4 FR[NCS EV~NT TEST 32 999 119 2. CI-APGF +2 TEST 31 999 IFO 1. CHAUCE +1 TEST ) IFE 0. CHAPOF 3 TEST 21 cR9 lEE —1. CHARGE —1 TE~1 22 99’~ lEE —2. CHA9r-E —2 TEST 45 932 ~TW )•75 1.05 t.rLrFON PEAK K+K— T~y~ 4A 2 NOT 45 NC NPUT~ON KsK— TEST 47 9)3 ~TW ).75 1.0 N FliT FUN PF AK P—P TEST 45 2 NET 47 NC NFlJTEC”~ P—P TPST 49 934 3T~ —3.35 3.35 Ft AcTIC °~AKPI—~ TE~T e(j 2 f~0T 49 P~C ELASTIC P1—P TE’T Si 5)1 FLT ~ANCF PT TEST 5? 933 8T~ —0.15 3.15 FA”.’CE PX Fig. 3. Commands for the definitions of simple conditions to be loaded in the TEST file.

150

N. Anmenise et al.

/ POL: an interactive system

a sequential dataset (TEST). In conclusion the primary relation of degree m is extended by means of two

At the start of execution the system must merely: 1) read into the memory the bit-string corresponding

datasets:

to the selected procedure, or compute a procedure

a) the direct dataset of relations (MULTIPLOTS) of degree r (r < k), which are suitable projections of

using a new condition;

the primary relation; b) the sequential dataset (TEST) of single conditions,

2) execute for each event simple operations on the Boolean vector corresponding to the event and the bit-string that represents the selected procedure.

in which there is one string for each event; and one

Generally, these operations require only a few micro-

bit for one single condition of the event,

seconds.

4. Selection logic In order to obtain a plot from an enquiry of type (1), it is necessary: a) to put in the memory the MULTIPLOT which contains the variable to analyze; b) to select the events fulfilling the ‘condition’; c) to display in sonic form the events thus selected. A detailed description of point b) is important and it involves the following steps: 1) syntactic analysis of the phrase describing the condition; 2) interpretation or compilation of the phrase; 3) selection of the events. By using an interpretative procedure it is not necessary to introduce new instructions in the prograni during the execution (in fact the procedure is executed in real time); but a certain amount of time is necessary to interpret the phrase for the selection of each event, so the response time becomes large when the nuniber of events is particularly large. On the contrary, in a compilative procedure, the cornpiled instructions must be added to the running program; moreover, other complications arise when the user wishes to hold a library of the selection proce-

dures. The selection method used in POL is based on the

three-valued logic proposed in ref. [3]: it allows the advantages of interpretation to be realised without the relative disadvantages, The appendix reports some concepts fundamental to the understanding of the method. The number of operations necessary for selection with Boolean functions is low and almost independent of the complexity

5. Structure of POL system Two different programs realize the creation and the management of the database. These programs are described in the next sub-sections.

5.1. Database creation This program has been written in the FORTRAN

language and produces the database previously described, reading a sequential dataset, that is generally recorded on a tape DST (Data Summary Tape), and contains the data collected by the experimental setup.

The program creates two direct access files: 1) the file of MULTIPLOT that contains the subsets (MULTIPLOT), that are the projections of the primary DST; 2) the file of TEST which contains the results of the evaluation of the simple conditions for each event. The number and the attributes inserted in the MULTIPLOT are specified by the user in the MPL cards, while the simple conditions to evaluate each event are written on the TEST cards (see figs. 2 and 3).

TEST 1 has the particular property to memorize in the MULTIPLOT dataset only the events satisfying the condition expressed in this TEST. In this way it is possible for the user to make a first selection of the events of the original DST. In this phase it is also possible to memorize in the dataset derived attributes that have been calculated as functions of original attributes in DST. The stages in the formation of the dataset are: ALGORITHM 1: (creation of dataset)

of the function and of the number of variables. Moreover every selection procedure may be represented

loop on the events of the DST; read one event;

as a string of bits, using only a few storage locations,

compute derived attributes (if this is requested);

N. Armenise etal. /POL: an interactive system

evaluate all simple conditions for the event; if TEST I is verified for the event then write the result of the evaluation of the file of TEST; loop on the multiplot; extract the attributes that are written on the MPL card and memorize them on the file of MULTIPLOT; end of loop on the multiplot; end of loop on the events; The access to two files (MULTIPLOT, TEST) is optimized if two different disks and long data blacks are used, 5.2. Management program This program performs two main functions: 1) the management of the interaction between the user at the terminal and the computer; 2) the construction of the mono and bi-dimensional plots; In order to make the program suitable for various

151

hardware configurations, these functions are performed by using two different modules sharing an intermediate direct access file. The module that constructs the plots must run on the computer containing the datasets. The computer reads all necessary data from the intermediate file, constructs the plots and memorizes them on the same fiie in a form independent of the terminal configuration. The steps through which plots are formed are: ALGORITHM 2: (construction of the histogram) read from the intermediate file the query request; make a syntactic control of the request; if all is o.k. then compile it; otherwise RETURN; read from the intermediate file the plot request; control its consistence; if the request is o.k. then seek the multiplot or the multiplots which contain the requested attributes to analyze; otherwise RETURN;

Fig. 4. Distribution on the video display.

152

N. Armenise etal. /POL: an interactive system

Fig. 5. Distribution on the video

display.

loop on the records of a MULTIPLOT; read a data block from the selected MULTIPLOT (or MULTIPLOTS); read a data block from the TEST file; DEl DI DC DI

loop on the events contained in the data block; evaluate the truth condition to select event; if the event is ‘significant’, increase the counter corresponding to the proper channel of the requested plot; end of the loop on the events of the data block; end of the loop on the data blocks of the MULTIPLOT; The module that manages the interaction with the user can be implemented either (a) on a specialized minicomputer or (b) on the same computer of the dataset; in the latter case it is possible to work in multiprogramming with the other module. Implementation (a) has been performed (see ref. [4]), using a cascade connection 1BM2250, IBMI 130—1BM37O/158 via BSC. Figs. 4 and 5 show a feasible distribution on the video display. Implementation (b) has been obtained using a keyboard terminal IBM2741 and a video terminal TEKTRONIX 4013 connected to an IBM37O/158 system. Figs. 6— 10 display some control cards and the corresponding distributions. Fig. 6 draws up the control statements, arranged for the terminal user. Returns to previous defined requests can be feasible since the intermediate file can preserve all control statements just assembled

list available commands. list parameters of last requested plot. — list selection condition used for the last plot. — list simple conditions stored in the file of TESTS. — list content of MULTftLOT file. DL — list content of procedure library. IST~0N — display last requested histogram,. ISTBiD — display last requested 2—dimensional scatter plot. ISTX — display X projection of last requested scatter plot. ISTY display V projection of last requested scatter plot. ISTO WORD LOW.EDGE BIN — request of histogram of quantity WORD. PLOT WORD1 LOW.EDGE1 BIN1 WORD2 LOW.EDGE2 BIN2 — request 2-dimensional scatter plot of quantities WORD1 and WORD2. TEST algebraic expression containing ( ) * + definining a Boolean expression of simple conditions for the selection of events. (* means AND, + means OR, - means NOT). CPLT title of PLOT. CTES comment on the selection. RUN — start filling of requested PLOT. STORE - store last selection condition in procedure library. COPY N — use the condition N of procedure library for the next request of PLOT. DELETE N — delete condition N from procedure library. PRINT - make a copy of last requested PLOT or~ printer. STOP end terminal session. -

-

Fig. 6. List of available commands for iNc query of POL system.

N. Armenise et al. /POL: an tnteractive system

by the user. This is another relevant advantageous use of the intermediate file.

6. Control instructions The use of the PCIL system is explained in this section performing a preliminary analysis of 100 000 events collected in the experimental set up at CERN (European organization for nuclear research). In this experiment the typical event that had been recorded was: 0 (2) irp -~jc~ + ic~+x where c~corresponds to a positively charged particle (if4, k~,P)’ = number of positive particles, c corresponds to a negatively charged particle (ii—, k~,~), number of negative particles, x0 vs. x corresponds to neutral particles (one or many not detected). The events belonging to reaction (2) had been collected on a sequential Data Summary Tape of about 30 attributes for each event. The case of apparent violation of the total charge (j ~r i) is due to reduction of the efficiency detection of the set up for particular emerging tracks. The preliminary analysis, having the aim to insulate the reaction ir p k k + n —

-~

from (2) was performed by appointing two Multiplots of 5 attributes for event (fig. 2). The physical meaning of the attributes memorized in the multiplots is: 790 momentum of the incident ir~, 14 number of charged tracks emerging from the vertex of the primary interaction, 15 16— 17— coordinates (x,y, z) of the main vertex, 900 component of missing momentum in the mcident direction (Pr), 901 component of missing momentum in the transverse direction to the incident (PT), 902— missing energy squared in overall CM (Center of Mass frame), where one assumes c+ = k+, ck, 903 missing energy squared in overall CM, where c+p,c_ ~i, 904 missing energy squared in overall CM, where c+ = p, c = —

—

153

It is noticeable that only the attributes number 14, 15, 16 and 17 were present in the original DST, the others had been calculated during the creation of the dataset. Fig. 3 displays a list of simple conditions that properly codified for each event had been memorized in the TEST file. The predictable number of single conditions, is up to 160. Each condition occupies on the disk S words of 32 bits for each event. TEST 1 had been used to make a first selection of the events: in fact only the events that had the vertex in a confidence region had been memorized in the MULTIPLOT. Using the control instructions listed in figs. 2 and 3 the program has produced from the DST the file of MULTIPLOT and the file of TEST spending the time normally used by a traditional program to obtain run plots from the original DST. Now the user can interrogate the dataset using the control instructions listed in fig. 6, otherwise he can first create the library of procedures listed in fig. 7 with the control state-. ments ‘test’ and ‘load’. The following figures show the plots obtained on an IBM 2741 terminal from the analysis of the events that are memorized in the dataset. The first plot (fig. 8) displays the distribution of the incident impulse and it has been obtained by the control statements: isto7 9.5.0 cplt incident impulse test The blanks in the ‘test’ control statements point out that no selection had been requested. The second plot (fig. 9) displays the distribution of the coordinates y vs. z of the vertex. The controls are: plot 16 —2.5 .117 —2.5 .1 cplt y versus z of the vertex test

—

—

—

TEST 12*30*148*50 select ion of it k

channel

TEST 12*30*146*50 selection of p —p

channel

TEST 12*30*146*148

itp channel Fig. 7. Procedure library.

selection of

IJ\Cl[FNT 154

24440 23218 2lc~6 2C774 lccs? 11330 17ICF 1581( i4~4

134’i2 12220

1~PULSE XX XX XX XX

. . • . • . • • . • .

xxx XX”

XX>>’ XXX>’ XXX>’ XXX>’

xxx>’

•

XxXXx XXXXX

8554

• 7332 • (tiC . 4808 • 3666 • 24~s4 •

XXXXY XXXXXX XXXXXX XXXXXY

1222.

XXXX>XX X~>XXXXXXXXXX

X

/ / / / / 0.53CC 9.7CC3 9.03IC 13.1030 10.300’) 10.5000 10.7000 30JC000003003C)00035**~~’~810O0OD03)03O0)0300D00O0CC0003O00003 CCOCCCCCCCOCCC J033877741630000300000000000033000000000000000

CC00CCCCCC0CCC0C054~i9~27SE7CCC0OOCCC000000000OCO0OO00O00O0O0

3

300000000100003 570748035’~92411 3000000 00 )0)0000030000C0000000

1 2 3 4 5 6 1234567890123456780C1 234~78S0123456789012345678S01234567890 JNflER~L0W 66 OVERFLOW C

N0.EVFNTS ?~EAN OMFAN 0.0420150 C.0000916

IN THIS PLOT 99934 S.C. SKEW. 0.0289506 —3.0483896

CURT. —3.3425541

Fig. 8. Histogram of word 790 without selection of event. Y VS 7 flF VT’~ 1

• • • C 3~2 /

~

5

I 1 Ii ii I ~‘ 211 1 1 1 11121112621.111 12 ~ElAk.JVI96 1

11.

1

•

17

1

l 1 231:S~ ~~Th11 21 22~tct~$~7

•

—I:

‘

I 1 1

~4 ~

I 227~ ~ ~

•

ii

33$~~t~~ ~* ~ 4~~1~H1 ‘ 13111 ct~c~tc~~G2 t •15 ~11;H;f1~~’ ~ici ~

•

31

• —5. ~3J35/

4;r,

•

1

•

2~1’4~~ 1! ~‘c~41c.tc.iit~~

• • •

1~

t.~121 I 101 ~.4~~=r-f.

7r+ • ~ çt$ ~t. t1 ~ ~‘)G63 I t’:’~ ~xi, ~I .>/P. ‘7SrH 2 I ~flNfUNPLPCB’1F1)O72

•

RFSCFi~8GBCQ5>’745

• •

2111E7A4AA81057221 24572431~~22?

324 7153132

—1 .50000/

1

—? .50000/ / —2.5330 0

/ —1. EC0~ 1

/ —

C.

2

5C30

/ 3. 5)00 3

1.503) 4

2.5000 5

123456789012345678901 23456789012345678901234567890 12345678965CDEFGH11 MNOPQRSTtiVZJKWX’Y=’.~f+>,” M—?$

NO. OF EVENTS CUT OF NO. OF EVENTS I>’ THIS CLET

THIS

PLOT

130000

Fig. 9. Plot of words 16 and 17 without selection.

0

N. Armenise etal. /POL: an interactive system

155

(MISSING MASS K+F—)**2 1960 1862 • 1764 •

X

1568

XX XX

1473

X

• •

1372

•

1078

•

XXX

980 • CC? . 784 •

XXX

1274 • 117 .

686

508

450

XX XX

XXX XXX XXX

• •

XXX>’

XXXXX XXX X XX X X K X XX X XXXYYX >XXX X>XX)~XXXXX XX XX X X xxxx XXXXX. XXXXX> XX> XX XXXXXX>>X>XXXXXXXXXXxXXXXXXXXXXXXXXXXXxXX.

. 352 • 254 •

191 CF

• .

X >>>XYXYXXXXXXYXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX. >xx>x>>>xvs>y> ~)XX>XXXX>)~XYXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.

/

/

/

/

/

/

/

~fl.IOOO0 0.°?CCC 1.OCCOC 7.10000 3.9000) 4.90000 ~.90O0O 3C300030111)10333153300u3011000)0)030)33)303303000003)00030)0O 46323444334334343~s34333433333343333333333333333233 )0S11241O 8~57054339050672I430l9cl616C5I87625787s9O677y7?634421323191l 51533401 8533147188 CC 12071645326669473345342)89227538429015$339 3 1 2 3 4 5 6 17345673°3123456~8C312345~~8fl’~2345678q)I?345678SC123456789O 43~ OVERFLOW 6760 N5.F-VEF’TS TX THIS PLOT 24054 i7’~r1N s.r. SKEW. CURT.

2.7291561

3.31)6013

1.1441641

3.2721514

—1.2256546

Fig. 10. Histogram of word 902 of events satisfying the condition 12 AND. 32 AND. (.NOT.47) .AND. (.NOT.49).

Finally the third histogram (fig. 10) shows the distribution of the missing mass (k+kj squared when the two prong events, with zero charge, are selected and the possible events ~pn and/or elastic events irp are rejected. The control instructions for this plot are: ist 902 0 05 0

.

.

+

—

cplt (missing mass k k ) **2 test 12 * 30 * (—47) * (49) + ctes selection of the channel k k

tions memorized per event. Therefore there is a variable number from 150 to 300 of accesses to display a plot since the simple access time is 25 ms, taking a loss of synchronization of ~30% into account, a total time of 9 s is obtained to read all events. 2) The CPU time (about 10 machine cycles per event) necessary to move a record just read from the buffer to the process vector must be added to the previous time.

—

7. Elapsed time evaluation The time was evaluated for an IBM 370/158 syswhich has 32 bits/word and a machine cycle of 500 ns. The disk units are the IBM 3330 at 3265 words/ track. The response time for an histogram is affected by: tem

The reading time 1)100000 events occupy, on the disk, 150 tracks for each MULTIPLOT, as many as for the file TEST, when there are 5 attributes and 160 simple condi-

The CPUtime 3) The evaluation of the selecting condition is made by an assembler routine and spends 20—200 machine cycles/event depending on the complexity of the assigned Boolean function. 4) The proper counter (IND), corresponding to the X-bin for the ‘significant’ event, is addressed using the FORTRAN statement: IND = INT((X—ESTINF)/STEP).

5)

This instruction involves 100 machine cycles/event for a mono-dimensional plot (200 machine cycles for the bi-dimensional plot). The increase of the counter is also realized by a

156

N. Armenise et al. /POL: an interactive system

FORTRAN instruction that uses about 10 machine cycles/event, The solar time 6) It is a variable time and depends on the multiprogramnming conditions existing in the computer system where POLis running. This detailed analysis has allowed identification of some devices for optimizing the response time. In fact the POL system runs superposing almost entirely the elaboration time on the access time, so the time 1) is practically zero. Moreover the use of buffers in direct access has required the modification of the access routines of the operating system. Time 2) was called off processing the record in the reading buffer. Time 4) can be reduced only if one renounces the FORTRAN language.

three operators (monadic functions) that assume one of the logical values: 1’) The true operator ‘T’: T(xi) = ‘true’ if xi is ‘true’ T(xi) = ‘false’ if xi is ‘false’. 2’) The false operator ‘F’: F(xi) = ‘false’ if xi is ‘true’ F(xi) = ‘true’ if xi is ‘false’. 3’) The indifferent operator ‘I’: I(xi) = ‘true’ if xi is ‘true’ I(xi) = ‘true’ if xi is ‘false’. ln a Boolean notation, it results: ~ 0 1 T(0) F(0) 1(0)

= = =

0, T(l) = 1 I F( 1) = 0 I 1(1) = 1

T 0 1 F 1 0 I 1 1

, ,

Now we consider a Boolean form B that expresses a complex condition of some variables xi: B

B(xil, xi2

xik)

with k ~ n

and expand it in the distributive form or in the disjunctive normal form (sand * represent logical sum and product, respectively):

Acknowledgements This work would not have been possible without the help of the Data Elaboration section of C.S.A.T.A. —BAR!. We wish also to acknowledge the kindness of the mernbers of~l-co1laborationin permitting the use of the original DST.

B

=

(

~

Br) =

r = i,s

(

~

*

I’ = i,S

x~ij)for some if: if ~ n for a certain s pE(O,l) x0i = ~ii x1i = xi

Introducing the operator T, F and I the three-valued logical test corresponding to B is a set of n-strings:

Appendix

S{SrISr(~i,~ 2, ...,gl,3);r A three-valued logic

with çtj E {T,

Let X = (xl, x2 xn) be an element with n attributes. In the ordinary logic each attribute can only assume the objective value ‘true’ of ‘false’. A threevalued logicone canofbethe based on thesubjective idea that statements we can formulate following for each attribute xi (the use of the term ‘statement’ instead of ‘proposition’ is justified since the statement 3) does not have the universal meaning that it has in ordinary logic): 1) “The attribute xi has the value ‘true’ “.

2) The attribute xi has the value false 3) “The value of the attribute xi is ‘not relevant’ These basic statements are formally expressed by “.

l,s}

F, I) Vi

The one-one correspondence between B and S is obtamed by these simple rules (for each r): a) Br Sr 9i E Br and p = 1 b) ~ == F T if x E Br and p = 0 if x~i /lj = I if x9i ~ Br Example: let X = (xl, x2, x3, x4, x5). If we consider the form B (xl * 53) ~ (x2 * x5) ~

.

...

that already is in the distributive form, we obtain: Bl Sl

= =

xl * ,3 (TIFII)

B2 = x2 * x5 S2 = (ITIIT)

N. Arm enise et al. /POL: an interactive system

The evaluation of the form B on X is obtained in this way: represent the T, F, and I operators as —

T= —

/l\

(, 1 )

F=

/l\ ~) , 0

I

=

I0\ ~ 0

,)

replace in every Sr each operator with the representation now introduced. In such a case Sr becomes a (2xn) matrix (called selection’s matrix) whose elements are 0 or 1, assuming the form: Sr =

—

,

‘S1r~ S2r /

perform the following operations for r = 1, 2 s: a) Execute (Slr AND X). b) Compare the result of a) with S2r. If the result of the comparison is positive then the form B is true on X (i.e. B(X) = 1).

157

The strings Sr can be represented with strings of bits. This makes the algorithm of selection very quick (the a) and b) operations usually correspond to a single machine instruction) and minimizes the space necessary for the selection matrices. References .

[1] N. Armenise, G. -69/6 (1969).

.

.

.

Piscitelli

and A.

Silvestri, INFN/TC

[2] N. Armenise and A. Silvestri, INFN/AE-7l/9 (1972). [3] V. Capasso, A. Circella and A. Silvestri, Una logica a tre valori per il calcolo del valore di yenta’ di funzioni booleane complesse, Rapp.C.S.A.T.A., Ban (1971). [4]N. Armenise et al., Acts of 2nd Interdisciplinary Conf. of INFN, Nov. 1975, Ban (1976) p. 142.