Patent Publication Number: US-5423038-A

Title: Specialized data management method

Description:
BACKGROUND 
     1. Field of Invention 
     This invention relates to a method of data management, and more particularly, to a method of data management wherein the characteristics of the data elements being collected are known. The exemplary embodiment of this method is a vote data management system. 
     2. Description of Prior Art 
     Data management technology exists because the computer source code for all data-intensive computer applications can be organized into three quite distinct modules: the user-interface functions, the application functions, and the data-serving functions. Conventional data management systems capitalize on this natural organization by creating a generalized data management system that can be used in a wide variety of applications. 
     These generalized data management systems present the application programmer with an extension to her programming language that provides the data-serving functions. The application programmer calls these functions from inside the application code. This process is called embedding. 
     However, embedded generalized data management systems are inherently inefficient because, as these programs run, the specific data must be transformed into a generalized format for storage and transformed again, back to the natural format, on retrieval. Storing the data in the generalized, unnatural, format almost always takes much more storage space than storing them in their natural format. 
     In addition, generalized data management systems can only supply the application programmer with low-level data-serving functions, like &#34;save --  record&#34; and &#34;fetch --  record&#34;. The programmer must deal with the complex task of transforming the specific data to fit a generalized record format. 
     This task is accomplished by 1) writing the code to fill up and unfill the records, and 2) setting up schema, or maps of the record formats. Because these things must be done before the computer program is compiled, the resulting application is incapable of run-time flexibility in its schema definitions. Indeed, in conventional data management art, it is understood (Object Data Management, page 215, by R. G. G. Cattell, Addison-Wesley Publishing Company, 1991) that no automatic and satisfactory schema-evolution capability is possible because generalization to a variety of data types necessitates too many possible transformations of the schema and the data. 
     In the software industry, there are (at least) several programs developed in response to each computable problem. For example, several software companies make warehousing applications. Sometimes the several programs developed for one problem rely on the same-data management system. This means that the task of generalizing the specific data must be duplicated by each developer. So, while using a generalized data management system circumvents the need for some duplicate code, it also creates a need for other duplicate code. 
     Worse yet, the work of evolving the schema, if it is possible at all, must be done by personnel at the end-user site, with the help of utility programs supplied by the application programmer. 
     The exemplary embodiment of this invention is a data management system for maintaining vote data for groupware systems. Groupware is the name given to any computer hardware/software system that helps people cooperate in some way. The most common form of groupware, and the form to which the exemplary embodiment of this invention is most immediately applicable, is the computer conferencing system, sometimes called a bulletin-board. These conferencing systems invite an on-line community to post and read information in an organized way. 
     In groupware art, there are almost no methods for collecting votes from an on-line community. One make-shift vote-keeping method is outlined in the booklet, Customizing the Caucus(TM) User Interface (Camber-Roth, Troy, N.Y., November, 1990). 
     The Caucus conferencing software works with the Unix operating system. As with most conferencing systems, the text posted to the system by its users is organized as an outline is organized. The major categories under discussion are called conferences. Each conference has a title. A user starts a discussion by creating an &#34;item of discussion&#34;. To do so, the user is required to enter text and a title for the new item. The titles for these items are listed on an &#34;contents&#34; screen. 
     An example of a prior-art contents screen is shown in FIG. 1. The list of item titles is under the &#34;ITEM TITLE&#34; heading 20. 
     Users can continue the discussion on a particular item by adding a message to the item. The number of messages added to each item is listed under the &#34;RESPONSES&#34; column 22 on the contents screen. The item number is listed under the &#34;ITEM #&#34; column 24. 
     The instructions recommend that votes be collected at the item level by using the messages as ballots: to vote &#34;yes&#34;, the user adds a message with &#34;YES&#34; in the text body; to vote &#34;no&#34;, the user adds a message with &#34;NO&#34; in the text body. 
     The votes are tallied and reported by a utility program that is run by the end-users from inside the conferencing program. 
     The utility program searches the messages for the &#34;YES&#34; and &#34;NO&#34; strings, counts the number of each, and reports the results to the user. This method, although clever, cheap, and useful, is inflexible, slow, and cumbersome to use. It does not allow numeric or grouped votes (as explained below), does not provide opportunity for collating votes from different computer sites, and does not allow users to query the vote data, to change their votes, or to place restrictions on the vote values or the manner in which the votes are collected, tabulated, and/or reported. 
     Many of the deficiencies of the Caucus method can be remedied, according to current art, by embedding a generalized data management system into the groupware&#39;s source code. However, as described above, the embedding task is somewhat large and difficult and the resulting system would either require much more storage space and processing time, or require constant human intervention to keep the schema up-to-date. 
     Objects and Advantages 
     The present invention, a specialized data management method, provides a high-level language extension for the application programmer. In the case of the exemplary embodiment, the new language elements are natural requests like &#34;i --  vote&#34; or &#34;send --  statistics --  on --  item&#34; instead of the low-level record-centered requests of generalized systems. Therefore, most of the work of application development is accomplished by the specialized data management system and only the user-interface and the connections to it must be developed. 
     In the specialized data management method, schema-evolution is handled by the data management system and by the end-user. However, the end-user is not aware that he is causing schema-evolution; his mundane requests and commands trigger the complex data management tasks transparently. 
     Because data are stored in a natural format for the particular data type, they are stored optimally compactly. Also they are arranged so that data retrieval is as fast as possible; i.e., they are optimally clustered. In order to affect these optimal arrangements, a certain amount of data grooming, i.e. reordering and pruning, takes place. The grooming tasks are handled by the invention without conscious human intervention. Additionally, these tasks are undertaken, as much as possible, only when the computer system is otherwise idle. 
     Besides the advantages that the specialized data management system provides over a generalized data management system, there are advantages that the exemplary embodiment, the vote-keeper, provides over the Caucus vote-tallying method. The vote-keeper, like the Caucus method, allows any user to initiate a vote question. The vote-keeper also allows vote statistics to be presented on the contents screen, a huge user-interface advantage. While the Caucus method only allows one type of vote, the vote-keeper supports a myriad of vote types and options. 
     SUMMARY OF THE INVENTION 
     A method of specialized data management is provided in which the specialization allows distribution of the schema over the specialized objects so that schema-evolution is handled transparently by the end-user at run time, so that the data are stored with optimal compactness, so that data can be more efficiently clustered, so that self-grooming rules can be applied to the data, and so that the database management system can supply a higher level of interface to the application programmer. 
     The specialized data management method executes the data-grooming activities, as much as possible, when the computer&#39;s central processing unit is relatively idle. 
    
    
     DRAWING FIGURES 
     In the drawings, closely related figures have the same numeral but different alphabetic suffixes. 
     FIG. 1 An Example of a Prior-Art Contents Screen 
     FIG. 2.A Contents Screen with Yes/No Vote 
     FIG. 2.B Contents Screen with Numeric Vote 
     FIG. 2.C Contents Screen with Grouped Yes/No Vote 
     FIG. 2.D Contents Screen With Grouped Numeric Vote 
     FIG. 3 Data-Intensive Menu 
     FIG. 4.A (prior art) Two-Process Architecture 
     FIG. 4.B (prior art) Simultaneous Processes 
     FIG. 5 Overall Architecture Of the Server 
     FIG. 6.A MailBox Class Category 
     FIG. 6.B InterProcess Communication Channels 
     FIG. 7 Instruction Class Category 
     FIG. 8 DataBase Class Category 
     FIG. 9 Item Class Category 
     FIG. 10 Dense Packing of Vote Data 
     FIG. 11 The Execution of a Request 
     FIG. 12 The Emergence and Postponing of a Grooming Request 
     FIG. 13 Main Controlling Function 
    
    
     Reference Numerals in Drawings 
     In the drawings a class and an object of that class are identified by the same reference numeral but have a different letter appended to indicate whether the particular component of the diagram represents a class or an object. If the component represents a class, the numeral is appended with `c`; if the component represents an object, the numeral is appended with `o`. Class categories bearing the same name as a class are also identified with the same numeral as the class but with no appended letter. 
     
         ______________________________________                                    
       First                                                              
Refer- Appears                                                            
ence   in                                                                 
Numeral                                                                   
       FIG. #   Refers to                                                 
______________________________________                                    
20     1        ITEM TITAL column                                         
22     1        RESPONSES column                                          
24     1        ITEM number column                                        
26     2.A      ACC column-number of accessers                            
28     2.A      VTR column-number of voters                               
30     2.A      YES column-number of yes votes received                   
32     2.B      AVE column-average vote                                   
34     2.B      no vote item                                              
36     2.C      instruction for a group of items                          
38     2.C      YOU column-the user&#39;s vote                                
40     2.C      number of voters in a group of items                      
42     2.C      sum of the user&#39;s votes on a group                        
44     2.C      limit of the sum of a user&#39;s votes on a group             
46     2.D      enforced vote limits                                      
48     3        &#34;See&#34; your vote option                                    
50     3        &#34;Who voted&#34; option                                        
52     3        &#34;How voted&#34; option                                        
54     3        &#34;Remove your vote&#34; option                                 
56     4.A      data-server                                               
58     4.A      embedded programming language extension                   
60     4.A      application                                               
62     4.A      InterProcess Communication                                
64     4.B      end-user terminal                                         
65     4.B      central processing unit                                   
66     5        DataBase                                                  
67     4.B      information storage device                                
68     5        MailBox                                                   
70     5        Instruction                                               
72     6        InQ-request queue                                         
74     6        OutQ-return message queue                                 
76     6        QList                                                     
78     7        abstract instruction classes                              
80     8        ConfList                                                  
82     8        Conf                                                      
84     8        ItemList                                                  
86     8        VoterList                                                 
88     8        BallotBox                                                 
90     8        Ballot                                                    
91     7        Entering instruction                                      
92     8        Voter                                                     
93     7        KeepQ instruction                                         
94     8        Item                                                      
95     7        NeedsQ instruction                                        
96     9        ItemID                                                    
98     9        TalliedItem                                               
100    9        GroupedItem                                               
102    9        ItemGroup                                                 
104    9        GroupList                                                 
106    10       ballot header                                             
108    10       ballot vote data                                          
112    11       IVote                                                     
114    11       About Item                                                
116    11       HasQ                                                      
118    11       vote() message                                            
120    11       mark.sub.-- ballots() message                             
122    11       report.sub.-- stat() message                              
124    11       reply() message                                           
126    12       Request                                                   
128    13       MailBox::deliver()                                        
130    13       find request?                                             
132    13       inner loop                                                
134    13       &lt;DON&#39;T WAIT&gt; entry                                        
136    13       &lt;WAIT&gt; entry                                              
138    13       operating system busy?                                    
140    13       sleep()                                                   
142    13       ConfList::groom()                                         
144    13       perfectly groomed?                                        
146    13       outer loop                                                
______________________________________                                    
 
    
     DETAILED EXPLANATION OF AN EXEMPLARY EMBODIMENT OF THE INVENTION 
     An exemplary embodiment of the specialized data management system is a data management system specialized to vote data generated by a groupware system as described above. The system will be referred to as the vote-keeper. 
     The vote-keeper was developed on Interactive Unix V.3.2 but can be used on any Unix platform. With some fairly minor adjustments, it can be used on any multi-user computer system and embedded into any groupware application. 
     FIGS. 2 and 3 detail the possible results of using the vote-keeper in a conferencing system. These are explained in the section, The Vote-Keeper in Use. 
     The next section, Extension to A Programming Language, lists the vote-keeper&#39;s user-interface as seen by the application programmer. 
     FIG. 4 is a diagrammatical representation of the overall architecture of the vote-keeper&#39;s source code. FIGS. 5, 6.A, 7, 8, and 9 are diagrams of the architecture of smaller pieces of the source code. The other FIGS., 6.B, 10, 11, 12, and 13, each diagram some important detail of the system. 
     The Vote-Keeper In Use--FIGS. 2 and 3 
     When the vote-keeper is embedded into a conferencing system like the system explained in Description of Prior Art, above, the most obvious change will be in the appearance of the contents screen. 
     FIG. 2.A shows a contents screen with the vote-keeper embedded and with a simple YES/NO vote requested. As in a conference without the vote-keeper, there is a list of item titles 20 and a column that shows the number of messages that have been added to the item, marked RSPS 22. The vote-keeper provides support for the three new fields in FIG. 2.A: ACC 26, showing the number of users who have accessed the item; VTR 28, showing the number of users who have voted on the item; and YES 30, showing the number of users who have voted `YES` on the item. 
     FIG. 2.B shows a contents screen with a numeric vote, also supported by the vote-keeper. Here the YES column is replaced by an AVE column 32. The AVE column reports the average vote given to the item by the community. 
     Item 4 in the example of FIG. 2.B 34 serves as an instruction item and there is no vote taken on item 4 itself. The vote-keeper allows plain, unvoted items and supports the reporting of the number of users who have accessed the unvoted item 26. 
     The vote-keeper also supports the distributing of YES votes, by the end-users, over a set of items. FIG. 2.C is an example of such distributing where the vote question is &#34;VOTE YES ON 5 OF THE FOLLOWING 8&#34; 36. In FIG. 2.C, the YOU column 38 replaces the VTR column 28 of FIG. 2.A). Each of the items in a group has the same number of voters. That number is shown at the bottom of the group in the example 40. Also shown at the bottom of the group is the number of YESes this voter has used 42 and how many are available 44. 
     The vote-keeper supports, but is not limited to supporting, another vote configuration whereby numeric votes are distributed by the voter over a group of items. FIG. 2.D shows an example contents screen resulting from this configuration. In FIG. 2.D, as in FIG. 2.B, there is a plain item with no vote taken that provides instructions for the group of items 34. In the grouped numeric example of FIG. 2.D the vote question is &#34;DISTRIBUTE $100 OVER THE NEXT 9 ITEMS&#34; 46. The column headings for this example are: ACC 26 showing the number of users who have accessed the item; YOU 38 showing the vote that the current voter has given the item; and AVE 32 showing the average vote that the item has received. The number of voters 40 and the sum of the current user&#39;s votes on the group 42 and the total number of vote points that the user is allowed to distribute over the group 44 are shown at the bottom of the group. 
     The vote-keeper supports the-setting and enforcing of limits on the acceptable votes for each item 46. 
     The vote-keeper provides support for data intensive menu items similar to those shown shown in FIG. 3. The menu choices supported by the vote- keeper include but are not limited to: a &#34;See&#34; 48 command that allows each voter to see her own votes, enhancing the system&#39;s security; a &#34;Who voted&#34; 50 command whereby users can query the data on a item to find who has given this item a specific vote, i.e., &#34;Who has voted `yes` on this item?&#34; or &#34;Who has voted greater than 8 on this item?&#34;; a &#34;How voted&#34; 52 command whereby a user can know how another user voted on a specific item. The current embodiment of the vote-keeper also supports a user&#39;s capability to remove her vote from an item 54, to change his vote, and to remove her participation from the conference. 
     The current vote-keeper supports, but is not limited to supporting, three vote permission types: &#34;public&#34;, &#34;if-voted&#34;, and &#34;private&#34;. Votes on items can be designated &#34;public&#34;, whereby voters can see each other&#39;s votes, and all the menu options described above are available. Votes on items can be designated &#34;if-voted&#34;, whereby voters can see if other members of the on-line community have voted but they cannot see how the other members voted. And, of course, votes can be &#34;private&#34;, whereby only the statistics listed on the contents screen are available. 
     The vote-keeper also supports, but is not limited to supporting three vote states for each voted-on item: HIDDEN, whereby votes are accepted but statistics about the vote are not available; OPEN, whereby votes are accepted and the statistics are available; and CLOSED, whereby votes are not accepted and the statistics about the vote are available. 
     The vote-keeper can also be embedded so that several votes are taken on each item, for example: one vote to judge the group&#39;s acceptance of the idea expressed, and one vote to judge the expression of the idea. When the expression is being judged, the resulting score can be used to determine whether or not this item should be deleted from the conference. 
     This is a method of democratically pruning or censoring the material in the groupware application. 
     Although the embodiment presented here is a vote-keeper embedded into a conventional conferencing system, the vote-keeper can be embedded anywhere that a vote is useful. Additionally, instead of a vote-keeper, the method can be used to build a data management system for other types of specialized data. 
     Extension to A Programming Language 
     The vote-keeper&#39;s user-interface, like the user-interface for most data management systems, is an extension to a programming language. The user is the application programmer and the interface he sees is the list of new language elements. In the case of the vote-keeper, the new C routines are written in the C programming language. Most computer languages have provisions for calling C functions so most languages can be extended to include the vote-keeper by linking in the new C library and calling the C routines. 
     Here the C calls provided by the vote-keeper are listed along with their synopses which indicate exactly how to use the calls in the application program. 
     The new C and C++ language elements provided by the vote-keeper fall into three general categories: administrator functions, facilitator functions, and voter functions. Many of these functions return OKorNOT, an enumerated type. 
     Administrator Functions 
     Administrator functions are called when creating, adjourning, checking, and dropping conferences, and when statistics are sent or received from other computers. Dropping a voter from a conference and stopping the server are also considered administrative functions. 
     
         ______________________________________                                    
OKorNOT adjournevotefor(conf.sub.-- name)                                 
         char * conf.sub.-- name;                                         
Here, we take the conference out of memory for                            
continuing another time. It will be reconvened the                        
first time someone enters it with a call to                               
i.sub.-- am.sub.-- entering(), below.                                     
}                                                                         
OKorNOT check.sub.-- conf(conf.sub.-- name)                               
         char * conf.sub.-- name;                                         
{                                                                         
The named conference is checked. The ballots are re-                      
tallied and the item totals are checked. Discrepancies                    
are fixed, if possible, and reported in evote.log, the                    
log file for the vote-keeper.                                             
}                                                                         
OKorNOT collect.sub.-- net.sub.-- info(conf.sub.-- name, iid, from.sub.-- 
file)                                                                     
         char * conf.sub.-- name;                                         
         ItemID * iid;                                                    
         FILE * from.sub.-- file;                                         
{                                                                         
This function collects, from &#34;from.sub.-- file&#34; , a particular            
item&#39;s vote configuration information gathered from                       
another computer.                                                         
}                                                                         
OKorNOT collect.sub.-- net.sub.-- stats(conf.sub.-- name, iid,            
from.sub.-- file)                                                         
         char * conf.sub.-- name;                                         
         ItemID * iid;                                                    
         FILE * from.sub.-- file;,                                        
{                                                                         
This function collects new statistics gathered from                       
another computer about the item from &#34;from.sub.-- file&#34;.                  
}                                                                         
OKorNOT create.sub.-- evote.sub.-- for(conf.sub.-- name)                  
         char * conf.sub.-- name;                                         
{                                                                         
This function starts a new conference.                                    
}                                                                         
OKorNOT drop.sub.-- conf(conf.sub.-- name)                                
         char * conf.sub.-- name;                                         
{                                                                         
Drops the conf from the database, making backup files.                    
}                                                                         
OKorNOT drop.sub.-- voter(conf.sub.-- name, uid.sub.-- to.sub.-- drop)    
         char * conf.sub.-- name;                                         
         int uid.sub.-- to.sub.-- drop;                                   
{                                                                         
This function drops the named voter from the conf. The                    
voter&#39;s votes are taken out of the statistics for all                     
items in the conf.                                                        
}                                                                         
OKorNOT send.sub.-- net.sub.-- info(conf.sub.-- name, iid, to.sub.--      
file)                                                                     
         char * conf.sub.-- name;                                         
         ItemID * iid;                                                    
         FILE * to.sub.-- file;                                           
{                                                                         
 This function stores the vote configuration information                  
about the item in &#34;to.sub.-- file&#34;.                                       
}                                                                         
OKorNOT send.sub.-- net.sub.-- stats(conf.sub.-- name, iid, to.sub.--     
file)                                                                     
         char * conf.sub.-- name;                                         
         ItemID * iid;                                                    
         FILE * to.sub.-- file;                                           
{                                                                         
This function stores the statistics about the item in                     
&#34;to.sub.-- file&#34;.                                                         
}                                                                         
OKorNOT send.sub.-- quit()                                                
{                                                                         
Tells the server to save everything and quit.                             
}                                                                         
______________________________________                                    
 
    
     Facilitator Functions 
     Facilitator functions deal with setting up and managing the votes. 
     
         ______________________________________                                    
OKorNOT evote.sub.-- new.sub.-- item(iid, evote.sub.-- flag, max, min,    
priv.sub.-- type,                                                         
         group.sub.-- flag, more.sub.-- to.sub.-- come, sum.sub.-- limit  
         )                                                                
         ItemID *iid;                                                     
         char evote.sub.-- flag, group.sub.-- flag;                       
         unsigned short max, min;                                         
         PRIV.sub.-- TYPE priv.sub.-- type;                               
         short more.sub.-- to.sub.-- come, sum.sub.-- limit;              
This is called to create a new item, whether it is                        
tallied, plain, or grouped. When creating a plain or                      
tallied item, the unused arguments are ignored.                           
}                                                                         
OKorNOT close.sub.-- vote(status)                                         
         CSTATUS *status;                                                 
{                                                                         
This changes the status to show that the vote is closed.                  
The status pointer that is passed in should point to the                  
status variable kept in the item&#39;s data structure.                        
}                                                                         
OKorNOT drop.sub.-- item(iid)                                             
         ItemID* iid;                                                     
{                                                                         
Drops the item from the conf.                                             
}                                                                         
OKorNOT hide.sub.-- vote(status)                                          
         CSTATUS *status;                                                 
{                                                                         
Hides the vote tally on the item.                                         
}                                                                         
OKorNOT open.sub.-- vote(status)                                          
         CSTATUS *status;                                                 
{                                                                         
Reopens the vote on the item.                                             
}                                                                         
______________________________________                                    
 
    
     Voter Functions 
     Voter functions log the user&#39;s activity, accept the user&#39;s vote, and return various statistics. 
     
         ______________________________________                                    
char* get.sub.-- stats(iid)                                               
         ItemID* iid;                                                     
Returns a string containing the statistics to print for                   
the item requested.                                                       
}                                                                         
short how.sub.-- voted(iid, priv.sub.-- type, pwname)                     
         ItemID *iid;                                                     
         PRIV.sub.-- TYPE priv.sub.-- type;                               
         char *pwname;                                                    
{                                                                         
Returns the vote for the given pwname. If pwname ==                       
NULL, the caller&#39;s vote is returned. If not, the vote                     
is returned only if the priv.sub.-- type allows it.                       
}                                                                         
OKorNOT i.sub.-- am.sub.-- entering(conf.sub.-- name, no.sub.-- notes.sub.
-- in)                                                                    
         char *conf.sub.-- name;                                          
         short no.sub.-- notes.sub.-- in;                                 
{                                                                         
Alerts the server that there is activity here. The                        
server readies statistics for sending back. no.sub.-- notes.sub.-- in     
is the number of items currently in the conference.                       
}                                                                         
void i.sub.-- am.sub.-- leaving()                                         
{                                                                         
Informs the server that this voter is leaving so that                     
the server can make a little space by storing this                        
voter&#39; s ballot.                                                          
}                                                                         
OKorNOT i.sub.-- just.sub.-- read(iid)                                    
         ItemID *iid;                                                     
{                                                                         
Informs the server that the user has read the item. No                    
acknowledgement given.                                                    
}                                                                         
OKorNOT i.sub.-- vote(iid, status, max, min, group.sub.-- flag, vote)     
         ItemID* iid;                                                     
         CSTATUS status;                                                  
         unsigned short max, min;                                         
         char group.sub.-- flag;                                          
         short vote;                                                      
{                                                                         
Accepts, checks and acknowledges vote to stdout.                          
}                                                                         
OKorNOT who.sub.-- voted(iid, priv.sub.-- type, instruction)              
         ItemID * iid;                                                    
         PRIV.sub.-- TYPE priv.sub.-- type;                               
         char *instruction;                                               
{                                                                         
Asks a question like &#34;Who voted less than 3&#34; on the                       
item. &#34;instruction&#34; is a character string that contains                   
the meat of the question, &#34;&lt;3&#34;, in this case. The                         
server passes back a list of user-ids and this function                   
translates them to login names and prints them to                         
stdout.                                                                   
}                                                                         
______________________________________                                    
 
    
     Two-Process Architecture--FIGS. 4.A and 4.B 
     The vote-keeper uses a two-process architecture as is common in database management art and as is described in Object Data Management, supra. FIG. 4.A is a diagrammatic representation of the architecture for the vote-keeper. The data-serving process 56 is a daemon as described on page 301 of Unix--The Complete Reference by Stephen Coffin (Osborne McGraw-Hill, 1988). It runs as a background process without user intervention. The vote-keeper provides an extension to the C or C++ programming language in the form of a library of C routines 58 that are embedded into the application&#39;s source code 60, the conferencing system in the present example. The C routines communicate with the server through the InterProcess Communication facilities 62 provided by the operation system. The Unix InterProcess Communication facilities used in the exemplary embodiment are the message system calls, described in Advanced Unix Programming by Marc J. Rochkind, page 182 (Prentice-Hall, Inc., 1985). 
     Although the source code for the device uses a two-process architecture, in reality, when the vote-keeper is in use, many processes can be running simultaneously, as shown diagrammatically in FIG. 4.B. Each end-user runs and controls a separate process, executing a copy of the application program 60. 
     In the example, each of the processes running the application program 60 communicates with a single data-server process 56 running in the computer&#39;s background through InterProcess Communication 62. All of the application processes 60 as well as the data-server process 56 are executing under the control of the multi-process operating system 63 on the central processing unit 65. The data are stored on the information storage device 67. 
     On busy systems, however, this architecture is easily extended to run more than one data-server by specifying that the data for certain conferences be maintained by one server process while the data for other conferences be maintained by another server process. 
     Also, the architecture can be modified so that the application programs 60 run on separate computers as long as communication with the data-server process is maintained. In this case, the operating system can be a single process operating system. 
     InterProcess Communication Messages 
     The C routines listed above, when necessary, translate the request into an InterProcess Communication message and send the request to the vote-keeper&#39;s server program. The types of messages that the server program understands includes but is not limited to: 
     ADJOURN --  CONF--stores all data regarding the designated conference. 
     CHECK --  CONF--retallies all the votes and checks the stored results. 
     COLLECT --  NET --  INFO--includes the items and vote configurations gathered from other computers. 
     COLLECT --  NET --  STATS--includes statistics gathered from other computers. 
     CREATE --  CONF--adds a new conference to the database. 
     CREATE --  GROUPED --  ITEM--adds a new grouped item to the database. 
     CREATE --  PLAIN --  ITEM--adds a new unvoted item to the database. 
     CREATE --  TALLIED --  ITEM--adds a new voted item to the database. 
     DROP --  CONF--removes a designated conference from the database. 
     DROP --  ITEM--removes a designated item from the database. 
     DROP --  VOTER--removes the data relating to a specified voter from the portion of the database relating to the specified conference. 
     ENTERING--copies a specified voter&#39;s data regarding a specified conference from disk into memory. 
     HOW --  VOTED--answers a query about how a particular voter voted. 
     I --  READ--registers a specified user as one who has accessed a specified item. 
     I --  VOTE--registers a specified user as one who has voted a specified amount on a designated item. 
     LEAVING--stores a specified voter&#39;s data regarding a specified conference on disk and frees up computer memory. 
     QUIT--stores all data on disk and stops the server. 
     SEND --  NET --  INFO--returns the vote configuration about the specified item for sending to other computers. 
     SEND --  NET --  STATS--returns statistics about the specified item for sending to other computers. 
     SEND --  STATS--returns a string of statistics for printing on the contents screen. 
     SET --  TYPE--sets the vote status or the vote permission type for a specified item. 
     WHO --  VOTED--answers a query about which voters voted in a particular manner on a specified item. 
     Overview of the Vote Server Program--FIG. 5 
     The vote-keeper&#39;s server program is object-oriented: the diagram notation and terminology used here is described in Object-Oriented Modeling and Design by James Rumbaugh et. al. (Prentice-Hall, Inc., 1991) with the addition that class categories, as defined in Object Oriented Design with Applications, by Grady Booch (The Benjamin/Cummings Publishing Company, Inc., 1991) are represented by double-lined rectangles. 
     The vote-keeper&#39;s server program consists of three class categories as shown diagrammatically in FIG. 5. The DataBase class category 66 actually manages the data. The MailBox class category 68 is responsible for incoming and outgoing InterProcess Communication 62 to the application processes 60. 
     When a MailBox object receives a request from an application process, it creates an appropriate Instruction object in the Instruction class category 70. The Instruction object coordinates the execution of the requested task by issuing requests to the appropriate objects in the DataBase class category and sending any required responses back to the application process through the MailBox. Each of these three major class categories is discussed in detail below. 
     The MailBox Class Category--FIGS. 6.A and 6.B 
     The MailBox class category is shown diagrammatically in FIGS. 6.A and 6.B. In each vote-server, there is exactly one MailBox object 68o that is responsible for maintaining communication with the library of C routines that is embedded into the application 60, and for creating and destroying the Instruction objects in the Instruction class category 70, FIG. 6.A. 
     FIG. 6.B is a diagrammatical representation of the InterProcess Communication message queue configuration for the vote-keeper, maintained by the MailBox object and the library of C Routines that is embedded into the groupware application. 
     All incoming InterProcess Communication 62 arrives on the same request message queue controlled by the InQ object 72o. For the InterProcess Communication facility supplied by Unix, each message queue is identified by a unique long integer supplied by the programmer. In the vote-keeper, the request queue&#39;s identifier is a large number, larger than can be stored in a short integer. Smaller numbers are reserved for outgoing return message queues. 
     Each application process 60 that communicates with the vote-server gets its own queue for return messages. This return queue is maintained, on the application side, by the embedded library of routines and, on the server side, by an OutQ object 74o, FIG. 6.B of the OutQ class 74c, FIG. 6.A. The return queue is established either by the vote-server, or by the calling process, whichever side of the communication needs the queue first. 
     The return queue bears an identifier equal to the calling process&#39; id. This id, a short integer, is guaranteed by the operating system to be unique at any time. Using the process id as the message queue id in turn guarantees that each calling process always receives the return messages intended for it, even when there are many vote-server processes running on the same central processing unit. 
     In a very busy groupware system, it may be necessary to use two or more vote-servers. This is done by using a different large identifier for each server&#39;s request queue. The work is divided between the servers by sending all activity that pertains to one conference to one server and all the activity that pertains to another conference to another server. 
     The simple scheme of assigning the message queue id to be equal to the process id may not be possible in all operating systems. Indeed it is only possible if the range of possible queue ids has a subset that is disjoint from the range of possible process ids, which is the case in Unix. The essential points that need to be replicated in any scheme are 1) reserving one queue id for each server&#39;s request queue, and 2) establishing a one-to-one correspondence between the process id of the user and the user&#39;s return message queue id. In the rare event (never in Unix) that the return queue id for the application process turns out to be the same number as the reserved queue id of a server process, the application process can restart itself to obtain a new process id. 
     Another scheme for maintaining the return message queues is to identify the return queue by the calling user&#39;s user id. This scheme would be appropriate in an operating system where each user is only allowed one active computer process. This is not the case in Unix. 
     The list of active return queues, or OutQ objects, is maintained by the QList object 76o, FIG. 6.A which is contained in the MailBox object. This list is a singly-linked list with a reverse sort on creation time. This means that, when the list is searched, the search starts with the newest queue. This is done so that if any queues are dropped from the application side without notifying the vote-server, they will fall to the bottom of the search list. This happens when the application crashes, or, more usually, when a user hangs up the modem without following the proper exit procedures. 
     The message queue is checked periodically for inactive queues. 
     If inactive queues are found, they are dropped. This is done when the server is otherwise idle. The mechanism for timing the execution of this and all other &#34;grooming&#34; tasks is described in Postponing Grooming Tasks and Precipitating Grooming Tasks below. 
     Instruction Class Category--FIG. 7 
     FIG. 7 is a diagrammatical representation of many of the classes in the Instruction Class Category. It is an inheritance hierarchy used in object-oriented software designs to reduce duplicate code. At the top of the hierarchy is the abstract Instruction class 70c. All the classes inside the heavy circle 78 are abstract classes. Each instantiable class corresponds to one specific type of message that might be received by the vote-server through its incoming InterProcess Communication request queue. 
     When the MailBox object 68o receives a request on its request message queue, it creates the corresponding Instruction object. During the construction of the Instruction object, the actual request is passed along to the appropriate objects in the DataBase class category 66, and any response is sent back through the MailBox object. After an Instruction object is completely constructed, its job is finished; so the object is destroyed. This is explained in greater detail in From Message to Execution, below. 
     DataBase Class Category--FIG. 8 
     FIG. 8 is a diagrammatical representation of the main classes in the DataBase class category. In each vote-keeper there is exactly one ConfList object 80o that maintains a list of all the active conferences in the vote-keeper, each conference becoming, in the software, an object of the Conf class 82c. 
     The Quick List-Attacher 
     Although maintaining ordered lists is well-known in the art, the ConfList class 80, an ordered list, does have one new device. As is common in the art, the list of Conf objects 82 is always searched before a new Conf object is made, to be sure that the new conference isn&#39;t already listed. When the search shows that the conference is, in fact, new to the database, a new Conf object is made and attached to the list in the proper order, which would ordinarily require a second search through the list. This second search is avoided in the vote-keeper by the following method. 
     When the list of Conf objects is searched and the target conference is not found, the search routine returns a pointer to the Conf object that should precede the new Conf object when it is added to the list. Then, rather than instructing the ConfList object to simply attach the new Conf object, the vote-keeper instructs the ConfList object to attach the new Conf object and specifies where to attach it, eliminating the second search. 
     The other list classes, the ItemList 84c and the VoterList 86c discussed below, use the same search/attach method and all three (and possibly more) list classes can be parameterized, if parameterization is supported in the programming language. 
     Each object of the Conf class represents one conference or category heading in the groupware application. In the vote-keeper, each Conf object contains one object of the ItemList class 84c, responsible for maintaining a list of the items in the conference; one object of the VoterList class 86c, responsible for maintaining a list of the voters currently on-line and participating in the particular conference; and one object of the BallotBox class 88c. 
     As is common in the art, two data files are kept for each conference, one to store the schema and one to store the actual data, or votes in the case of the vote-keeper. Schema storage is discussed in Schema Storage below. 
     Ballot Storage and Retrieval--FIGS. 7 and 8 
     The BallotBox object is responsible for storing and retrieving the Voters&#39; ballots, and it uses a very simple scheme, made possible by the specialization of the server. 
     All the ballots in one conference are maintained by the same BallotBox object and are stored in the same data file. All the ballots for the conference have the same size, but the size of the ballots varies as the conference progresses. 
     Ballots are stored in blocks, in order of user id, except for the last block in the file. The last block of the data file for the conference contains the newest members of that conference&#39;s community, also in user id order. When the block becomes crowded according to the BallotBox&#39;s self-grooming rules, the BallotBox requests a reordering of the ballots. 
     This request is sent to the server&#39;s own request queue as described in Postponing Grooming Tasks below. When the MailBox receives the reorder request, it sends it back to the BallotBox object. The BallotBox then reorders the whole data file so that all the ballots are in user id order and the last block is empty. The execution of this grooming task, and others, is timed so that it happens when the system is otherwise idle. See Data Grooming below. 
     The vote data are indexed by user id. The last user id in each block is kept in a list in memory for quick access. This index is adjusted when the data file is reordered. 
     The ballots, when they are copied from disk to memory, become instances of the Ballot class 90c, FIG. 8. On-line participants are represented in the software as objects of the Voter class 92c. Each Voter object contains and controls its Ballot object. 
     Each Voter object has a corresponding object of the OutQ class 74c which is part of the MailBox class category 68, described above. When a user first enters a conference, the groupware application sends an ENTERING request to the vote-server. The MailBox (refer back to FIG. 7, 68o) receives the ENTERING request and creates an Entering instruction FIG. 7, 91c. As the Entering instruction is being created, the KeepQ FIG. 7, 93c, NeedsQ FIG. 7, label 95c, and Instruction FIG. 7, 70c constructor functions are executed because they are parent classes to the Entering class. The NeedsQ constructor creates an OutQ object whose message queue id equals the id of the user&#39;s process (discussed above). Subsequent instructions from the same user will be sent from the same process. This provides a key for finding the appropriate OutQ object for the subsequent requests. 
     Each OutQ object keeps a pointer to its corresponding Voter object so that when subsequent requests from the same process are received, the process&#39; user&#39;s Voter object is immediately found once the correct OutQ is identified. 
     Item Class Category--FIGS. 8 and 9 
     The group of classes associated with the Item class category 94, FIG. 8 is shown diagrammatically in FIG. 9. The main class of the Item class category, the Item class 94c contains an ItemID class 96c, which can be easily modified to suit the particular groupware application. The vote-keeper&#39;s current version of the ItemID class allows each item three id numbers: 2 long integers and one short, in anticipation of networking votes and statistics to remote sites that also run the vote-server. This follows the scheme used in Notesfile, a public domain networked conferencing system written by Ray Essick. The short integer holds the local identification; the items are listed at the local site in this order. The two long integers hold universal id&#39;s. The first universal id uniquely identifies the originating computer. The other id is generated by the originating computer and is unique among the items generated on the originating computer. 
     Objects of the ItemList class 84c keep two lists of the Items in the conference. The primary list links the Items in the order of their universal id&#39;s as explained above. The secondary list is a simple array where the elements are pointers to Item objects, kept in the order of the local id. 
     The vote-keeper anticipates three different types of vote data generated by groupware applications: 1) data for items that are not voted on, 2) data for items that are voted on, and 3) data for items that are voted on and grouped with other items. The third type of data is generated when several voted-on items are grouped together with a question like, &#34;Vote for 5 of the following 10&#34;, or &#34;Distribute 100 points over the next 20 items.&#34; Because of the architecture of the vote-keeper, additional vote types are easily added. 
     The three types of items are represented in the software by an inheritance hierarchy. The Item class 94c, FIG. 9 is at the top of the hierarchy. All items in the groupware application become objects of the Item class. If the item is not voted on (data type 1 above), it is only an Item object in the software and has no properties of the classes of objects further down the hierarchy. If the item is voted on (data types 2 and 3), in the vote-keeper, it is also a TalliedItem 98c. Grouped items in the application become objects of the GroupedItem class 100c in the software. Every time a group of items is created, one object of the ItemGroup class 102c is also created for controlling the group. All the ItemGroup objects in a particular conference are maintained in a list by the conference&#39;s GroupList 104c. The GroupList object is contained in the conference&#39;s ItemList 84c. 
     Dense Packing of Data/Distributed Dynamic Schema--FIGS. 8 and 10 
     FIG. 8 also shows a diagrammatical representation of the way objects in the DataBase class category work together. When a user enters the conference, a new Voter object is created and attached to the list of Voters maintained by the VoterList object. As the Voter object is being created, it asks the BallotBox object to retrieve the Voter&#39;s ballot from persistent storage. If the Voter is entering the conference for the first time, the BallotBox object makes a new, empty Ballot for the Voter. Ballot objects, unlike all the objects previously mentioned, have only data, no intelligence. 
     At the core of the vote-keeper is the method for dense packing of the vote data into the Ballot objects, herein after called ballots, made possible by the distribution of the data&#39;s schema over the Item objects. 
     FIG. 10 shows a diagrammatic representation the relationship between the items&#39; vote characteristics and the way the vote data are packed into ballots. Each ballot has two main parts: the header 106; and the vote data 108. The header contains the user id of the voter, perhaps the last access time, and any other information about the user that the groupware application needs. The vote data portion of the ballot contains the data pertaining to the particular user&#39;s activity (accesses and votes) in the conference. 
     For the first vote-data type (items without a vote question), only one bit of storage is required to indicate whether or not the user has accessed the item. One byte of storage is allocated for each item that is voted on (vote types 2 and 3). An additional 2 bytes of storage is allocated for storing the sum of the user&#39;s votes for each group of grouped items; although this sum can be calculated each time it is needed and not stored if space is more important to conserve than computer time. 
     Every time a new item is introduced into the conference, the ItemList object 84o, FIG. 10 creates a new Item object 94o. The ItemList object assigns a particular byte in the ballots to the new Item object; and it assigns a particular bit in the designated byte to the new Item object, if the corresponding item in the groupware application is not voted on. 
     In the example depicted in FIG. 10, items 1 and 3 are not voted on in the application. They are each assigned one bit of storage in the first byte of vote data in each ballot. The next 6 unvoted-on items that are created in the groupware application will also keep their vote data in first byte, but in the subsequent bits of the first byte. When the 9th unvoted-on item is created, its datum is stored in the first bit of the next empty byte in the ballots. In this manner, each unvoted item gets one bit for storing its datum for the voter. 
     Item 2 in FIG. 10 is the first voted-on item in the example. Data for item 2 is kept in byte 2 of the vote records. Similarly, data for items 4, 5, and 6, are stored in bytes 3, 4, and 5. In the example, items 4, 5, and 6 are grouped together. Bytes 6 and 7 are allocated for storage of the sum of the user&#39;s votes on items 4, 5, and 6 42. 
     (If the vote-keeper relied on a conventional, generalized data management system, storing these data would require from 5 to 40 times more storage space. Because, in a generalized system, the schema must be fixed, each record would necessarily contain three fixed fields: the user id (2 bytes), an item identifier (at least 2 bytes), and the vote datum (1 byte). This means that 5 bytes or 40 bits of storage are necessary for each item/voter combination instead of the 1 byte, or more usually, 1 bit necessary in the specialized method.) 
     To update or access the vote stored for a particular item, the Voter object passes the memory address where its ballot stored to the appropriate Item object and asks it to mark or report the ballot. This is an easy, quick task for the Item object since it knows exactly where in the ballot its vote datum is kept. Therefore, each Item object keeps its part of the vote data schema. 
     Schema Storage 
     The ItemList object orchestrates the storage and retrieval of the schema. Storage is accomplished by cycling through the Item objects, in local id order, and asking each Item to store its information. It first stores a character to indicate the type of Item object, i.e., if it is a plain, Item, a TalliedItem, or a GroupedItem. It then stores its id and a record of its storage spot (i.e., it&#39;s part of the distributed schema) in the ballots. It also stores its current statistics although these can be recalculated from the ballots. If the item is a GroupedItem, and if it is the first item in its group, it asks its ItemGroup object to store itself. 
     On retrieval, the ItemList object peeks at the next byte in the file to discern the type of item that is next: plain Item, TalliedItem, or GroupedItem. It then creates that type of Item, and the constructor for the Item reads its own information from the file. If the Item is the first GroupedItem in a group, that first GroupedItem creates an ItemGroup object and the constructor for the ItemGroup reads its information from the file. 
     Although the statistics for the Items will change rapidly as users vote, these changes are only saved to disk when the server process is brought down. This is because the statistics are readily recalculated from the vote data (which is always kept up to date on disk) in the event of a system crash. 
     Schema-evolution only happens when new items are added to the conference or when old items are dropped or when the data are groomed. The schema on disk are updated whenever these operations occur. 
     From Message To Execution--FIG. 11 
     FIG. 11 shows diagrammatically how an incoming request message becomes an executed command and how a return reply is sent. The MailBox object 68o recognizes the type of the request and creates a new corresponding object in the Instruction hierarchy, an IVote object 112o in our example. Because an IVote object is also an AboutItem object 114o and a HasQ object 116o, the constructor functions for these objects are called before the body of the IVote constructor function is executed. The HasQ constructor finds the appropriate OutQ 74o for the return reply and, because each OutQ knows the address of its corresponding Voter object, the HasQ constructor also provides the appropriate Voter object 92o which contains the appropriate Ballot object 90o. The AboutItem constructor finds the appropriate Item object 94o so all the objects that participate in the requested voting transaction are available to the IVote constructor function. 
     The IVote constructor orchestrates the transaction by passing a vote() message 118 to the Voter object which responds by (1) asking the Item object to mark the ballot 120, and (2) asking the Item object to report the statistics on the item 122. The mark --  ballot() function returns the old vote stored for the voter/item combination so that it is available for sending back to the application. The IVote object then asks the MailBox to send a reply 124 through the OutQ to the voter&#39;s application process. In this way, all the work associated with executing the request is completed as the corresponding Instruction object is constructed. The MailBox immediately deletes the Instruction object, or IVote object in the case of our example, and the vote-server is ready for the next request. Other request types are handled similarly. 
     Data Grooming--FIG. 12 and 6.B 
     Occasionally, as described in Ballot Storage and Retrieval above, the ballots need to be reordered. Also, when items are dropped from the conference, and when space is needed in the ballots, the ballots are collapsed to exclude each corresponding dropped Item object&#39;s storage byte(s) or bit. In this case, the dropped items&#39; Item objects are deleted from the conference&#39;s ItemList and each remaining Item updates its knowledge of its storage spot to reflect the new arrangement in the ballots. In this way, both the vote data and the schema are updated as the conference progresses, resulting in distributed, dynamic schema. 
     The vote-keeper recognizes these and possibly other critical points in the accumulation of the data when, in order to maintain, deliver, and update the data efficiently, the data must undergo some transformation or &#34;grooming&#34;. So that data delivery to the groupware application is not unnecessarily interrupted, the vote-keeper attempts to undertake all grooming tasks when the computer system, or at least the vote-keeper, is otherwise idle. This is accomplished by using a two-part method: (1) a postponing scheme whereby low-priority grooming needs are postponed until the server is otherwise idle, and (2) a precipitation scheme whereby the data are groomed before a real need arises and during times when the computer system is relatively idle. 
     Postponing Grooming Tasks--FIG. 12 
     FIG. 12 (expanded from FIG. 6.B.) shows diagrammatically the emergence of a task that is suitable for delaying and the method of delaying the grooming task. This method can be used to postpone any suitable task, including but not limited to the grooming tasks described in this document. Before an ItemList object 84o creates a new Item object, it calculates if there is space in the ballots for the new data that will be generated by the new item. If the ItemList detects an emerging need for a larger ballot (determined according to its grooming rules), it asks the MailBox 68o to send a low-priority request 126 to its own InQ 72o through the InterProcess Communication channel 62. This is the same InterProcess Communication channel (see FIG. 6.B) used by the application 60 to make its requests. The prioritization of requests is supplied by Unix&#39;s InterProcess Communication facility. 
     If the need for grooming becomes critical, a high-priority request is sent along the same channel. If the need becomes immediate, the data serving functions are suspended while the data are immediately groomed. 
     Precipitating Grooming Tasks--FIG. 13 
     The data are also methodically groomed when the operating system is idle. This part of the scheme is controlled by the main controlling function for the server. 
     The main controlling function for the server is shown diagrammatically in FIG. 13. The controlling function contains an indefinite loop that, over and over, asks the MailBox object to attempt to &#34;deliver&#34; a message 128. If the MailBox finds a request 130 on the request message queue, it creates the appropriate Instruction object as described in From Message to Execution above, and in doing so completes the execution of the request. When control returns to the main function, the inner loop segment 132 is traversed and the MailBox once again attempts to deliver a message. 
     The inner loop enters the MailBox::deliver() function through the &lt;DON&#39;T WAIT&gt; entry 134 causing the MailBox::deliver() function to return to the main function immediately, even if there are no messages on the input queue. The &lt;DON&#39;T WAIT&gt; entry is in contrast to the &lt;WAIT&gt; entry 136 which is used when the data are perfectly groomed so the MailBox::deliver() function will wait until there is an incoming request. After a request is found and executed, control returns to the inner &lt;DON&#39;T WAIT&gt; loop. 
     If no incoming requests are found by the MailBox, not only are there no users waiting for a response, but also the data have no grooming needs that are urgent enough to trigger the grooming rules in the DataBase objects, described above. At this point, the operating system is queried for its activity level 138. If the system is busy, the server sleeps 140 a short while and once again traverses the inner loop. 
     However, if activity on the computer&#39;s central processing unit is sufficiently low, the ConfList object is requested 142 to find some even less immediate grooming task to do. When the ConfList judges 144 the state of the grooming to be perfect, control follows the outer &lt;WAIT&gt; loop 146 so that the server is quiet until a request is received. If grooming is not yet perfect, control once again joins in the inner &lt;NO WAIT&gt; loop so that, if there is not a request on the incoming message queue, another grooming task can be undertaken. 
     The method of postponing the grooming requests generated while the server is busy, and the method of generating and executing less urgent grooming tasks when the operating system is not busy, together keep the data so well-groomed that usually, a specific ballot is found in one disk read and only occasionally, for new participants to a conference, in two disk reads. Only if the central processing unit is heavily overloaded at all times will it be necessary to groom the data while the system is busy. 
     Conclusion 
     Thus the reader will see that the method of specializing a data management system herein described provides a system that is much more efficient than generalized data management systems in that: 
     1. The method minimizes the complexity and size of the application developer&#39;s task. 
     2. Processing time is minimized since the data are stored in their original, natural format. 
     3. The storage space necessary for maintaining the data is minimized since data packing can be as dense as possible. 
     4. The maintenance of data can be automated further than has been possible with generalized data maintenance systems. 
     In addition, the exemplary embodiment of the method, the vote-keeper, provides new ways to make democratic decisions. 
     While a particular embodiment of the invention is described above, it should be understood that changes can be made without departing from the spirit or scope of the invention. For example, a data management system can be specialized to keep test data, and other types of data. Indeed any application that uses a generalized database server would run more efficiently if the data were served by a specialized server. 
     Moreover, many of the inventive concepts described above can be rearranged such that the same functions are accomplished without departing from the essence of the inventive method. Therefore, this invention is not to be limited to the specific embodiment discussed and illustrated herein, but rather by the following claims and their legal equivalents.