Relational database compiled/stored on a memory structure providing improved access through use of redundant representation of data6519601Abstract A relational database compiled/stored on a computer environment for storing data about units of work includes a first set of tables and a second set of tables. The first set of tables includes first columns and first tuples and a first dataset containing first data included in the first columns and first tuples. The second set of tables includes second columns and second tuples and a second dataset consisting of second data. The data included in the second columns and second tuples being second data. The units of work including first services, final services and current services. The unit of work having a status being inactive, active or terminated. The second data is a redundant representation of a part of the first data. Claims What is claimed is: Description FIELD OF THE INVENTION
dkey omit sender sendTime omitter omitTime cdkey X
1 i Jeff 21.7.95 15:03:04
AAA
2 i Ann 22.7.95 09:33:12
BBB
If Jeff now omits the message sent by Ann the table will become:
dkey omit sender sendTime omitter omitTime
cdkey X
1 i Jeff 21.7.95 15:03:04
AAA
2 o Ann 22.7.95 09:33:12 Jeff 22.7.95 09:35:14
BBB
If Ann corrects the message that was sent by Jeff (and changes the content from AA to CCC, this update will be translated in an omit of the original message and an insert of the new message.
dkey omit sender sendTime omitter omitTime
cdkey X
1 c Jeff 21.7.95 15:03:04 Ann 23.7.95 11:12:13
AAA
2 o Ann 22.7.95 09:33:12 Jeff 22.7.95 09:35:14
BBB
3 i Ann 23.7.95 11:12:13 1
CCC
The actual insertion of the username, timestamp, etc. in the System header fields is not directly done by the application programs but is accomplished using "triggers". The three basic operations (insert, omit and correct) can easily be initiated in a standard way from each electronic form. The electronic forms in the present system all share a standard header of icons. Each of the functions is linked to an icon in the header. The formTools module of the present system generator handles the processing of these functions for all forms in a generic way. Due to the deletionless-ness, the physical level contains also a log of all versions of all messages. This has several advantages. The first is that whenever there is an argument as to what information was available at a certain point in time, the state of a message or group of messages that time can easily be reconstructed. Although only the programmers can query the physical level to retrieve previous versions of a message, some privileged users (the administrators) can retrieve a history of the versions of a message. This history lists who changed a message and when. If a user has questions about the version history of a message, the administrators can give him the names of the people involved. If necessary, the actual versions can also be retrieved and compared. The second and most important advantage is that every user is responsible for every bit of information he enters into the database. This is also the reason why the dkey and the sender's name are shown when a form is sent: it reminds the user of the fact that the database has accepted the message and stamped with his name. The unique number identifies this version and any subsequent updates can never erase this version. When changing or overwriting information in a written medical file, it can almost always be seen that some information was overwritten. In a computer this is not the case. The new version of a medical report looks as pristine as the previous one. This lowers the resistance to change information in an electronic medical record. The aim of the logging of all changes and the constant reminding to the users of this logging is to compensate for the lack of visual traces of the overwriting. Conceptual Data Model of the Generator The basic layers of the present system software are called the generator. In the conceptual data model of the generator, the deleted messages and older versions are logically omitted from the tables. A table at this level contains only the last version of each message. This level is used in all application queries and the physical level is completely hidden (except for the version history query for administrators). This level can easily be created by defining relational database views on top of the x# tables. By convention, the name of this view is the same as the underlying table but without the x# prefix. The definition of the view foo on top of x#foo is shown in FIG. 3. The structure of these views are simple, thus they do not hamper performance. To all intents and practical purposes this view behaves as the conceptual base table for all higher level data models. Therefore these tables are called table-views. Updates and deletions of messages should only be used in case of errors. This is only possible if the application data model is an additive model. This implies that a message should contain information all of which is known at the expected time of data entry by a single user. The user must be able to send all the information as a whole to the database. E.g. if two information items A and B are not known at the same time, but operational procedures require the data entry of item A into the system, then item B cannot be part of the same message (and part of the same electronic form) as item A. If it would, the procedure would force the user to guess the value of item B (or to leave it blank) when sending the message. When item B becomes known, the user would then have to correct the message. Such a situation is considered a data modelling error for an additive data model. Again compromises have to be made to keep the system ergonomic. Taken to the extreme every data item could be a different message. This would avoid the problem above since one never has to send two or more items on one form. In an ideal world with infallible and omniscient users the content of this level should exactly be the same as the content of the physical level. Conceptual Data Model of the Application This level is based on the conceptual model of the generator. This level defines the fields that hold the contents of the messages. An application data model defines an information stream. Each user (or function generating information) is localized somewhere on this stream. A user receives the messages from the people upstream and adds his information using electronic forms for the use of the persons downstream. This is exactly the same as with paper forms. A paper form is completed and then sent to the next person in the information stream. This person will probably generate new information and send it (back) to the next person in the stream. This data modelling strategy allows the users to take on a more active role in defining the data model. Usually the future are asked users to think as if they will re-engineer their procedures using paper forms. There are a few extra assumptions they are allowed to make because of the electronic nature of the forms: the forms arrive at their destination virtually immediately; a form can be viewed by several persons at the same time (there is no serialization necessary if two persons need the same information); parts of forms can be hidden for some (types of) users. The users can build their data model together with the analysts, so they understand what the data model represents. This transparency allows them to deduce which information functions are possible and which ones are excluded by the data model. This contrasts with the more classical approach where the analyst extracts the specifications for the different functions that need to be accomplished by the information processing system, and subsequently builds a data model to support these functions. When the user changes the specifications or when new functions need to be added, it is possible that these do not fit well onto the data model. The data model then needs to be adapted, which is costly. By taking on a more transparent approach towards data modelling the user can guard compliance of the data model with his world view. Benyon states that a data processing model is built from a data model and a process model. The data model represents the structure of the enterprise by modelling it in terms of objects and relationships between those objects. The process model focuses on the transformations which take place in the system. These processes transform the data through some manipulation, re-structure it more usefully, or relate it to other data. The data model and the process model respectively represent the static and dynamic features of the information model. Mapping one's data modelling technique on this type of data modelling, one could say that the process model is highly simplified. Processes in the real world result in only one type of change in the database: the addition of a message. No data are manipulated or restructured by any user originated function. This simplification adds to the transparency of the data model. As stated before, this simplification in data entry and manipulation leads to more complex deductions. So the price to pay is performance. This is solved by trading deduction performance for storage space and insertion performance as explained in the next section. Non-conceptual Tables (Application Level) Optimize Performance The message modelling technique treats a business process as a flow of messages. The status of a business process can be deduced from the presence and absence of messages. As an example, 5 of the messages involved in an outpatient visit are examined. A reception form is filled when the patient arrives (1). Then the patient is assigned to an assistant and a supervisor (2). The assistant will write a report after the visit (3) and the supervisor will validate this report (4). The secretary mails the report to the (external) doctor who requested the examination (5). Each of these messages can be sent by a different person. The messages have to be sent in this sequence. It is obvious that one cannot validate a report that does not exist but the system will also check that a report cannot be written if the patient is not assigned to an assistant and a supervisor. For each outpatient visit all four forms have to be completed (allowing a number of exceptions). The five phases describe a unit of work. The status of this unit of work called "ambulatory care visit" is the progress through these five phases. The phase the patient is in, and the next step to do, can be deduced from the presence and absence of the messages. This way the system will make worklists to show the users the specific information necessary to accomplish their work. E.g. the assistants will want a list of all patients that have been receptioned but not yet assigned. They will start from this list to divide the work among them. After assigning patients (sending the electronic assignment form) they will see and treat the patient. Later the assistant uses a list of all patients assigned to him but for whom no report is written yet, to start writing the medical reports. The supervisor will want a list of all unvalidated reports for patients assigned to him. Each of these work lists is defined as a view in the relational database 101. The structures of these views are similar: they select patients for which a particular message exists and another message does not exist. Only a small part of the tuples in each of the tables will participate in these queries, namely the tuples pertaining to units of work for which not all five phases have been completed. These units of work 111 are said to be in production. Most of the data will be on units of work 103 not in production: data about visits that have validated reports. For the work lists mentioned above most of the computational work is of the type "find tuples from table A for which there isn't a tuple in table B". For real life queries obviously more than two tables will participate in the query. The performance of the query will deteriorate as the size of the tables grows. In a medical setting historical data are so important the users want to keep information on-line as long as possible. This means that as the database grows performance will degrade. Two types of tables can be discerned: static and dynamic tables. Dynamic tables 105 grow in size at approximately the same rate as units of work are added to the database. E.g. the report table is a dynamic table 105: for each visit of the patient to the hospital one or more reports will be written. Static tables grow at a much slower rate, which is usually not linked to the amount of units of work 103. E.g. a table of definitions of radiological examinations will grow as more techniques for medical imaging or new machinery becomes available. Other examples are the tables containing doctor identifications, ward numbers and descriptions, medication lists, . . . These tables also grow, but several orders of magnitude slower than the dynamic tables. They usually contain hundreds or a few thousand records. Queries (like work lists) used to support the normal workflow are called production queries to discern them from management queries. Production queries need fast response times to assure a smooth workflow. Production queries can be divided in point queries and set queries. Point queries are queries that give all tuples pertaining to one known entity and has an indexed identifier. E.g. all reports for a single patient; or all assignment forms for a single supervisor. Set queries range over several entities and are usually of the work list type as described above. Point queries can be speeded up using indexes that are available in any commercial database system. Set queries also benefit from indexes but these are not sufficient to reach the required performance level. The solution found for this problem was using extra tables to store the information needed to speed up these queries. These tables contain only redundant information and do not exist from a conceptual point of view. Hence the name non-conceptual-tables 109. Status tables are non-conceptual tables 109 containing information about the status of a unit of work. The non-conceptual tables 109 make up an alternative redundant data model. It is a compressed data model since only the redundant information needed to speed up the selection of the relevant units of work needed in queries is stored. In a way the non-conceptual tables 109 act as semantic indexes to the data in the conceptual tables. Once the relevant units of work are identified the actual data are retrieved from the conceptual tables. To optimize the ambulatory care example, a status table should be needed with four attributes in addition to the four tables containing the messages for the reception, assignation, report and validation form. In this status table visitID contains the identification number of the visit, assigned contains 0 or 1 indicating the existence of an assignation form for this visit. Report also contains 0 or 1 indicating the existence of a medical report. Whenever a new unit of work starts, a record is created in the status table (see FIG. 4a). The tuple above indicates that a visit with identification number 7 is in production and that only the reception phase has been completed. When the visit is assigned to an assistant and a supervisor, the assigned bit is flipped from 0 to 1 (see FIG. 4b). When the medical report is sent to the database the report bit is flipped. When the report is validated the next bit is flipped. When the "sent" message is added to the database the record for that visit is deleted from the status table. Sending is the last phase so the unit of work is no longer in production. The status table (non-conceptual table 109) contains information on all visits: all visits not represented in the table are out of production; the visits that are in production can be in either of four states receptioned only receptioned and assigned receptioned, assigned and reported upon receptioned, assigned, reported upon and validated (i.e. no status record is present). Time is also represented differently. In the non-conceptual tables 109 time progress is represented in the columns: as work for a unit of work progresses, values in the columns are updated. In the conceptual tables 105, time progress is represented in the rows. Completing a phase in a unit of work 103 means adding a rows to a table (see FIG. 5). The status table (non-conceptual table 109) allows to rewrite queries that test for the existence of messages and make them more efficient. Assume that all visitIDs and patient names of visits that still needed to be validated by supervisor A are wanted. Without the status table this means going through the "assigned" table and for each visitID assigned to supervisor A go through the report table and check for the existence of a report with the same visitID. For each of those reports, check in the validation table whether they are already validated or not. For those for which no validation tuple exists, retrieve the patient name from the reception table. Both the "assigned" table and the report table are dynamic tables. Most of the records in the assigned table have validated reports since only a limited set of all data will be in production. So the existence test for a record in the validation table will most of the time find that the report is already validated. The same query is much faster to compute using the status table (non-conceptual table 109). Since it is very much smaller, it allows to find the units of work 111 that are still in production much faster. This will be shown in the following experiment which is part of the query that supervisors use to retrieve the list of reports they have to validate. Experimental Proof of Performance Gain As an example (a part of) the query to retrieve the validation list for a supervisor in the clinical workstation is shown. The query retrieves the list of reports that need to be validated by the supervisor assigned to handle that unit of work (i.e. a patient contact). In the case of the supervisor used in the example, the query returns 6 rows (i.e. 6 reports need to be validated). Six conceptual tables take part in this query. A short description of these is given in Table 1. In an experiment, 3 versions of the same query were shown and their performances were compared. The first version is a straight declarative implementation of the query. The second version uses the non-conceptual tables to enhance performance. The third version does not use the non-conceptual tables but is written more procedurally to help out the optimizer. To compare performance, the time spent in evaluating the query and the number of times each table was scanned to find the solution were measured. The query optimizer can choose to access a table more than once because it does not find it optimal to do all data retrieval in one access. Usually the table will be scanned several times during one access. Sybase allows to print out the order of accesses (the query plan) but it does not tell which data where retrieved in each access. The Version The first version does not use the non-conceptual tables. The query is written as one declarative select statement and all optimization is left to the query optimizer (see FIG. 6). The query optimizer only has syntactic information and thus does not "know" that most of the reports in the report table will be validated ones. The order of accesses and the use of an index in the access is listed in Table 2. The complete query plans for all three queries are listed in Table 3. From the order of accesses, it can be seen that the server chose a path in which it needs to access the x#verslag en x#validatie tables several times before it has identified the units of work that are relevant. Once these are identified, it accesses the other tables to retrieve the attributes that need to be displayed. In Table 4 the performance results are listed. Query 1 took 129 seconds to complete. Most of the time was spent in scanning the x#validatie table to resolve the "not exists" test in the subquery. Version 2 The second version of the query uses the status table and is listed in FIG. 7. The status table not only stores flags to indicate which phases have been completed but also the identification of the supervisor and the assistant to whom the unit of work is assigned. This means that both the selection based on the supervisor and the selection based on the existence of a validation can be done simultaneously on the status table. The name of the patient is also stored (redundantly) in this non-conceptual table since almost all production type queries need to show patient names. As in query 1, this version is written as a single select statement and all optimization is left to the optimizer. An optimizer always tries to reduce the number of tuples to be processed as early as possible in the query. The optimizer has no problem identifying the optimal path for this query. It has three selection criteria (s.usernameSup="x163646", s.verslag=1 and s.validatie=0) on the statusContact table which also happens to be the shortest table. From this information it surmises that the biggest reduction in tuples to be processed can be gained from accessing this table first. This results in dramatic speed increase (elapsed time less than 0.5 sec). As can be seen from the query plan in the appendix, the query now accesses first the statusContact table using the index on supervisor, immediately identifies the 6 units of work that are relevant and accesses the x#S9User and x#verslag table to retrieve additional attributes not present in the status table. The number of table scans is thus greatly reduced. The problem with query 1, is that the optimizer builds a non-optimal plan. Its heuristics can only use information from the structure of the query, the length of the tables and the presence or absence of indexes. It cannot use the semantic information that the application programmer has. In the case of query 1, the optimizer takes the wrong decisions and becomes a "pessimizer". In such cases an application programmer can increase the performance by enforcing a more optimal execution order. This is usually done by splitting the query in parts. The query optimizer will still optimize each of these parts but cannot change their execution order. Some of the advantages of SQL are lost this way. The query is harder to read, takes longer to write and if the length of some of the tables changes fundamentally, the optimization has to be redone. Nevertheless, this technique is often unavoidable for very complex queries. Version 3 The third version of the query does not use the status table but is optimized by splitting it in three parts (see FIG. 8). The first part creates a table containing the identifiers for the units of work assigned to the supervisor. In the second part, all tuples pertaining to units of work that are already validated are deleted from this table. With the resulting identifiers, the other tables are accessed to retrieve the attributes that need to be displayed. This sequencing of the computation is imposed because it is known that only a small percentage of the reports needs to be validated. Because semantic information is used (which is unknown to the query optimizer), this optimization technique is called semantic optimization. This query is much faster than query 1 but still more than 7 times slower than the query using the status table. Although the number of scans has been dramatically reduced, the first two parts of the query that identify the relevant units of work have more processing to do than using the status table: the x#validatie table needs to be scanned for all reports that are assigned to supervisor "x163464". Query 2 is by far the fastest query especially if one looks at the CPU time. In query 1 CPU time nearly equals elapsed time. This means that the query is CPU bound: the CPU is the bottleneck. Query 2 needs less than 100 ms CPU time (Sybase reports CPU time in units of 100 msec) so most of the 446 msec is spent waiting for disk access. The actual processing is very light. Query 3 is situated in between. Apart from the performance advantage, query 2 also is much more readable than query 3. As the number of units of work in the database increases, the performance of query 1 and 3 will deteriorate since both of them need to scan tables that grow with the number of units of work. Query 2 scans the statusContact table. This table will remain in a steady state if the workload on the department does not change fundamentally. The number of accesses to other tables does not depend on the total number of units of work in the database but on the workload of the supervisor which will also be in steady state. The actual accesses to these tables are indexed accesses and thus only deteriorate logarithmically with the response time. Using non-conceptual tables is trading in insert time and disk space for shorter query time. The redundant tables are kept up to date and synchronized with the conceptual tables using database triggers. Inserts become slightly less performant because at insertion time redundant data have to be updated or added in the non-conceptual tables. This is analogous to indexes. These also contain redundant data, and adding indexes to a table slows down insertions but speeds up queries. Because triggers are used to maintain the non-conceptual tables no extra overhead is placed on the application or on the network traffic between the client and the server. All overhead is on the database server. At the start of a unit of work (e.g. the reception form in the experiment above) the insert in the reception table also causes an insert in the status tables. All subsequent phases in the unit of work cause updating one or more fields in the corresponding record in the status table. Usually an insert causes numerous checks to be done by the database server. E.g. when an assignment is made to an assistant and a supervisor, the system will check if the identifications in the assignment form exist in the identification table for MD's. If one orders a radiological examination, the system will check if this type of examination exists. Often several of these types of checks will take place during the insert process. Usually an insert takes a few milliseconds so the additional overhead of maintaining the non-conceptual tables is negligible for the end users. The other price to pay is disk space. The overhead here is low (see Table 4) and decreases as the database grows because the ratio of units of work in production versus historical units of work decreases. The number of records on a status table remains relatively constant when the department is in a steady state, that is it finishes as many units of work as it starts. There may be some fluctuations in the number of units in production (seasonal changes, shortage of personnel, . . . ) but eventually a steady state has to be reached. What is gained is query response time as illustrated in the example above. Since a message is inserted once but queried many times the benefits clearly outweigh the costs. A relational database not only optimizes the query paths but also memory management. Often used data are kept in main memory because the server anticipates that they will be used again and wants to avoid the overhead of disk access to retrieve them. Since most of the production queries use the status tables and most of the users use (only) production queries in their daily routine, the status tables are constantly accessed. Because they are small they can reside completely in memory. This has an additional positive effect on query response times because most of the accesses to the status table will only be logical reads (only in internal memory) and no physical reads (disk access). In conclusion there are 3 reasons to keep the status tables small: the less redundant data there is, the less synchronizing needs to be done at insertion time. the smaller the status table, the more chance there is it will stay memory resident. use of disk space. At current disk storage prices the third reason hardly plays a role anymore. The first two have to be offset by the gains in query performance. Separating Design for Performance from Design for Expressivity Maybe the biggest advantage of using non-conceptual tables is that less compromises need to be made in the conceptual data model to ensure performance. In the present methodology, the design for representation and the design for performance are split over different data models. This gives much more freedom in the representational aspects of the data model. The conceptual tables are externally visible through the functions in the system. The non-conceptual tables are invisible to the users. If in time the query patterns change and other functions need to be optimized, non-conceptual tables can be added or changed easily and then rewrite the queries to be optimized to use these tables. The data model as the users see it, remains unchanged. Recovery Time The non-conceptual tables allow the database to grow while query performance degrades only with the logarithm of the database size. This removes one bottleneck to unlimited database growth. The next bottleneck that will arise will be recovery time. The larger the database, the longer it takes for back up or to reload it from tape in case of media failure. Although this is a much less stringent constraint on database growth, it cannot be ignored. For each of the databases, it must be determined which is the maximum recovery time allowed. This, in combination with the maximum backup-and-restore bandwidth, will determine the maximum size of the database. Effect on Database Size The amount of corrected or omitted messages varies greatly from table to table. E.g. the assignment form for patients on a ward is corrected each time the physicians are assigned to new wards. The reports table contains many logically deleted reports since even a minor correction like for a typing error causes a copy of the report to be saved. All overhead in other tables is dwarfed by the overhead in the reports table: not only is this the table with the highest number of corrections, it is also the table with the biggest rows. Each report text field takes up at least 2 kilobytes Architecture Where the clinical workstation is used in direct support of the clinical work, X-terminals are preferred for their robustness. On private desks or for secretaries a personal computer is more suitable. Robustness is less of a problem here. These machines are usually less critical to the operation of a department than e.g. the clinical workstation in an operating theatre or a nursing ward. Hardware Architecture Conceptual Network Architecture The conceptual hardware architecture of the present System consists of three layers: a presentation workstation, an application server and a database server. These are connected by a network and act as a single system (see FIG. 9). For each of the three conceptual tiers different physical machines are used. This allows to choose a hardware configuration for each tier that is optimally tailored to its function. Presentation Workstation The presentation workstation only runs the presentation software and holds no application logic. No "programming" is done on this machine. This is the machine on the desktop with which the user interacts. The system needs to be capable of running a graphical user interface but should be controlled by programs on the application server. For the first two implementations of present System (Surgical Pathology and Radiology) Macintoshes where chosen as presentation workstations. The Macintosh was at that time (1990 and 1992) the most cost effective system capable of running a graphical user interface: it had a graphical operating system, networking was built in and it was easy to administrate. As already mentioned, X-windows was chosen as the user interface software for the clinical workstation. This software can be run on PC's, Macintoshes or specific hardware called X-terminals. These are "intelligent" terminals capable of running a graphical user interface but without the need to store local software. X-terminals look like workstations. They have a processor and internal memory but no hard disk. When an X-terminal is started up ("booted"), it connects to a host computer which uploads all the necessary software. This is the reason why no local hard disk is needed. They are also easier to administer since, after installation, hardly any local interventions are needed. The X-terminal has a local processor and memory but this is only used for the processing and data storage needed for the presentation software. The absence of a hard disk and lack of local software makes the X-terminal much more robust than a personal computer. These machines rarely crash since they have no moving parts. If they crash they can be swapped for a similar model without much effort since no local files need to be transferred from the old machine to the new one. The cost of client-server solutions is much higher if one works with personal computers as compared to X-terminals. By '93 the cost of an X-terminal was higher than that of a Macintosh, but the difference was so small that it was offset by the cost of migration halfway through the project. While the X-terminal lacks the disadvantages of a PC, it also lacks the advantages of the PC. No local processing is possible and the standard office automation packages that are widely available on personal, computers have no real counterparts on the UNIX machines that usually acts as hosts to the X-terminals. The X-windows software that runs on the X-terminals, can also be run on personal computers. In those places where one workstation is used both as a front-end to the hospital information system and for office automation, a Macintosh is placed with X-windows software. Since the application server converses with the presentation software via the X-windows protocol, no additional programming needs to be done on the application server to support this configuration. Application Server The application server runs the present System environment. All application programming (with the exception of stored procedures, views and triggers) is done on this system. The application server controls the presentation workstation via the X-windows client software and is a client to the database server. Only transient data that are not shared by multiple users is stored on this system. This allows to have many application servers because each can function independently from the others: all data that need to been seen by other users is sent to the database server and all application servers are connected to it. The application server executes CPU intensive tasks. Events from the windowing server trigger some Prolog programs. This results in issuing commands to the windowing server. Sometimes data from the database server will be retrieved. But no large amounts of data are processed on the application server. The disks on this machine are only needed to store the operating system (and other software necessary to exploit the machine), the programs for the clinical workstation and swap space. Each Prolog process requires on average 22 Mb of virtual memory. The ratio of physical memory over virtual memory is influenced by the expected number simultaneously active users and the number of functions in the application. The more functions in the application, the smaller the procentual part of the program that will constantly be used: a user can only do a few things simultaneously. Since each user has a specific task, he or she will only (repetitively) use and keep using a subset of all possible functions. This is called locality of function. A receptionist will fill in reception forms and continue to do so for most of the time. Due to locality of function the part of the program that is needed in physical memory (the resident set) will not change during the use of the application by the same user. Database Server The database server runs only the server part of the database. On this machine all data that are shared between users is stored. There is only one database server for all application servers. The database server receives SQL commands from the.applications via the Sybase client software. No System programs run on this machine but some application knowledge resides on this system in the form of database triggers (used for consistency) and procedures (mainly used for reporting). By using a separate machine as database server, its configuration can be tailored optimally to its use. The database server handles large amounts of data so this machine needs to be able to handle large volumes of disks. Most manufactures have machines in their product lines that are specifically geared towards database operations. Example of the Processing of an Event in this Three Tier Architecture Suppose a user presses a button on a dashboard to retrieve the medical report linked to a particular hospital stay (see FIG. 10). When the user presses the button (1), the X-windows server detects this event. (2) The windowing server notifies--via the network--the windowing client on the application server of the event. The client triggers the execution of the program written to handle this event. (3) The program will prepare an SQL statement to retrieve the report. (4) A Sybase client function is used to send the SQL--again via the network--to the Sybase database server. (5) The database server executes the SQL statement, retrieves the data from the database and (6) sends them to the client. (7) The present System program on the application server uses several Sybase client functions to read out the data. (8) Using X-windows client functions, it creates a report window on the X-terminal (via the network) and (9) displays the data using this report window. Physical Network Architecture In reality, the three types of computer are not connected to each other serially. The physical network architecture uses a backbone Ethernet network to which the application servers and the database server are connected. These reside in the Main Equipment Rooms (MER). From the MER fiber optic links are made to Satellite Equipment Rooms (SER). This is called the "vertical" cabling. A SER is a small room containing a patch panel. Each network outlet is connected point-to-point to the patch panel in a nearby SER. This is called the "horizontal" cabling. A universal cabling system is used for this connection. By making minor changes at the outlet and placing the appropriate active components in the SER, these cables could be used to support the most common network and terminal protocols (Ethernet, token ring, AppleTalk, RS 232, IBM 3270, . . . ). The active components in the SER are connected via vertical cabling to the servers in the MER. The main advantage of this cabling system is that a building can be cabled when it is constructed. It is not necessary to know the type of network connections in advance. Also, no cables have to be replaced if network services need to be changed for a particular room. E.g. if a user changes from a terminal to a PC or X-terminal, his network outlet needs to be reconnected in the SER to another active component. Possibly the external plug needs to be changed. The cabling needs no changes. Upgrading the network to handle higher throughput (e.g. switched Ethernet or ATM) will be done the same way. The disadvantage is that to keep the system universal some constraints have to be taken into account. The distance between the SER and the network outlet cannot exceed 100 meters and has to be a point-to-point connection. This means that enough network connections need to be foreseen for each room since it is not possible to connect a workstation via another workstation. The Scaling of the Present System Since present System will take a few years to install hospital wide, the system will need to be scaled during that time. The effect of scaling on the three tiers of hardware will be examined. Three dimensions of scaling are considered: the number of users, the size of the application (as the number of functions grows, the amount of program code will grow also), and the amount of data stored. It will now be investigated what needs to be done on each of the hardware levels to accommodate the growth in each of these dimensions. Presentation Workstation This is the easiest level to scale: one is added per workplace. The amount of data in the database does not influence the parameters of this workstation because the user will always require lists of a length that can be read on screen. It is no use to let the report lists grow as the amount of data in the database grows. The same holds for the size of the application. While the number of windows that can be opened might grow, the number of windows simultaneously opened by a user is limited by what is ergonomically acceptable. If too many windows clutter the desktop, the user will close them automatically. For a given a type of function, adding more functions will not require a more advanced workstation since the user is the limiting factor and he will only use a small subset of this larger whole simultaneously. Application Server The application server also scales trivially with the number of users: each type of application server can accommodate a certain amount of users depending on its processing power and internal memory. Adding users means adding or expanding application servers. If the size of the application grows, more virtual memory will be needed per user since more program code and more data structures need to be stored in memory. Either more memory is added or more application servers are installed (adding both memory and CPU capacity). The amount of data stored does not influence the application server since these only pass through the application server which formats them to be displayed on the presentation workstation. Since the data are not stored and the number of records will automatically be limited by what can still be handled by the users, the amount of data that needs to be processed by the application server will not increase with the length of the database. Database Server The database server needs to be scaled with the number of users: more users means more simultaneous queries and transactions. Both memory and processing power will need to be added. Database servers do not scale linearly by simply adding hardware. The size of the application alone does not influence the load on the database server: the users will have more ways to view the same data. This might result in more usage of the computer but, since a user can only do one thing at a time, this increase will not be significant. If the amount of data increases significantly, more disks need to be added and probably more processing power and memory (if the response times of the queries are to be kept constant). The query performance scales logarithmically with the size of the tables due to the present data modelling technique. The data modelling technique does not solve the problem of multiple users simultaneously doing updates in the database. More users and more data need to be offset by adding hardware and smarter database algorithms. It is expected to have at the most 1000 concurrent users in the present System. This can be handled already by current technology. Database vendors are improving the parallellization of their servers and computers with 10 and more processors are state of the art. Therefore it is possible to scale a database to more than 1000 users. In conclusion, scaling the present System comes down to scaling the back-end database server. All other levels scale linearly by adding hardware. Software Architecture To separately develop applications for all departments in the hospital would require too much resources. The implementation time for the whole of the hospital would be unacceptably long. In order to speed up development, it is decided to develop a set of generic software modules first to serve as larger building blocks for subsequent applications. The software developed at the U.Z. Leuven can be divided in 4 groups: the System generator, the System tools, the builders and the clinical workstation modules. The Surgical Pathology, Radiology and clinical workstation modules all share the generator and System tools as basic building blocks. The first three types of modules are generic modules and will be discussed here. The System Generator The System generator consists of three modules that closely interact with each other. It provides a higher level interface to Sybase and X-windows and implements the concept of forms on top of a deletionless database in a generic way. The generator is not specific to hospitals. In FIG. 11, is represented the data ship between presentation and database. In an application, data are constantly shipped between the screen (the front-end, in the present case X-windows) and the database (the back-end, in the present case Sybase). In between, formatting, manipulation and checking of the data is done by the application. Procedures are specially structured application parts used solely for checking data integrity. The generator provides tools to do much of this shipping between front-end and back-end. Because of the use of the form metaphor, all parts of the application related with forms can be handled in a generic way. The three modules are: motifShell, messageTools and formTools. Their interaction is shown in FIG. 12. Modules can use lower modules but not vice versa. E.g. the application can use formTools, which in turn uses motifShell, which uses X-windows to display data on the screen, but motifShell can never call functions from formTools. MotifShell MotifShell is used to handle all presentation tasks in the present System applications. Roughly the module serves three purposes: a Prolog interface to Motif/X-windows, implementation of high-level interface objects, and speed-optimization. By having a generic module to handle these tasks, it is avoided having to redo this for every program or application, and the access to the X-windows presentation package can be standardized, thus facilitating maintenance. Prolog Interface The first purpose of this module is to shield the System programmer from the low level details of X-windows. All X-client functions have their Prolog counterparts and these are used in application programming. It is the Prolog version of the X-windows client software. Apart from this low level functionality, motifShell provides powerful high level predicates that automate part of the work of creating and managing windows in X-windows. The creation function of the window is generated by a tool called Builder Xcessory (BX). This tool is used only to design the window ("paint"). Only the resources needed to determine the type of widgets and their positional interactions (alignment to each other, determining which widgets manage other widgets) are set using BX. These are resources that are relatively fixed in time and that will need little maintenance. All resources that will probably need maintenance in the future are set in the Prolog application. This allows to generate the creation function with BX, link it to the System application and almost never touch it anymore. All maintenance can be done on the Prolog level. To speed up application development, a small interpreter was constructed to allow the setting of resources on a higher conceptual level. For each type of window ("shell") a data structure must be defined. This data structure contains high-level instructions to set or modify window parameters (see FIG. 13). A small program reads these and for each instruction there are one or more rules determining what low-level instructions need to be executed. One instruction can result in the execution of several low-level X-windows client instructions. Prolog is very apt to write these types of programs. Having such an interpreter speeds up application development because many complex tasks can be bundled in one System instruction. The interpreter is easy to maintain because the program that drives the execution of the high level instructions, uses a rule base to "decode" them. To add high level instructions, only add rules are needed. These rules can be maintained independently of each other. High Level Display Items MotifShell also defines very high level "widgets" such as the logicBox. The logicBox is a widget that maintains two representations of the data it handles: a textual representation used to visualize the data and a logical representation that is used internally and has a richer structure than pure text. The application programmer can use and manipulate both representations. The synchronization of both representations and the mapping of high level logicBox instructions onto the lower level widget instructions of X-windows is done in a generic way. The logicBox defines a set of rules that the programmer should supply to handle all application-specific tasks. The logicBox can be used to browse a graph. This is frequently used in the clinical workstation. Often the system has to present the user a set of options. When the user selects an option, a set of sub-options is presented. Selecting a sub-option might again list new options until the desired option is reached. This technique is used whenever the users needs to select from a list of options that is too big to show on one screen. E.g. there are over 700 Radiological examinations that can be requested. A graph structure is defined on top of this set that allows to "zoom" in on the examination wanted. Often such large sets of options need to be browsed by the users. The logicBox allows to specify only the variable parts in the form of rules. The structure of the graph (i.e. the relation between the options: the layers on top of other layers of options, and the possible paths to navigate through this structure) are specified using Prolog rules. The program code that navigates through the structure, updates screens, reacts to events, etc. is all generic code. It interprets the rules that were specified to decide on the appropriate actions. Another high level object is a table with the possibility to create graphs based on the data in the table. The table widget is used to display all kinds of lists in a tabular format. MotifShell provides several optimized predicates to access the table, sort, read out rows and columns, etc. . . GraphTools is a module that given a table allows the user to create pie charts, curves, bar charts, . . . based on the data in the table. A programmer's interface to graphTools exists to make application specific charts in one command. Optimization MotifShell also optimizes the speed of the interface. The creation of large and complex windows can require a few seconds. In the present System applications, the user often opens an electronic form just to look at the data content and then closes it again. To avoid creating the window each time it is opened, motifShell does not destroy the window when the user closes it but hides it. When the users wants to open the window again, motifShell makes the old window visible again. The programmer can specify which parts of the window need to be re-initialized when a window is re-opened this way. This considerably speeds up the opening of windows. The performance penalty of the real creation is only incurred once for each window. If a user wants a second version of the same type of window, motifshell detects this and creates a second copy. Upon closing this second copy is also not destroyed but hidden. The trade-off is memory: because the windows are not destroyed but hidden, the hidden representation still requires memory for storing it. MotifShell manages this memory usage and can decide to free up memory (by destroying a window) when needed. All this is completely transparent to the user: there is no difference between a newly created and a "recycled" window. The users will only incur the performance penalty related to the first-time creation of the windows, at the beginning of a newly started session with the clinical workstation. After all windows are created once (or more if the user wants more than one copy of a window simultaneously open) the system will be able to use almost only recycled windows. Most users will only open a subset of all the windows available in the clinical workstation because of locality of function. Due to locality of function, it is needed to store the hidden representation of only a subset to have all windows recycled for a specific user. While it is often more complex to optimize on a generic level, the pay-off is greater: all applications benefit from the optimization. The overall optimization is to optimize each and every program. MessageTools MessageTools is the lowest module on the database side of System and the only module which directly uses the Sybase client. MessageTools has roughly three purposes: implementing generic support for the conceptual data model of the generator, provide a higher level interface to Sybase than the Prolog--Sybase interface by BIM, and optimization. Generic Support for the Conceptual Data Model of the Generator The conceptual data model of the generator is based on a deletionless model. When the user inserts a message ("sends"), the system time-stamps it and stores the name of the user with the message. A user can delete ("omit") a message but the message is only removed from the view on top of the x#table by setting the omit flag to "o". When a user changes the data content of a message and sends this new content as a correction of the old message to the database, messageTools translates this operation into an omit of the old message, an insert of the new message and links the new message to the old one. To do this messageTools has program code that handles all messages in a generic way. It also uses specific SQL program code that was generated by formBuilder to handle those tasks that are too specific or would be inefficient to handle generically. MessageTools works on the conceptual data model of the generator. All manipulations of the physical level of the data model are done using triggers or procedures. Most of this SQL program code is generated automatically by formBuilder. High Level Interface to Sybase The application programmer only calls one Prolog predicate to do an insert, omit or delete. MessageTools will query the Sybase data dictionary to retrieve the necessary information to generate SQL instructions required to perform the database operation. One call to messageTools usually results in several Sybase client calls. Because it will itself query the data dictionary it is not necessary to add a patient messageTools each time a new table is created in the system. MessageTools is the only module that directly accesses the Sybase client software. The advantage of this approach is that all higher level modules are shielded from the idiosyncrasies of the Sybase client. Apart from making the access to Sybase simpler, this is also a maintenance advantage. Changes in the Sybase client software cause changes in one module only. Usually software changes gradually but sometimes total revolutions need to be taken care of. Sybase chose in '93 to change its client software: the current client software (DB-lib) is still maintained and supported but no new features are added to it. The new interface software (CT-lib) will gradually replace the old and it is expected that support for the old interface will be dropped somewhere in the future. MessageTools will be ported from DB-lib to CT-lib and if the changes to messageTools only can be contained, no application program will need to be adapted. Optimization MessageTools also optimizes Sybase access. Locality of function has as effect on the database that not all users will access all tables or views. MessageTools remembers the meta-data it retrieved locally. If a user needs the data again later in the session, messageTools retrieves it from its internal data dictionary without going to the Sybase server. Each user needs a "process" on the database server. The client passes SQL commands to this process which executes them and sends results back to the client. Opening a process each time an SQL command needs to be processed is too much overhead, and keeping unused processes open is inefficient. MessageTools manages process use. The application programmer specifies how many processes a user can keep open simultaneously. MessageTools will allow the opening.of extra processes but will close al superfluous processes after they completed their work. All this is transparent to the application. FormTools FormTools implements the basic System 9 metaphor: the electronic mailing of forms. It uses motifShell for the user interface and messageTools to access the database. FormTools accesses these modules via the same API (Application Programmer's Interface) as the System 9 applications do. In other words, formTools is an application to messageTools and motifShell. FormTools makes the connection between the visual representation of the message (the electronic form) and the database table used to store the message data. It handles all standard operations on forms in a generic way, again reducing the amount of code to be written. These standard operations can be invoked from the icon bar that resides on each System form. Their functions are briefly explained: Send FormTools checks the form procedures (see next section), sends the content of the form to messageTools which sends it further on to the database. The content of the form is stored in a table with the same name as the form. Only the content of the fields on the form with a name that is also a name of a column in that table are stored. Only the minimal data needed to reconstruct the form will be stored. These are said to be part of the message. The user does not need to specify which widgets are part of the message: FormTools accesses the Sybase data dictionary to retrieve the name of the columns and automatically builds the message from the content of the corresponding fields. If the message is accepted by the database (database triggers perform checks on the content and may cause the insertion to abort), it is assigned a unique key (the dkey). The dkey and the name of the user who sent the form are displayed in the right hand corner of the form. Receive FormTools will retrieve the content of all non-empty editable fields of the form. The resulting `selection record` will be used to generate an SQL query to retrieve all records having the same values for these columns. The result is presented as a list of records. Clear All fields of the form are cleared, that is, edit fields are emptied and check boxes are unchecked. Popup menus are reset. Initialize The form disappears and a new copy of the original form template is drawn on the screen. If an initialization function is associated to the form, this will be used to regenerate the form. Context Displays who sent the form and when. Omit The form is omitted (logically deleted: it is no longer visible in the table-view but still exists on the physical level). Correct After changing the content of the form the user can press this button to replace the old message with the new. What happens at the formTools level is highly similar to sending a form except that the dkey of the message to be corrected is passed along with the message to messageTools. Form Procedures, Initialization and Receive Rules If a form is defined correctly, System allows the user to add, omit and correct data without having an application program written for this. Sometimes the application needs to check the integrity of the data before allowing to store it or after storing data, the application might want to change something in another table or on the user's screen. This cannot be handled generically. To allow the application to interfere if necessary, form procedures can be defined by the application. Form procedures are Prolog rules that will be called by formTools before and after each send, omit and correct. E.g. there are four types of that can be associated with the sending of a form: beforesend, beforeSendOnly, aftersend and afterSendOnly. Since a correction is translated into an omission and a send, the beforeSend and afterSend are also called when a message is send to correct another message. Using these rules, application specific code can be executed between the generic parts. The before-rules are typically used to do checks on data integrity that are too difficult to express in SQL. The after-rules usually perform clean-up tasks (e.g. closing a window automatically if the form was sent successfully). Many rules of the same or different types can be defined for the same form. The initialization rules define what needs to be done when a form is opened. Usually these rules pre-fill the form with defaults (these may vary depending on the user, department, . . . ). The receive rule can be used to intercept the normal way of doing a receive on a form. This is used if the generic implementation of the receive would be too inefficient. The receive rule can deduct more efficient queries based on application knowledge by looking at the parameters that are constraining the search. Storing Only what is Needed When discussing the sending of the form, it ghas been stated that formTools only stores the content of the fields on the form that have a name that also appears as column name in the corresponding table. Usually there are many more fields on a form than the ones that are stored. E.g. many forms display the patient's name and number, but only the number is stored. This is common practice in designing a data model. The number is used as a reference to more data (in this case demographic data) so that if any of these change, the data need to be updated in only one place (the patient identification table). All other tables refer to the patient using the unique patient number and can retrieve the correct information from this table. If the data were duplicated in every table, the correction of a simple spelling error in the patient's name would require updates in numerous tables. Such a situation usually occurs many times on even simple electronic forms. The assignment form e.g. assigns a patient visit (e.g. an ambulatory care visit) to an assistant and a supervisor. The form (see FIG. 15) lists the name (first and last) of the patient, the number and type of the visit, and the ID, first and last name of the assistant and supervisor. Although all this information is necessary to allow the users to understand the form, only the visit number, the identification number of the assistant and the identification number of the supervisor are needed to express the relation between the patient's visit and the two physicians. The visit number is linked to the patient number via a reception table. The name of the patient can be retrieved from the patient identification table. Thus, only the three identification numbers are needed. If the form is to be understood by the users, the information linked to the numbers is to be displayed also. Because this occurs many times on all forms, a generic solution was opted for. Just as formTools uses the table-view definition (which defines the conceptual level on top of the physical level) to insert data, it looks for the receive view to display the form. The receive view has the same name as the table-view with r# in front of it. The receive view ties the information from the different underlying tables together. FormTools uses it to display data on the form. Just as with sending, column names in the view definition correspond to fields on the form. In a way the receive view definition acts as an application specific rule which is used by a generic application (formTools). It would be possible to specify the receive view in Prolog, but this would be much less efficient. Because it is specified as an database view, the receive view can also be used to create new views. High Level Interface Apart from being a generic application in its own right, formTools provides also a high level interface on top of both messageTools (Sybase) and motifShell (Motif/X-windows) to build specific applications with. Theoretically one could make any application just using formTools' functionality but this would not be ergonomically acceptable. Users want and need application-specific short cuts. This results in extra buttons and menus on the forms. FormTools provides predicates to manipulate forms that ease the implementation of such extra functions. Users view the contents of other forms usually in the form of (work)lists. A typical user permanently switches between querying the database and adding data. The handleQuery predicate allows to specify a query and the options to display the results; it sends the query to the database, retrieves the results and displays them. Since there are many parameters that can be specified, a small interpreter was written to generate the low level program code that corresponds to each of these parameters. There is of course an overhead in creating a predicate of the complexity of handleQuery but it pays off: almost all lists in System 9 programs are generated using this predicate. Conclusion The goal of the present System generator is to handle as much processing as possible on a generic level. This reduces the total amount of program code and thus increases maintainability not only through code reduction but also through standardization. The richness of the tools allows faster development. The drawback is that the tools have to be built and maintained themselves. The larger the system, the larger the pay-back of such an approach since more people and more program code benefit form the same set of tools. The present System generator is and has been constantly improved. Each repetitive programming task is scrutinized to see if it can be split in a generic and an application specific part. If so, and if it is expected to need the generic part in the future, the generic functionality is added to the appropriate module or a specific module is created. This way, the generator is constantly refined. Jean et al. advocate the use of a homogeneous platform to integrate all modules of a clinical workstation. The authors discern 4 aspects of integration: data, presentation, communication and control integration. The System generator tackles the first two of | ||||||