Anubis / Anubis

   
   
                                    The Anubis Project. 
   
                     A Simple Data Base Management System (version 2).
   
                           Copyright (c) Alain Proute' 2004-2005. 
   
   
   Author: Alain Proute'
   
   Last revision: December 2005. 
   
   
   This is version  2 of our data  base management system. The differences  with version 1
   ('tools/sdbms1.anubis', formerly 'tools/sdbms.anubis', now obsolete) are as follows:
   
     - The  notion of  'row  identifier' has  been  removed.  Actually,  it  was not  very
   useful. If you want to have row identifiers, you have to invent a method of identifying
   the rows  of your  tables.  This  method may be  different for  each table.   Also, row
   identifiers  created  many  problems  of   performances,  and  problems  with  the  new
   implementation of tables.
   
     - The notion of  'version number' for rows  has been removed. If you  want to compare
   the current  state of a row  with a previous state,  just use a comparison  of the rows
   themselves instead of a comparison of version numbers.

     - As a  consequence of  the above, the  types 'DBRowId($Row)' and  'DBRow($Row)' have
   disappeared. This provides an important simplification of this system. 
   
     - The tables  are now split into 'chunks',  which are saved into  separate files. So,
   this version 2  of our data base management  system is able to handle big  or even very
   big tables, which was  not the case of version 1. This  splitting is a good replacement
   method for families of tables (of the same type).
   
     - Indexing methods have  been introduced. 'Primary indexing' and  an arbitrary number
   of 'secondary  indexings' are now  possible in  order to speed  up the various  ways of
   searching.
   
     - The  prefix 'DB'  for public  types has  been changed  into 'DB2',  so as  to allow
   programs using  'sdbms1.anubis' and 'sdbms2.anubis'  together.  This may be  useful for
   making programs for converting tables from version 1 to version 2.
   

   ----------------------------------- Contents ------------------------------------------

   *** (1) Motivations.
   
   *** (2) Data base and table structure. 
      *** (2.1) Data base roots. 
      *** (2.2) Errors and informations. 
      *** (2.3) Tables. 
      *** (2.4) Indexing. 
      *** (2.5) Initializing a table. 
      *** (2.6) Initializing an index.
      *** (2.7) Data bases. 
      *** (2.8) Handling changes in table formats. 
      *** (2.9) Handling a change of the primary index. 
   
   *** (3) Using the data base. 
      *** (3.1) Adding rows to a table. 
      *** (3.2) Row selection methods. 
      *** (3.3) Getting rows from a table. 
      *** (3.4) Updating rows in a table. 
      *** (3.5) Deleting rows from a table. 
         
   ---------------------------------------------------------------------------------------
      
   
   
   *** (1) Motivations.
   
   Relational data base management systems provide two kinds of commands:
   
     - utilization  commands,  like adding,  updating  or deleting  rows  in  a table,  or
       querying using the SQL command 'SELECT'.
   
     - restructuring commands, like adding columns  in a table, deleting columns, creating
       an index, etc...
   
   Normally, if a data base is restructured, programs using that database must themself be
   restructured, while  the transformation of the  data base by  utilization commands does
   not require any modification of the programs which are using the data base.
   
   Our aim is to provide a data base  mecanism, which is as much as possible in the spirit
   of Anubis. Our first demand is that cells  in a table should be able to contain data of
   any  (serializable) Anubis type  (one type  per column  of the  table of  course). More
   precisely, if T is a type, we want to  consider tables whose rows are data of type T. A
   consequence of this  is that adding a column  to a table requires a  modification of an
   Anubis type,  hence a  modification of  the program using  the data  base. But  this is
   precisely in the spirit of Anubis, because this will force a corresponding modification
   of the program, so ensuring more safety.

   This  data base management  program is  highly experimental  (actually, version  1 gave
   complete  satisfaction,  and  was  only  limited  in the  size  of  tables,  and  speed
   performances). Indeed,  the obligation  of deciding everything  about types of  data at
   compile time, introduces a rigidity which  renders the mimicking of the usual data base
   manipulations   quite  difficult  (at   least  as   far  as   the  SELECT   command  is
   concerned). Nevertheless,  it's an  interesting adventure because  it puts de  facto at
   different levels  aspects of data base  management which are otherwise  consider of the
   same kind.
   

   
   
   *** (2) Data base and table structure. 
   
   
      *** (2.1) Data base roots. 
   
   For creating a data base, you need a 'data base root'. This is of the following type:
   
public type DB2Root:...        (an opaque type)
public type DB2Error:...       (see below)   
public type DB2Info:...        (see below)   
   
   In order to create a data base root, use the following tool: 
   
public define DB2Root
   make_root
     (
       String           directory,   // where the files will be located
       Int32            kilo_bytes,  // maximal number of kilo bytes in memory
       Int32            delay,       // maximal synchronisation delay between memory and files
       Var(Bool)        shutdown_v,  // shutdown flag
       DB2Error -> One  warn,        // warning function for administrator
       DB2Info -> One   inform       // information function for administrator
     ). 
   
   Create as many data base roots as  you have data bases in your project. Choose distinct
   directories for all data base roots.
   
   'kilo_bytes' determines  the maximal number  of kilobytes the  data base may  occupy in
   memory  (RAM). When the  memory occupied  by the  data base  becomes greater  than this
   value, those chunks and tables which have been used the less recently are unloaded from
   memory.
   
   'delay' is the maximal  number of seconds which may elapse between  a modification of a
   table in the memory and the synchronisation with the data on the disk. 
   
   The  dynamic  variable  'shutdown_v' is  the  'shutdown  flag'.   When the  tables  are
   initialized this  variable receives the  value 'false'.  As  soon as you put  the value
   'true' in this variable,  all the table which have been initialized  with this root are
   shutdown, which means that  no more utilization command may work, and  that the data on
   the disk are  synchronised with the content of the memory.   You should probably create
   only one such variable for all the data  bases of your program, i.e. even if you create
   several  data base  roots,  you should  provide the  same  shutdown flag  to all  these
   roots. Nevertheless,  if you want  to shutdown your  data bases at distinct  times, use
   several shutdown flags.
   
   The function 'warn' is  called when an error arrives in one of  the tables of this data
   base.   This function  may  print the  error  on the  console  or send  a  mail to  the
   administrator or do anything else.  The  function 'inform' is similar to 'warn', except
   that it concerns information messages, instead of error messages.
   
   
   
   
      *** (2.2) Errors and informations. 
   
   Errors may occur during the normal use of the data base. 
   
public type DB2Error:
   file_not_found                    (String path),
   file_reading_problem              (String path), 
   file_type_problem                 (String path),
   cannot_open_file                  (String path), 
   cannot_write_file                 (String path),
   cannot_find_index                 (String directory, 
                                      String table_name, 
                                      String index_name). 
     
   
  You may also be informed on the work your data base is doing. 
   
public type DB2Info:
   creating_table                    (String path), 
   loading_table                     (String path),
   unloading_table                   (String path), 
   beginning_table_synchronisation   (String path), 
   ending_table_synchronisation      (String path), 
   creating_chunk                    (String path), 
   loading_chunk                     (String path), 
   unloading_chunk                   (String path),
   beginning_chunk_synchronisation   (String path), 
   ending_chunk_synchronisation      (String path).
   
   
   Data of these types are transmitted to the functions 'warn' and 'inform', that you must
   provide when you create your data base root.

   For your convenience we provide  the following formating functions transforming data of
   type DB2Error and DB2Info into English sentences:
   
public define String
   en_format
     (
       DB2Error    e
     ) =
   if e is 
     {
       file_not_found(p)          then "File not found: '"+p+"'", 
       file_reading_problem(p)    then "Cannot read file: '"+p+"'", 
       file_type_problem(p)       then "Incompatible type: '"+p+"'",
       cannot_open_file(p)        then "Cannot open file: '"+p+"'", 
       cannot_write_file(p)       then "Cannot write into file: '"+p+"'",
       cannot_find_index(d,t,i)   then "Cannot find index: '"+d+"/t_"+t+"["+i+"]" 
     }.
   
   
public define String
   en_format
     (
       DB2Info     i
     ) = 
   if i is 
     {
       creating_table(p)                    then "Creating table: '"+p+"'", 
       loading_table(p)                     then "Loading table: '"+p+"'", 
       unloading_table(p)                   then "Unloading table: '"+p+"'", 
       beginning_table_synchronisation(p)   then "Beginning table synchronisation: '"+p+"'", 
       ending_table_synchronisation(p)      then "Ending table synchronisation: '"+p+"'", 
       creating_chunk(p)                    then "Creating chunk: '"+p+"'", 
       loading_chunk(p)                     then "Loading chunk: '"+p+"'", 
       unloading_chunk(p)                   then "Unloading chunk: '"+p+"'", 
       beginning_chunk_synchronisation(p)   then "Beginning chunk synchronisation: '"+p+"'", 
       ending_chunk_synchronisation(p)      then "Ending chunk synchronisation: '"+p+"'"
     }. 
   
   
      *** (2.3) Tables. 

   The type of the rows of a table  is up to you (but must be serializable). However, this
   data base  management system includes a  mecanism for handling the  possible changes in
   the definition  of the types of the  rows of a table,  in such a way  that updating the
   actual table file  format on the disk  is automatic.  For this reason,  the type scheme
   'DB2Table($Row,$HRow)'  representing tables  has two  type parameters.   The  first one
   represents the  current type of the  rows of the  table, the second one  represents the
   history of all successive  types of the rows of the table.   With this mecanism, and if
   you respects some principles explained below,  your program will always be able to read
   old tables saved in old formats.   When tables (actually table chunks) are written back
   to disk, they are always written in the most recent format.
      
public type DB2Table($Row,$HRow):...         (an opaque type)

   
   
   
      *** (2.4) Indexing. 

   In order to speed  up the access to the data, especially  when dealing with big tables,
   and also to optimize  memory usage, we need an indexing system.   This system allows to
   define for each table a primary indexing method and secondary indexing methods.
   
   An index is some way of finding rows of a table more quickly than by just having a look
   at all rows until the wanted rows are  found. This is similar to a dictionary. When you
   are looking for a word in a dictionary,  you don't start at the beginning and check all
   words until you find yours. You have some more efficient method.
   
   Notice however  that this process  is specific to  the method used for  selecting items
   from  the dictionary.   In this  case, the  items  you want  to find  are selected  'by
   name'. Since items in the dictionary are ordered alphabetically by name, the search may
   be performed  quickly. However, what  about finding all  words the definition  of which
   contains the word 'dog' ? This is much more difficult, and requires a priori a complete
   search item by item.
   
   In order  to solve this problem,  the dictionary could  have an 'index' (in  general it
   does not have one), within which you should  easily find the word 'dog', and get a list
   of pages or  item numbers or item  names whose definition contains the  word 'dog'. You
   may also want to  find all words of containing the string 'dog'  in their name. In this
   case, you need yet another kind of index.
   
   From this dictionary story, we should remember two things:
   
     1. The dictionary is ordered in such a way that finding an item 'by name' is easy, 
     2. If we  want to  find items  according to other  criteria, we  need an  extra index
        (maybe one for each criterium).

   The way the  dictionary is ordered could be called the  'primary indexing'.  Each extra
   index may be  called a 'secondary indexing'.  The same principles  apply to data bases,
   except that instead of ordering items by alphabetical order we use 'hashing methods'.

   Indexes for a table of type 'DB2Table($Row,$HRow)' are of the following type:
   
public type DB2Index($Row):...            (an opaque type)   
   
   

  
   
      *** (2.5) Initializing a table. 

   Tables are initialized by 'init_dbtable':
   
public define DB2Table($Row,$HRow)
   init_dbtable
     (
       DB2Root                          root, 
       String                           table_name,
       Int32                            average_file_size, 
       $HRow -> $Row                    update,
       $Row -> $HRow                    store,
       $Row -> $Locked                  locked,
       DB2Index($Row)                   primary_index,
       List(DB2Index($Row))             secondary_indexes
     ). 
   
   This function must  be executed only once  per table when your program  starts. Now, we
   discuss the arguments.
   
   'root' determines the data base to which the table belongs. 
   
   The name 'table_name' above becomes part of the names of the files containing the table
   (located in the  directory 'directory(root)').  'init_dbtable' does not  load the table
   from the disk.  Tables are divided into  'chunks' and a chunk is loaded only if needed.
   If the table does  not exist on the disk, 'init_dbtable' creates  an empty table of the
   right type.
   
   'average_file_size' is the average size you  want for chunk files.  This is measured in
   bytes (octets). For example, if you put  '4096' for this argument, the files into which
   the  table  chunks will  be  stored  will have  (approximately)  a  average  size of  4
   kilobytes. Of course, how the table is divided into chunks depends on this number. As a
   consequence,  changing  this  number  may  require a  complete  reorganization  of  the
   table. Hence,  you should better choose the  right size at first.  Nevertheless, if you
   change your mind the table is automatically reorganized at its next initialization.  Of
   course, depending on the total size of the table, this may take some time.
      
   The 'update' and 'store' functions are used for automating the changes of format of the
   tables. This is explained below in  the section 'Handling changes in table formats'. At
   the beginning, while  the two types '$Row'  and '$HRow' are identical, you  can use the
   function 'identity'  (actually a scheme  of function, defined  in 'tools/basis.anubis')
   for both 'update' and 'store'.

   For security reasons, you  may want to protect some informations in  a table from being
   modified.   For example,  in a  'products' table  the reference  of the  product should
   perhaps never  be modified.  The argument 'locked'  is of type '$Row  -> $Locked' where
   '$Locked' is any  type for which equality  (=) is meaningful (so it  should not contain
   data of type  'Float'). When the system is on  the point to update a row  in a table it
   first checks  if 'locked(r1)  = locked(r2)', where  'r1' and  'r2' are the  current and
   future values of the row.  If this check fails the row is not updated.
   
   For example, for initializing your table of products, locking the two fields 'supplier'
   and 'name', you just have to provide a function of type:
   
                                  Product -> (String,String)
   
   extracting the supplier name  and product name from the row. If  you don't want to lock
   data in a  table, define the 'locked'  function as '($Row r) |->  (One)unique'.  At the
   opposite, if you use 'identity' for 'locked' (provided there is no 'Float' in the row),
   all the data in the table are locked, but you can still add new rows to this table.

   
   
   
      *** (2.6) Initializing an index.
   
   The indexes are initialized by 'init_dbindex':
   
public define DB2Index($Row)
   init_dbindex
     (
       String             index_name,    // used as part of a file name
       $Row -> $Info      extract
     ). 
   
   The  'extract' function extracts  from a  row the  information which  will be  used for
   searching using the index. For example, if  you want to make an index for searching for
   clients by  their names,  you should use  the implicit  destructor 'name' of  your type
   Client as the 'extract' function. 
   
   You must provide  at least one index,  which is called the 'primary'  index. This index
   should correspond  to the  main (primary)  search method, and  also determines  how the
   table is  divided into chunks.  You  provide an arbitrary number  of secondary indexes,
   one for each other search methods you have in mind for this table. You can use the same
   name for several indexes, provided they are not in the same table.
   

   
   
   
   
      *** (2.7) Data bases. 
   
   You must  define the type of  your data base (you  may have several of  them).  Since a
   data  base is  essentially a  set  of tables,  the type  of  your data  base should  be
   something  like this  (at the  beginning, you  can  use the  same type  for '$Row'  and
   '$HRow'):
   
   type MY_DB:
     my_db
       (
         DB2Table(Client,HClient)         clients, 
         DB2Table(Product,HProduct)       products, 
         DB2Table(Supplier,HSupplier)     suppliers, 
         ...
       ). 
          
   where  the  types  'Client',  'Product',   etc...   have  been  previously  defined  by
   yourself. At the  beginning, 'HClient' may be the same type  as 'Client' etc...  Notice
   that a  datum of type  'Client' is just  an entire row  in the 'clients'  table. Hence,
   'Client' is probably a  type with just one alternative and the  components needed for a
   'client', like 'name', 'address', etc...

   Your program  will be  safer if you  choose distinct  types for all  tables in  a given
   database.
   
   You may think that the table 'products' for  example should be a set of tables, one per
   product, because  you will have many  products and many informations  for each product.
   Hence, you would like to use a family  of tables (of the same type) instead of just one
   very  big table.   This  is not  needed, because  this  system splits  big tables  into
   'chunks' automatically,  and only the chunks  which are needed are  loaded into memory.
   So, your  big table is  actually a family  of tables, but  this fact is  transparent to
   you. Hence, you use only one table for each  type of data you have to store in the data
   base. The only parameter you can tune is the average size of chunks.
   
   What if the type $Row has several alternatives ? This means that your table has several
   sorts of  rows (not with  the same columns  !).  But in  this case, you  should perhaps
   better use several tables. Nevertheless, this makes no problem.
       
   
   
   For example, you may write something like this:
   
   with   shutdown_v = var((Bool)false), 
          my_root = root(my_anubis_directory+"/my_data_base",
                         5, 
                         shutdown_v,
                         (DB2Error e) |-> send_mail_to_admin(e),
                         (DB2Info i) |-> unique), 
          my_data_base = 
     my_db
       (
         init_dbtable(my_root, "clients",   2048, identity, identity, locked, primary, []), 
         init_dbtable(my_root, "products",  4096, identity, identity, locked, primary, []), 
         init_dbtable(my_root, "suppliers", 4096, identity, identity, locked, primary, []), 
         ...
       ),    
   
   At that point you have the datum  'my_data_base' at hand, which is of type 'MY_DB', and
   which  represents the  whole data  base.  The  preparation above  determines  the whole
   structure of the data  base.  With a datum of type 'MY_DB' at  hand, you have an access
   to all the corresponding tables.
   
  
    
 
   
   
      *** (2.8) Handling changes in table formats. 

   Up to  here the types used  as instantiations of '$Row'  and '$HRow' are  the same one.
   That's OK, and  you have begun to  distribute your program and your  users have created
   tables whose types  are your types 'Client', 'Product' etc... If  you simply modify the
   definition of (say) the  type 'Client', your new program will not  work with the tables
   created  by your  users, which  is  obviously a  catastrophe. Fortunately,  there is  a
   remedy, and here it is.
   
   Assume that you  want to change the  definition of the type 'Client',  because you need
   more columns in  the table of clients.   As an example, assume that  your type 'Client'
   was first defined as:
   
   type Client:
     client(String name, 
            String address). 
   
   and you want to add a new component (column of the table):
   
            Int32 age
   
   
   --- Step 1:
   
   The first thing to  do is to make two copies of  your original type definition, because
   from now on, the types '$Row' and '$HRow' are no more identical:
   
   type Client:                  // current type of rows of 'clients' table
     client(String name, 
            String address). 
   
   type HClient:                 // history of type of rows of 'clients' table
     client(String name, 
            String address). 
   
   
   --- Step 2:
   
   The first  alternative of 'HClient' should  never be changed, because  it represents an
   'historical' way of representing clients. The only  thing that you can do is change the
   name of  the alternative.  We recommend  to name it  'version_1', and  to use  the name
   'version_2' for the  second alternative representing the new type  of rows.  Hence, the
   type 'HClient' becomes:
   
   type HClient:  
     version_1(String name, 
               String address),
     version_2(String name, 
               String address, 
               Int32  age). 

   Important  notice: When  a change  intervenes in  the type  of rows  of the  table, the
   alternative representing  the new type  of rows must  be added at  the end of  the type
   'HClient' (or any  other instance of '$HRow').  This is because  in serialized data the
   alternative  names   are  lost,  and   replaced  by  their   number  in  the   list  of
   alternatives. Also notice that another method  will be required if you create more than
   256 versions.

   The type 'Client' must also be changed in order to reflect the new format: 
   
   type Client: 
     client(String name, 
            String address,
            Int32 age). 
   
   
   
   
   --- Step 3:
   
   Now,  we  need   'conversion'  functions  in  both  directions   between  'Client'  and
   'HClient'. Presisely, we need the functions:
   
         (HClient -> Client)update
         (Client -> HClient)store
   
   The  function 'update'  gets an  'historical' row  (hence of  type 'HClient')  and must
   transform it into a row in the current format. In our example, it could be:
   
   define Client
     update
       (
         HClient hc
       ) =
     if hc is 
       {
         version_1(name,addr)          then client(name,addr,0),
         version_2(name,addr,age)      then client(name,addr,age)
       }.
   
   Of course, in the case of a row  in the old format (version_1), we need a default value
   for the  age. We have chosen  0 in the example.   In any traditional  data base system,
   when you add  a column to a table, you  need to fill this column  with a default value,
   even if this default value is 'NULL'.
   
   The other function does not require default values in principle, because it is mainly a
   conversion between  the current version and  the latest one (i.e.  essentially the same
   one):
   
   define HClient
     store
       (
         Client c
       ) =
   if c is client(name,addr,age) then version_2(name,addr,age). 
   
   
   The type used for  storing the data on the disk is always  'HClient' (hence the name of
   the  function  'store'),  and according  to  the  above  function  they are  stored  as
   'version_2(...)'.  The  type 'Client'  is used only  internally.  This is  required for
   being able to handle file containing different versions of the tables.
   
   

      *** (2.9) Handling a change of the primary index. 

   You may  also want to  change the  primary indexing method,  i.e. the function  used to
   construct  the primary  index. Such  a  change implies  a reorganization  of the  whole
   table. Even if the number of chunks does not change, most of the rows of the table will
   move from one chunk to another one.

   When a  table is initialized, the system  checks if the primary  indexing is compatible
   with the dispatching of rows into the chunks. If it is not, the table is reorganized. 
   
   Hence, the only  thing you have to do  is just to change the 'primary'  argument in the
   call to 'init_dbtable'. That's all.

   However, you  must be conscious  that changing the  primary search method may  put your
   program down. Indeed, when you want to get rows from a table or to update them, you may
   use  the term  'primary(model)'  (of  type 'DB2Select($Row)';  see  below for  details)
   meaning that you want all rows whose  primary datum is equal to 'model'.  Of course, if
   you change  the primary search method,  the model may become  completely wrong.  Hence,
   you should search for all occurrences of 'primary' in your source in order to adapt the
   model or maybe change the row selection method.

   Since, secondary search is  almost as fast as primary search, you  will maybe prefer to
   introduce a new secondary search method rather than changing the primary search method.
   
   

   
   
   *** (3) Using the data base. 

   When your data base is initialized, you can use it. Below are the tools for this. 
   
   
   
      *** (3.1) Adding rows to a table. 
   
   Adding rows to a table is performed by the following function:
      
public define List(DB2Error)
   add_rows
     (
       DB2Table($Row,$HRow)    the_table,
       List($Row)              new_rows
     ). 
   
   For example, you may write:
   
                        add_rows(clients(my_data_base),[row1,row2,row3])
   
   where 'row1','row2' and 'row3' are  of type 'Client'.

   The following variant is more convenient for adding just one row. 
      
public define List(DB2Error)
   add_row
     (
       DB2Table($Row,$HRow)    the_table,
       $Row                    new_row
     ). 
   
   The  value returned  is  of type  'List(DB2Error)'. If  this  list is  empty, no  error
   occurred. Otherwise, you get informations on those files which were not available.

   
   
   
      *** (3.2) Row selection methods. 
   
   In order to select a set of rows from a table (either for getting, updating or deleting
   them), you have several methods.  Row selection methods are of the following type:
   
public type DB2Select($Row):...       (an opaque type)
   
   These methods are the following:
   
     1. 'by condition'.  You  may use a function (denoted 'which' below)  of type '$Row ->
   Bool' to be used  for checking if a row should be  selected. This method is inefficient
   (except  if the table  is small),  because it  requires a  complete examination  of the
   table.  To be used only if the other methods cannot apply.
   
public define DB2Select($Row)
   condition
     (
       $Row -> Bool     which
     ). 
   
   Only the rows 'r' such that 'which(r)' is 'true' are selected. 
   
   
     2. 'by the primary index'. This is the fastest method. 
   
public define DB2Select($Row)
   primary
     (
       $Primary     model
     ). 
   
   Only the rows for which the primary datum is equal to 'model' are selected. 
   
   
     3. 'by a secondary index'. This is almost as fast as method 2. 
   
public define DB2Select($Row)
   secondary
     (
       String           index_name,
       $Secondary       model
     ). 
   
   Only the rows for which the secondary datum for the given index is equal to 'model' are
   selected.
   
   
  
   
      *** (3.3) Getting rows from a table. 

   In order  to get all  rows from  a table satisfying  some condition, use  the following
   function:
   
public define List(Result(DB2Error,$Row))
   get_rows
     (
       DB2Table($Row,$HRow)    the_table, 
       DB2Select($Row)         selection_method
     ). 
   
   This  function returns  all  rows from  the  table which  satisfy  the given  selection
   method. Errors may occur  when there are file problems. In this  case you get a mixture
   of rows and errors.
   

   
      
      *** (3.4) Updating rows in a table. 
   
   Updating rows in  a table is generally  the consequence of a previous  reading of these
   rows. Indeed,  interactive programs will first  show the row  to be updated to  a human
   user (phase  1). The user  is supposed to  modify the data by  hand. When the  data are
   modified, they may be  put in the table in order to  replace the previous values (phase
   2).
   
   This makes  a problem because, the  same data may  have been modified by  another human
   user (or in  some automatic way) in the  meantime (i.e.  between phase 1  and phase 2).
   Hence, phase 2  should perhaps not be performed  if the data have been  modified in the
   meantime. For this reason, when you want to  update one or several rows in a table, you
   do not provide the new values, but a function (denoted 'how_to_update' below) of type:
   
                                       $Row -> Maybe($Row)
   
   This function receives  as its argument the current  row as it stands in  the data base
   when phase 2 begins.  It should compare this row with the row it remembers from phase 1
   and decide  if the row  must be updated or  not.  If the  row must not be  updated, the
   function 'how_to_update'  must return 'failure'.  If  on the contrary, the  row must be
   updated, it must return the value 'success(r)', where 'r' is the new value of the row.
   
   Now, if  no error occurs, the 'update_rows'  functions return a datum  of the following
   type for each row:
   
public type DB2UpdateResult($Row):
   locked        ($Row the_current_row, $Row forbidden_value), 
   not_updated   ($Row the_current_row),
   updated       ($Row the_new_row).

   The result  is 'locked(r,f)' if  updating the row  would have modified locked  data. Of
   course in this  case, the row is not updated.   'r' is the non update  row, 'f' is what
   the row would have become if updating had been performed.
  
   It is  'not_updated(r)' if the 'how_to_update'  function returned 'failure',  and it is
   'updated(r)' when the row has been updated.  In all cases, 'r' is the new current value
   of the row in the table.
         
   
public define List(Result(DB2Error,DB2UpdateResult($Row)))
   update_rows
     (
       DB2Table($Row,$HRow)   the_table, 
       DB2Select($Row)            selection_method,
       $Row -> Maybe($Row)        how_to_update
     ). 
   
   Only the rows which satify the  selection method are eventually updated.  Of course the
   function returns  a list of possible  errors and 'DB2UpdateResult($Row)',  one for each
   selected row if there is no error.
   
   
   
   
   
      *** (3.5) Deleting rows from a table. 
   
public define List(Result(DB2Error,$Row))
   delete_rows
     (
       DB2Table($Row,$HRow)   the_table, 
       DB2Select($Row)            selection_method,     
     ). 
   
   The selected rows  are deleted from the table.   The result is the list  of the deleted
   rows (mixed with possible errors).

   Notice that  rows are deleted regardless of  locking. So deleting may  be dangerous. Be
   careful.
   
   
   
   --- That's all for the public part ! --------------------------------------------------

   
   
   
   
   
   

   ----------------------------------- Contents ------------------------------------------

   *** [1] Opaque and private types.       
      *** [1.1] Chunks.
      *** [1.2] Secondary indexes.    
      *** [1.3] Tables.
   *** [2] Initializing. 
      *** [2.1] Roots. 
      *** [2.2] Tables. 
      *** [2.3] Indexes. 
   *** [3] Tools for getting tables, chunks and indexes.
      *** [3.5] Loading a secondary index. 
      *** [3.1] Loading a table. 
      *** [3.2] Getting a table. 
      *** [3.3] Loading a chunk. 
      *** [3.4] Getting a chunk. 
      *** [3.6] Getting a secondary index. 
   *** [4] Adding rows. 
      *** [4.2] Adding a set of rows.
      *** [4.3] The public tool 'add_rows'. 
      *** [4.4] The public tool 'add_row'. 
   *** [5] Row selection. 
   *** [6] Acting on rows. 
      *** [6.1] Acting on selected rows of a chunk. 
      *** [6.2] Waiting for the end of chunk synchronisation. 
      *** [6.3] Acting on a chunk. 
      *** [6.4] Acting by condition. 
      *** [6.5] Acting by primary index. 
      *** [6.6] Acting by secondary index. 
      *** [6.7] Waiting for the end of table synchronisation. 
      *** [6.8] Acting in general. 
   *** [7] Utilization commands. 
      *** [7.1] 'get_rows'. 
      *** [7.2] 'update_rows'. 
      *** [7.3] 'delete_rows'. 
   *** [8] Synchronising memory with disk. 
      *** [8.1] Synchronising a table file. 
      *** [8.2] Synchronising chunk files. 
         *** [8.2.1] One chunk. 
         *** [8.2.2] One 'new' chunks (moving table).
            *** [8.2.2.1] 'Increasing' case.
            *** [8.2.2.2] 'Decreasing' case.
            *** [8.2.2.3] Both cases.
         *** [8.2.3] All chunks. 
      *** [8.4] Synchronising everything. 
      *** [8.5] Asking for delayed synchronisation.
   *** [9] Changing the number of bits of hash. 
      *** [9.1] Hashing. 
      *** [9.2] Deciding to change the number of bits of hash. 
      *** [9.3] Performing a change. 

   ---------------------------------------------------------------------------------------   
   
read tools/basis.anubis
   


   
   
   *** [1] Opaque and private types.       
   
      *** [1.1] Chunks.
   
   Table chunks are  loaded into memory only  on demand. During the loading  the format is
   changed to some format appropriate for the memory. The format is changed again when the
   table chunk is saved to disk.
      
   Each  chunk is  characterized  by  a 'hash'  (of  type Int32).   Chunks  may be  loaded
   independently of each other. A chunk in memory has the following format:
   
type ChunkSynState:
   unchanged,         // no change in the table since last synchronisation
   changed,           // the chunk needs to be synchronised
   synchronising.     // the chunk is currently synchronising with disk
   
   
type LoadedChunk($Row):
   lchunk
     (
       Var(Int32)           last_used_v,    // last time this chunk was used
       Var(ChunkSynState)   state_v,
       Var(Bool)            transfered_v,   // used only by moving tables
       Var(List($Row))      rows_v          // always a rather short list
     ).

   Now, a chunk may be either loaded or not loaded:
   
type Chunk($Row):
   not_loaded,                    // the chunk is not loaded
   loaded(LoadedChunk($Row)).     // the chunk is loaded

   
   When  the chunk  is not  loaded, no  information is  needed, because  all  the relevant
   information is in  the table itself. When we need  a chunk we get a  hash value, and we
   have everything we need.
   
   When a chunk  is loaded we need  to know when it was  used for the last  time.  This is
   because, when memory becomes low, we need to unload some chunks. We unload those chunks
   which have not been used since the longuest time.
   
   The 'changed_v' flag means when 'true' that the chunk is not synchronised with its file
   on the disk.  The flag 'transfered_v' is  used when the table is moving (see below). Of
   course, the component 'rows_v' contains the list of all rows in this chunk.  Normally a
   very short list.

   The file containing the chunk contains a serialized datum of type:
   
type ChunkFile($HRow):
   chunk(List($HRow)    rows). 

   The conversion function 'store' is used when saving a chunk on disk for converting from
   '$Row' to '$HRow'. Conversely, when a chunk is read from disk, the function 'update' is
   used for converting from '$HRow' to '$Row'. 
   
   The name of a chunk file is constructed as follows: 
   
       c_10_675_clients
       | |  |   |
       | |  |   +----------- name of table
       | |  +--------------- value of hash
       | +------------------ number of bits of hash
       +-------------------- 'c' for 'chunk'
   
   

   
   
   
      *** [1.2] Secondary indexes.    

   When an index is  loaded, it is in the form of an  array (multiple dynamic variable) of
   lists of integers.
   
type LoadedIndex($Row):
   lindex(String                   index_name, 
          (Int32,$Row) -> Int32    hash_row, 
          MVar(List(Int32))        values). 
   
   An index (for a given number of bits of hash) is just some kind of function associating
   a  list of  integers to  all integers  between 0  and the  2^bits_of_hash. It  works as
   follows. When a search is to be  performed using a secondary index, the secondary datum
   is  hashed. This  gives an  integer 'sh'  which is  between 0  and  2^bits_of_hash. The
   secondary index associates  to 'sh' a list of integers,  say [n1,n2,n3]. These integers
   are primary hashes. This means that the wanted rows are in the chunks number n1, n2 and
   n3. Of course, not all rows in these chunks  are to be selected, but all the rows to be
   selected are in these chunks.

   The function  'hash_row' takes as its  two arguments the number  of bits of  hash and a
   row. It returns  the secondary hash value of  this row, i.e. the result  of hashing the
   secondary search datum of this row.
   
   When it is not loaded, an index is represented into memory by:
   
public type DB2Index($Row):
   dbindex
     (
       String                     index_name,  
       (Int32,$Row) -> Int32      hash_row
     ). 

   An index is loaded when the table is  loaded.  The index is stored on disk in the table
   file as a datum of type:
   
type IndexFileDatum:   
   v1(String                index_name, 
      List(List(Int32))     entries).
   
   
   
   
   
   
      *** [1.3] Tables.
   
   Loaded tables must be  synchronised with disk from time to time. They  may be in one of
   the following synchronisation states:
   
type TableSynState:
   unchanged,         // no change in the table since last synchronisation
   changed,           // the table needs to be synchronised
   synchronising.     // the table is currently synchronising with disk

   See the section on synchronisation for more details. 
   
   A table when loaded into memory contains a datum of the following type:
   
type LoadedTable($Row,$HRow):
   ltable
     (
       DB2Root                       root, 
       String                        table_name, 
       Int32                         average_chunk_size, 
       Var(Int32)                    last_used, 
       Var(Int32)                    number_of_rows,
       $HRow -> $Row                 update,
       $Row -> $HRow                 store, 
       ($Row,$Row) -> Bool           locked, 
       Var(TableSynState)            changed_v,
       Int32                         bits_of_hash, 
       MVar(Chunk($Row))             chunks_mv,
       String                        primary_index_name, 
       (Int32,$Row) -> Int32         primary_hash,
       List(LoadedIndex($Row))       secondary_indexes,
       Var(Maybe(Int32))             mb_bits_of_hash_2_v
     ). 
   
   A  table is  either not  loaded or  loaded. When  a table  is loaded,  only  the global
   informations pertinent to this table are loaded. Chunks, hence rows, are not loaded.
   
type Table($Row,$HRow):
   not_loaded
     (
       DB2Root                  root, 
       String                   table_name, 
       Int32                    average_chunk_size, 
       $HRow -> $Row            update,
       $Row -> $HRow            store, 
       ($Row,$Row) -> Bool      locked, 
       DB2Index($Row)           primary_index,
       List(DB2Index($Row))     secondary_indexes
     ),
   loaded(LoadedTable($Row,$HRow)). 
   
   
   In a  'loaded' table,  the number of  entries in  the multiple variable  'chunks_mv' is
   '2^bits_of_hash'.  In order to find the chunk containing a row, given the primary datum
   for this  row, we hash the primary  datum with the 'my_hash'  function (defined below),
   using the given number of bits.  Then, the corresponding entry of the multiple variable
   contains the wanted chunk.
   
define Int32
   my_hash
     (
       Int32    bits, 
       $T       datum
     ).
   
   The  reason   why  we   use  this  function   instead  of  'simple_hash'   (defined  in
   'predefined.anubis') is explained in the  section entitled 'Changing the number of bits
   of hash'.
   
   
   When  the data  base  is  initialized, all  tables  in the  data  base  are created  as
   'not_loaded'.   When  a table  is  required,  it is  loaded,  but  its  chunks are  not
   loaded. Chunks are loaded only on demand.
   
   
   Since tables  are changing  dynamically from 'not_loaded'  to 'loaded'  and conversely,
   they need to be put into a variable. Hence the following type:
   
public type DB2Table($Row,$HRow):
   table(Var(Table($Row,$HRow))). 
   
   
   A table is stored on disk in the following format: 
   
type TableFile:
   table   (Int32                  number_of_rows, 
            Int32                  bits_of_hash, 
            String                 primary_index_name,
            List(IndexFileDatum)   secondary_indexes,
            Maybe(Int32)           mb_bits_of_hash_2). 

   and the name of the file is constructed as follows:
   
       t_clients
       | |
       | +------------------ name of table
       +-------------------- 't' for 'table'
   
   
   

   
   
      
   *** [2] Initializing. 
   
   
   
      *** [2.1] Roots. 
   
   A root for a data base contains the following informations:
   
public type DB2Root:
   dbroot
     (  
       String              directory, 
       Int32               delay, 
       Var(Bool)           shutdown_v,
       DB2Error -> One     warn
     ). 
   
   Below is the public function for constructing such a root:
   
public define DB2Root
   root
     (
       String              directory, 
       Int32               delay,     
       Var(Bool)           shutdown_v,
       DB2Error -> One     warn
     ) =
   forget(make_directory(directory)); // make the directory if it does not already exist
   dbroot(directory,delay,shutdown_v,warn). 
   
   
   
   
   
      *** [2.2] Tables. 
   
   Initializing  a table  consists  just in  gathering  the informations  (and making  the
   comparison function for locked data). The table is initialized as 'not_loaded'.
   
public define DB2Table($Row,$HRow)
   init_dbtable
     (
       DB2Root                          root, 
       String                           table_name,
       Int32                            average_file_size, 
       $HRow -> $Row                    update,
       $Row -> $HRow                    store,
       $Row -> $Locked                  locked,
       DB2Index($Row)                   primary_index,
       List(DB2Index($Row))             secondary_indexes
     ) =
   if root is dbroot(directory,_,_,_) then 
   table(var(not_loaded
     (
       root,
       table_name, 
       average_file_size, 
       update,
       store, 
       ($Row r1, $Row r2) |-> locked(r1) = locked(r2), 
       primary_index, 
       secondary_indexes
     ))). 
   

   
   
   
      *** [2.3] Indexes. 
   
   Initializing  an index  amounts in  gathering  the informations,  and transforming  the
   'extract' function, because we cannot keep the type '$Info'. Otherwise, it would not be
   possible to make lists of secondary  indexes. Making such lists is possible because the
   type 'DB2Index($Row)' does not depend on '$Info'. 
   
public define DB2Index($Row)
   init_dbindex
     (
       String             index_name,    // used as part of a file name
       $Row -> $Info      extract
     ) =
   dbindex(index_name,
           (Int32 bits, $Row r) |-> my_hash(bits,extract(r))). 
   
   

   
 
   *** [3] Tools for getting tables, chunks and indexes.

   We have to load  tables and chunks.  Of course, we keep them  into memory when they are
   loaded. Some of them are unloaded only if the memory becomes low.
   
   Hence, we have the following main functions for getting:
   
      get_loaded_table
      get_loaded_chunk
      get_loaded_index
   
   If what we want is already loaded it  is juste returned. Otherwise a call to one of the
   following functions is performed:
   
      load_table
      load_chunk
       
   and the loaded object is returned except if some error occurs. 
   
   
      *** [3.5] Loading a secondary index. 
   
   Secondary indexes are not  in separate files but in the table  file itself.  When it is
   loaded, an index is just a multiple  variable with as many slots as 2^bits, whose slots
   contain lists  of primary hashes. Actually, it  associates a list of  primary hashes to
   each secondary hash.
   
   
define MVar(List(Int32))
   load_index_values
     (
       List(List(Int32))        values,
       MVar(List(Int32))        mv,
       Int32                    i
     ) =
   if values is 
     {
       [ ] then mv,
       [h . t] then
         mv(i) <- h;
         load_index_values(t,mv,i+1)
     }.
   

define List(List(Int32))   
   assoc_index_values
     (
       String                  index_name,
       List(IndexFileDatum)    values
     ) =
   if values is 
     {
       [ ] then [ ], 
       [i1 . others] then 
         if i1 is v1(n,entries) then
         if n = index_name
         then entries
         else assoc_index_values(index_name,others)
     }.
   
   
define List(LoadedIndex($Row))
   install_secondary_indexes
     (
       List(DB2Index($Row))    indexes,
       List(IndexFileDatum)    values,
       Int32                   bits
     ) =
   if indexes is 
     {
       [ ] then [ ],
       [i1 . others] then 
         if i1 is dbindex(name1,hash_row) then 
         [lindex(name1,hash_row,
                 load_index_values(assoc_index_values(name1,values),
                                   mvar(1<<bits,[]),
                                   0))
          . install_secondary_indexes(others,values,bits)]
     }.
   
   
   
      *** [3.1] Loading a table. 
   
   If there is no table file, we create  an empty table. Otherwise, we load the table from
   the table file. It may be the case that a read or type error occurs. 
   
define Result(DB2Error,LoadedTable($Row,$HRow))
   load_table
     (
       DB2Root                        root,
       String                         name,       // of table
       Int32                          acs,        // average chunk size
       $HRow -> $Row                  update, 
       $Row -> $HRow                  store, 
       ($Row,$Row) -> Bool            locked, 
       DB2Index($Row)                 primary_index, 
       List(DB2Index($Row))           secondary_indexes,
       Var(Table($Row,$HRow))         location    // where to put the table
     ) =
   with path = directory(root)+"/t_"+name, 
   if (RetrieveResult(TableFile))retrieve(path) is 
     {
       cannot_find_file  then // create an empty table
         with tbl = ltable
             (
               root, 
               name, 
               acs,
               var(now),                 // last used
               var((Int32)0),            // number of rows
               update,
               store,
               locked,
               var(unchanged),           // changed_v
               10,                       // bits_of_hash
               mvar(1,not_loaded),       // only 1 chunk
               index_name(primary_index), 
               hash_row(primary_index),
               map((DB2Index($Row) i) |-> 
                  if i is dbindex(name,hash_row) then
                  lindex(name,hash_row,mvar(1,[])),secondary_indexes),
               var(failure)              // currently not moving
             ),
         location <- loaded(tbl); 
         ok(tbl),
   
       read_error then 
         error(file_reading_problem(path)),
   
       type_error then 
         error(file_type_problem(path)),
   
       ok(TableFile t) then if t is table(nor,bits,piname,sisvals,mb_bits_2) then 
         with tbl = ltable
             (
               root, 
               name, 
               acs,
               var(now),                  // last used
               var(nor),                  // number of rows
               update,
               store,
               locked,
               var(unchanged),            // changed_v
               bits,                      // bits of hash
               mvar(1<<bits,not_loaded),  // chunks
               index_name(primary_index), 
               hash_row(primary_index), 
               install_secondary_indexes(secondary_indexes,sisvals,bits),
               var(mb_bits_2)
             ),
         location <- loaded(tbl); 
         ok(tbl)
     }. 
   
   
   
      *** [3.2] Getting a table. 

   Eventually, we need to load the table. 
   
define Result(DB2Error,LoadedTable($Row,$HRow))
   get_loaded_table
     (
       DB2Table($Row,$HRow)  the_table,
     ) =
   if the_table is table(v) then
   if *v is 
     {
       not_loaded(root,tn,acs,up,st,lk,pi,sis) then 
         load_table(root,tn,acs,up,st,lk,pi,sis,v), 
   
       loaded(lt) then 
         ok(lt)
     }. 
   
   
   
   
   
      *** [3.3] Loading a chunk. 

   If there is no chunk file, we create  an empty chunk. Otherwise, we load the chunk from
   the file. This may produce a read or type error.
   
define Result(DB2Error,LoadedChunk($Row))
   load_chunk
     (
       String             directory, 
       String             table_name, 
       Int32              bits,
       Int32              hash,
       MVar(Chunk($Row))  chunks, 
       $HRow -> $Row      update
     ) =
   with path = directory+"/c_"+bits+"_"+hash+"_"+table_name, 
   if (RetrieveResult(ChunkFile($HRow)))retrieve(path) is 
     {
       cannot_find_file then
         with c = (LoadedChunk($Row))lchunk(
                                  var(now),        // last used
                                  var(changed),    // not synchronised with disk
                                  var(false),      // transfered
                                  var([])),        // rows
         chunks(hash) <- loaded(c); 
         ok(c), 
   
       read_error then
         error(file_reading_problem(path)),
   
       type_error then
         error(file_type_problem(path)), 
   
       ok(cf) then if cf is chunk(rows) then 
         with c = (LoadedChunk($Row))lchunk(
                                  var(now),        // last used
                                  var(unchanged),  // synchronised with disk
                                  var(false),      // transfered
                                  var(map(update,rows))),
         chunks(hash) <- loaded(c); 
         ok(c)
    }. 
   
   
   
   
   
      *** [3.4] Getting a chunk. 
   
define Result(DB2Error,LoadedChunk($Row))
   get_loaded_chunk
     (
       String                     directory, 
       String                     table_name, 
       Int32                      bits, 
       Int32                      hash,
       MVar(Chunk($Row))          chunks_mv,
       $HRow -> $Row              update
     ) =
   with c = *chunks_mv(hash), 
   if c is
     {
       not_loaded then
         load_chunk(directory,table_name,bits,hash,chunks_mv,update),
   
       loaded(lc) then ok(lc)
    }. 

   
   
   
   

      *** [3.6] Getting a secondary index. 
   
define Result(DB2Error,LoadedIndex($Row))   
   assoc
     (
       String                    dir, 
       String                    table_name, 
       String                    index_name, 
       List(LoadedIndex($Row))   indexes
     ) =
   if indexes is 
     {
       [ ] then error(cannot_find_index(dir,table_name,index_name)),
       [i1 . others] then if i1 is lindex(name,_,_) then 
         if name = index_name
         then ok(i1)
         else assoc(dir,table_name,index_name,others)
     }.
   
   
define Result(DB2Error,LoadedIndex($Row))   
   get_loaded_index
     (
       LoadedTable($Row,$HRow)   the_table, 
       String                    index_name 
     ) =
   if the_table is 
     ltable(root,tn,acs,lu,nor,up,st,lk,cv,bits,chunks,pin,pi,sis,mb_bits_2_v) then 
   assoc(directory(root),tn,index_name,sis). 
   
   
   
   
   
   
   
   *** [4] Adding rows. 
     
   
      *** [4.2] Adding a set of rows.
   
define Result(DB2Error,One)
   add_rows
     (
       String                     directory, 
       String                     table_name, 
       MVar(Chunk($Row))          chunks_mv, 
       (Int32,$Row) -> Int32      primary_hash,
       List($Row)                 rows, 
       Int32                      bits, 
       $HRow -> $Row              update, 
       Var(Int32)                 last_used, 
       Var(Int32)                 number_of_rows, 
       Var(TableSynState)         changed_v
     ) =
   if rows is
     {
       [ ] then ok(unique),
       [row1 . other_rows] then 
         with hash = primary_hash(bits,row1), 
         if get_loaded_chunk(directory,table_name,bits,hash,chunks_mv,update) is 
           {
             error(msg) then error(msg), 
             ok(c) then 
               protect
                 (
                   if c is lchunk(lu_v,ch_v,tr_v,rows_v) then 
                   lu_v <- now;
                   ch_v <- changed; 
                   rows_v <- [row1 . *rows_v];
                   number_of_rows <- *number_of_rows + 1
                 );
             add_rows(directory,
                      table_name, 
                      chunks_mv, 
                      primary_hash, 
                      other_rows,
                      bits, 
                      update, 
                      last_used,
                      number_of_rows,
                      changed_v)
           }
     }.
   
   
   
   
   
   
      *** [4.3] The public tool 'add_rows'. 
   
public define Result(DB2Error,One)
   add_rows
     (
       DB2Table($Row,$HRow)  the_table,
       List($Row)                       new_rows
     ) =
   if get_loaded_table(the_table) is 
     {
       error(msg) then error(msg), 
       ok(tbl) then 
         if tbl is ltable(root,tn,acs,lu,nor,up,st,lk,cv,bits,chunks,pin,pi,sis,mb_bits_2_v) then
         add_rows(directory(root),tn,chunks,pi,new_rows,bits,up,lu,nor,cv)
     }.
   

   
   
   
      *** [4.4] The public tool 'add_row'. 
   
public define Result(DB2Error,One)
   add_row
     (
       DB2Table($Row,$HRow)     the_table,
       $Row                     new_row
     ) =
   add_rows(the_table,[new_row]). 
   

   
   
   
   
   
   
   *** [5] Row selection. 

   Rows  in a  table  may be  selected  (regardless of  the type  of  action) via  several
   different methods.
   
public type DB2Select($Row):  // an opaque type
   cond($Row -> Bool     which),                 // by condition 
   prim(ByteArray        serialized_model),      // by primary index
   secd(String           secondary_index_name,   // by secondary index
        ByteArray        serialized_model). 
   
   
   Interface constructors for this opaque type. 
   
public define DB2Select($Row)
   condition
     (
       $Row -> Bool     which
     ) =
   cond(which). 

   
   Of  course,  the  types $Primary  and  $Secondary  must  disappear from  the  selection
   method. This is why we serialize the given model. 
   
public define DB2Select($Row)
   primary
     (
       $Primary     model
     ) =
   prim(serialize(model)). 

   
public define DB2Select($Row)
   secondary
     (
       String           index_name,
       $Secondary       model
     ) =
   secd(index_name,serialize(model)). 
   
   
   

   
   
   *** [6] Acting on rows. 
   
   We need to  be able to act  in several different ways on  a set of rows,  selected by a
   DB2Select($Row) datum. Possible actions are:
   
      - getting rows, 
      - updating rows, 
      - deleting rows. 

   
   The type below records what can happen to a row after the action is performed:
   
type NewRow($Row):
   deleted,                     // the row has been deleted
   unchanged,                   // the row did not change
   changed($Row new_row).       // the value of the row has been changed, 
                                //   and here is the new value
   
   
   The function which acts on a row has type:
   
                              $Row -> (NewRow($Row),Maybe($Result))
   
   regardless of the sort  of action performed.  It returns eventually a  new row (this is
   considered as a change of value).

   When  a change of  value is  performed, we  must ask  for delayed  synchronisation with
   disk. This is performed by:
   
define One
   ask_for_delayed_synchronisation // defined below in this file
     (
       LoadedTable($Row,$HRow)     the_table
     ). 
   
define One
   ask_for_delayed_synchronisation // defined below in this file
     (
       LoadedChunk($Row)           the_chunk
     ). 
   
   This function  starts a virtual machine  for delayed synchronisation, except  if one is
   already started.
   
   
   
   
   
      *** [6.1] Acting on selected rows of a chunk. 

   We get the list of  rows of the chunk, and we act on each  row by induction on the list
   of rows. We return 3 things:
   
      - the new list of rows of the chunk,
      - the list of results
      - a flag saying if some row has changed
   
   Note: this function  is deterministic. The actual action of chunk  data is performed by
   the next function.
   
   
define (List($Row),             // new rows of chunk
        List($Result),          // results
        Bool)                   // 'true' if some row has changed in the chunk
   act_on_chunk_rows
     (
       List($Row)                              rows,   // old rows of chunk
       $Row -> (NewRow($Row),Maybe($Result))   act
     ) = 
   if rows is 
     {
       [ ] then ([ ],[ ],false), 
       [row1 . others] then
          if act_on_chunk_rows(others,act) is 
               (other_new_rows,other_results,other_changed) then          
          if act(row1) is (new_row,mb_result) then 
            (
              if new_row is
                {
                  deleted            then other_new_rows,
                  unchanged          then [row1 . other_new_rows]
                  changed(new_value) then [new_value . other_new_rows]
                },
              if mb_result is 
                {
                  failure            then other_results,
                  success(result)    then [result . other_results]
                },
              if new_row is 
                {
                  deleted            then true,
                  unchanged          then other_changed,
                  changed(_)         then true
                }
            )
     }. 
      

   
   
      *** [6.2] Waiting for the end of chunk synchronisation. 
   
   The  next 'waiting'  function  is used  to  forbid operation  on a  chunk  while it  is
   synchronising.
   
define One
   wait_for_end_of_synchronisation
     (
       Var(ChunkSynState)      st_v
     ) =
   if *st_v is 
     {
       unchanged     then unique, 
       changed       then unique, 
       synchronising then 
         checking every 1 millisecond, 
         wait for *st_v /= synchronising then 
         unique   
     }.
   
   
   
   
      *** [6.3] Acting on a chunk. 
   
   This is the interface to the previous function. We are given a chunk and an action. The
   chunk is updated.
   
define List($Result)   
   act_on_chunk
     (
       LoadedTable($Row,$HRow)                   the_table,
       LoadedChunk($Row)                         c,
       $Row -> (NewRow($Row),Maybe($Result))     act
     ) =
   protect
   if c is lchunk(lu_v,st_v,tr_v,rows_v) then 
   wait_for_end_of_synchronisation(st_v); 
   if act_on_chunk_rows(*rows_v,act) is (new_rows,result,ch) then 
   rows_v <- new_rows; 
   lu_v <- now; 
   (if ch then st_v <- changed else unique); 
   result.    
   

   
   
   
   
      *** [6.4] Acting by condition. 
   
   We want to act on  all rows of a table (actually we apply 'act'  to all rows, but 'act'
   may not select some rows). We have to work on all chunks. Hence, the function is a loop
   based  on the  value of  the hash.  More  precisely, the  function acts  on all  chunks
   starting at some given hash value.
   
   The  function returns  a list  of results.   Each  result is  either an  error of  type
   'DB2Error' or a result of type '$Result' which depends on the kind of action performed.
   
   
define List(Result(DB2Error,$Result))
   act_by_condition
     (
       LoadedTable($Row,$HRow)               the_table, 
       DB2Root                               root, 
       String                                table_name, 
       $HRow -> $Row                         update, 
       ($Row,$Row) -> Bool                   compare, 
       Int32                                 bits, 
       Int32                                 hash,   // first primary hash to consider
       MVar(Chunk($Row))                     chunks_mv,
       ($Row,($Row,$Row) -> Bool) -> (NewRow($Row),Maybe($Result))    act
     ) =
   if hash >= (1<<bits)  // no hash value to consider
   then [] else
   //
   // work on first chunk
   //
   with result1 = (List(Result(DB2Error,$Result)))
   if get_loaded_chunk(directory(root),table_name,bits,hash,chunks_mv,update) is 
     {
       error(msg)        then [error(msg)], // was not able to get the chunk
       ok(loaded_chunk)  then 
         map(ok,act_on_chunk(the_table,loaded_chunk,
             ($Row row) |-> act(row,compare)))
     }, 
   //
   // work on other chunks
   //
   with other_results = (List(Result(DB2Error,$Result)))
   act_by_condition(the_table, 
                    root,
                    table_name, 
                    update, 
                    compare, 
                    bits,
                    hash+1,
                    chunks_mv, 
                    act), 
   //
   // gather the results
   //
   result1 + other_results. 
   
   
   
   
   
      *** [6.5] Acting by primary index. 
   
   We are given  the serialization 'serialized_model' of the primary  datum to be searched
   for. From this serialization and the number of bits of hash, we compute the hash of the
   unique chunk to be searched for. We get this chunk, and we act on it. 
   
define List(Result(DB2Error,$Result)) 
   act_by_primary_index
     (
       LoadedTable($Row,$HRow)                                        the_table, 
       DB2Root                                                        root, 
       String                                                         table_name, 
       $HRow -> $Row                                                  update, 
       ($Row,$Row) -> Bool                                            compare, 
       Int32                                                          bits, 
       MVar(Chunk($Row))                                              chunks_mv,
       Int32                                                          hash,
       ($Row,($Row,$Row) -> Bool) -> (NewRow($Row),Maybe($Result))    act
     ) =
   if get_loaded_chunk(directory(root),table_name,bits,hash,chunks_mv,update) is 
     {
       error(msg) then [error(msg)], 
       ok(loaded_chunk) then 
         map(ok,act_on_chunk(the_table, 
                             loaded_chunk,
                             ($Row row) |-> act(row,compare)))
     }.
   

   
   
   
   
      *** [6.6] Acting by secondary index. 
   
   We are again  given a serialization of a  secondary datum to be searched  for. We first
   hash this datum so  as to get a secondary hash 's_hash'. We are  also given the name of
   an index,  so that we can  load this index and  find the list  '[h1,h2,...]' of primary
   hashes corresponding  to 's_hash'.   Then we  act on all  the corresponding  chunks and
   gather the results.
   
define List(Result(DB2Error,$Result)) 
   act_by_secondary_index
     (
       LoadedTable($Row,$HRow)                                       the_table, 
       DB2Root                                                       root, 
       String                                                        table_name, 
       $HRow -> $Row                                                 update, 
       ($Row,$Row) -> Bool                                           compare, 
       Int32                                                         bits, 
       MVar(Chunk($Row))                                             chunks_mv,
       ByteArray                                                     serialized_model,
       String                                                        index_name,
       ($Row,($Row,$Row) -> Bool) -> (NewRow($Row),Maybe($Result))   act
     ) =
   with s_hash = my_hash(bits,serialized_model), 
   if get_loaded_index(the_table,index_name) is 
     {
       error(msg) then [error(msg)], 
       ok(loaded_index) then 
         if loaded_index is lindex(_,hash_row,values) then 
         with primary_hashes = *values(s_hash), 
         flat(map(
           (Int32 ph) |-> 
             act_by_primary_index(the_table, 
                                  root,
                                  table_name,
                                  update,
                                  compare,
                                  bits,
                                  chunks_mv,
                                  ph,
                                  act),
           primary_hashes))
     }. 
   
   
   
   
   
      *** [6.7] Waiting for the end of table synchronisation. 
   
   The  next 'waiting'  function is  used to  forbid  operations on  a table  while it  is
   synchronising.
   
define One
   wait_for_end_of_synchronisation
     (
       Var(TableSynState)   changed_v   // synchronisation state of table
     ) =
   if *changed_v is 
     {
       unchanged      then unique, 
       changed        then unique, 
       synchronising  then 
         checking every 1 millisecond, 
         wait for *changed_v /= synchronising then 
         unique
     }.
   
   
   
   
   
      *** [6.8] Acting in general. 
   
   Now we define the general function 'act_on_rows' which calls one of the above depending
   on the selection method.
  
define List(Result(DB2Error,$Result))
   act_on_rows
     (
       DB2Table($Row,$HRow)                                        the_table, 
       DB2Select($Row)                                             selection_method,
       ($Row,($Row,$Row) -> Bool) -> (NewRow($Row),Maybe($Result)) act          
     ) =
   if get_loaded_table(the_table) is 
     {
       error(msg) then [error(msg)], 
       ok(loaded_table) then if loaded_table is 
         ltable(root,tn,acs,lu,nor,up,st,lk,cv,bits,chunks_mv,pin,pi,sis,mb_bits_2_v) then 
         wait_for_end_of_synchronisation(cv); 
         if selection_method is 
           {
             cond(which) then
               act_by_condition(loaded_table,root,tn,up,lk,bits,
                                0,  // start with hash = 0
                                chunks_mv,
                                act),
   
             prim(serialized_model) then
               act_by_primary_index(loaded_table,root,tn,up,lk,bits,chunks_mv,
                                    my_hash(bits,serialized_model),
                                    act), 
   
             secd(secondary_index_name,serialized_model) then
               act_by_secondary_index(loaded_table,root,tn,up,lk,bits,chunks_mv,
                                      serialized_model,
                                      secondary_index_name,
                                      act)
           }
     }. 
   
   
   
   
   
   
   
   
   
   
   
   *** [7] Utilization commands. 
   
   
      *** [7.1] 'get_rows'. 
   
public define List(Result(DB2Error,$Row))
   get_rows
     (
       DB2Table($Row,$HRow)    the_table, 
       DB2Select($Row)         selection_method
     ) =
   act_on_rows(the_table,
               selection_method,
     ($Row                   row,
      ($Row,$Row) -> Bool    compare) |-> 
        (unchanged,            // don't modify the row
         success(row))).       // return the row
         
       
   
   
      *** [7.2] 'update_rows'. 
   
public define List(Result(DB2Error,DB2UpdateResult($Row)))
   update_rows
     (
       DB2Table($Row,$HRow)       the_table, 
       DB2Select($Row)            selection_method,
       $Row -> Maybe($Row)        how_to_update
     ) = 
   act_on_rows(the_table,
               selection_method,
     ($Row                 row,
      ($Row,$Row) -> Bool  compare) |-> 
       if how_to_update(row) is 
         {
           failure then // dont modify this row
             (unchanged,
              success(not_updated(row))),
   
           success(new_row) then 
             if compare(row,new_row)
             then (changed(new_row),
                   success(updated(new_row)))       // locked data not modified
             else (unchanged,
                   success(locked(row,new_row)))    // locked data would be modified
         }). 
   
   
   
   
   
      *** [7.3] 'delete_rows'. 

public define List(Result(DB2Error,$Row))
   delete_rows
     (
       DB2Table($Row,$HRow)   the_table, 
       DB2Select($Row)        selection_method,     
     ) =
   act_on_rows(the_table,
               selection_method,
     ($Row                  row, 
      ($Row,$Row) -> Bool   compare) |-> 
        (deleted,
         success(row))). 
   
   
   

   
   
   
   
   
   *** [8] Synchronising memory with disk. 

   A table has 3 possible states with respect to synchronisation:
   
     - unchanged
     - changed
     - synchronising
   
   When the table is loaded from disk,  it starts in the state 'unchanged'. When something
   changes in the table, the state becomes 'changed', and a virtual machine is started for
   synchronisation. This virtual machine begins  by sleeping during the given delay. After
   this delay,  the state  of the table  becomes 'synchronising', and  the synchronisation
   begins.  When synchronisation is done the state becomes 'unchanged' again. When a table
   is synchronising, no operation may be performed on this table.
   
   
   
      *** [8.1] Synchronising a table file. 
   
   Getting the list of all entries from a multiple variable. 
   
define List($T)
   to_list
     (
       MVar($T)    mv,
       Int32       n,
       List($T)    so_far
     ) =
   if n < 0 then so_far else
   with m = n-1, 
   to_list(mv,m,[*mv(m) . so_far]). 
       
   
   
define One
   synchronise_table_file
     (
       DB2Root                  root, 
       String                   table_name, 
       Int32                    number_of_rows,
       Int32                    bits,
       String                   primary_index_name, 
       (Int32,$Row) -> Int32    primary_hash,
       List(LoadedIndex($Row))  sis, 
       Maybe(Int32)             mb_bits_2
     ) =
   if root is dbroot(dir,delay,sd_v,warn) then 
   with path = dir+"/t_"+table_name, 
   if (SaveResult)
     save
       (
         table(number_of_rows,
               bits,
               primary_index_name,
               map((LoadedIndex($Row) i) |-> 
                 if i is lindex(n,hr,vals) then 
                   v1(n,to_list(vals,1<<bits,[])),
                   sis), 
               mb_bits_2),
         path
       ) 
     is 
       {
         cannot_open_file   then warn(cannot_open_file(path)),
         write_error        then warn(cannot_write_file(path)),
         ok                 then unique
       }.
   
   
   
   
      *** [8.2] Synchronising chunk files. 
      
         *** [8.2.1] One chunk. 
   
   Synchronising a single chunk file. 
   
define One
   synchronise_chunk_file
     (
       DB2Root              root, 
       String               table_name, 
       $Row -> $HRow        store, 
       Int32                bits, 
       Int32                hash, 
       Chunk($Row)          c
     ) =
   if c is 
     {
       not_loaded then unique,    // nothing to synchronise
       loaded(loaded_chunk) then 
         if root is dbroot(dir,_,_,warn) then 
         with path = dir+"/c_"+bits+"_"+hash+"_"+table_name, 
         if loaded_chunk is lchunk(lu_v,ch_v,tr_v,rows_v) then 
         with file_content = (ChunkFile($HRow))chunk(map(store,*rows_v)),
         if (SaveResult)save(file_content,path) is 
           {
             cannot_open_file    then warn(cannot_open_file(path)),
             write_error         then warn(cannot_write_file(path)),
             ok                  then unique
           }
     }. 
   
   
   
         *** [8.2.2] One 'new' chunks (moving table).
   
   The table is currently moving. Hence, we  have an old (current) number of bits of hash:
   'bits', and a new  number of bits of hash: 'new_bits'. One of  these two numbers is the
   successor of the other one. The table is either:
   
     'increasing': new_bits = bits+1    and two new chunk files for one old chunk file
     'decreasing': new_bits = bits-1    and one new chunk file for two old chunk files
   
   
            *** [8.2.2.1] 'Increasing' case.
   
   We have an (old) chunk which must be  saved into two separate new chunk files. For each
   row of  the chunk, we  must compute and  hash the primary data  with the new  number of
   bits. We always  get either 'new_hash_1' or 'new_hash_2', which are  the hashes for the
   two files. Hence, the list of rows of the chunk must be separated into two lists:
   
define (List($Row),List($Row))
   split_chunk
     (
       List($Row)                rows,
       Int32                     new_bits, 
       Int32                     new_hash_1,
       (Int32,$Row) -> Int32     primary_hash
     ) =
   if rows is 
     {
       [ ] then ([ ],[ ]), 
       [row1 . others] then 
         if split_chunk(others,new_bits,new_hash_1,primary_hash) is (others_1,others_2) then 
         if primary_hash(new_bits,row1) = new_hash_1
         then ([row1 . others_1],others_2) 
         else (others_1,[row1 . others_2])
     }.
   
define One
   synchronise_increasing_chunk
     (
       DB2Root                  root,
       String                   table_name,
       $Row -> $HRow            store,
       Int32                    old_bits,
       Int32                    new_bits,
       Int32                    old_hash,
       Int32                    new_hash_1,
       Int32                    new_hash_2,
       Chunk($Row)              old_chunk,
       (Int32,$Row) -> Int32    primary_hash
     ) =
   if old_chunk is 
     {
       not_loaded then unique, 
       loaded(loaded_chunk) then 
         if loaded_chunk is lchunk(lu_v,ch_v,tr_v,rows_v) then 
         if split_chunk(*rows_v,new_bits,new_hash_1,primary_hash) is (rows_1,rows_2) then 
         if root is dbroot(dir,_,_,warn) then 
         with path_1 = dir+"/c_"+new_bits+"_"+new_hash_1+"_"+table_name, 
              path_2 = dir+"/c_"+new_bits+"_"+new_hash_2+"_"+table_name, 
         if (SaveResult)save(chunk(map(store,rows_1)),path_1) is 
           {
             cannot_open_file   then warn(cannot_open_file(path_1)),
             write_error        then warn(cannot_write_file(path_1)), 
             ok                 then unique
           };
         if (SaveResult)save(chunk(map(store,rows_2)),path_2) is 
           {
             cannot_open_file   then warn(cannot_open_file(path_2)),
             write_error        then warn(cannot_write_file(path_2)), 
             ok                 then unique
           }
     }.

   
            *** [8.2.2.2] 'Decreasing' case.

   
define One
   synchronise_decreasing_chunk
     (
       DB2Root                  root,
       String                   table_name, 
       $Row -> $HRow            store,
       Int32                    old_bits,
       Int32                    new_bits, 
       Int32                    new_hash,
       Int32                    old_hash_1,
       Int32                    old_hash_2,
       LoadedChunk($Row)        old_chunk_1,
       LoadedChunk($Row)        old_chunk_2,
       (Int32,$Row) -> Int32    primary_hash
     ) =
   if old_chunk_1 is lchunk(lu1_v,ch1_v,tr1_v,rows1_v) then 
   if old_chunk_2 is lchunk(lu2_v,ch2_v,tr2_v,rows2_v) then 
   with new_rows = *rows1_v + *rows2_v, 
   if root is dbroot(dir,_,_,warn) then 
   with path = dir+"/c_"+new_bits+"_"+new_hash+"_"+table_name,
   if (SaveResult)save(chunk(map(store,new_rows)),path) is
     {
       cannot_open_file   then warn(cannot_open_file(path)), 
       write_error        then warn(cannot_write_file(path)), 
       ok                 then unique
     }.
   
   
   
define One
   synchronise_decreasing_chunk
     (
       DB2Root                  root,
       String                   table_name,
       $HRow -> $Row            update, 
       $Row -> $HRow            store, 
       Int32                    old_bits, 
       Int32                    new_bits,
       Int32                    new_hash, 
       Int32                    old_hash_1,
       Int32                    old_hash_2,
       Chunk($Row)              old_chunk_1,
       Chunk($Row)              old_chunk_2,
       (Int32,$Row) -> Int32    primary_hash,
       MVar(Chunk($Row))        chunks_mv
     ) =
   if old_chunk_1 is 
     {
       not_loaded then if old_chunk_2 is 
        {
          not_loaded then unique, 
          loaded(loaded_old_chunk_2) then 
            if load_chunk(directory(root),table_name,old_bits,old_hash_1,chunks_mv,update) is 
              {
                error(msg) then warn(root)(msg), 
                ok(loaded_old_chunk_1) then 
                  synchronise_decreasing_chunk(root,table_name, 
                                               store,old_bits,new_bits, 
                                               new_hash,
                                               old_hash_1,old_hash_2,
                                               loaded_old_chunk_1,loaded_old_chunk_2,
                                               primary_hash)
              }
        },
       loaded(loaded_old_chunk_1) then if old_chunk_2 is 
        {
          not_loaded then
            if load_chunk(directory(root),table_name,old_bits,old_hash_2,chunks_mv,update) is 
              {
                error(msg) then warn(root)(msg), 
                ok(loaded_old_chunk_2) then 
                  synchronise_decreasing_chunk(root,table_name, 
                                               store,old_bits,new_bits, 
                                               new_hash,
                                               old_hash_1,old_hash_2,
                                               loaded_old_chunk_1,loaded_old_chunk_2,
                                               primary_hash)
              },
          loaded(loaded_old_chunk_2) then 
            synchronise_decreasing_chunk(root,table_name, 
                                         store,old_bits,new_bits, 
                                         new_hash,
                                         old_hash_1,old_hash_2,
                                         loaded_old_chunk_1,loaded_old_chunk_2,
                                         primary_hash)
        }
     }.
   
    
   
            *** [8.2.2.3] Both cases.
   
define One
   synchronise_new_chunk_file
     (
       DB2Root               root, 
       String                table_name, 
       $HRow -> $Row         update,
       $Row -> $HRow         store,
       Int32                 bits,
       Int32                 new_bits,
       Int32                 old_hash, 
       MVar(Chunk($Row))     chunks_mv,
       (Int32,$Row) -> Int32 primary_hash
     ) =
   if new_bits > bits 
   
   ///////////////////////////////////////////////////////////
   // increasing:      old_hash =  0110
   //                new_hash_1 = 00110 (= old_hash)
   //                new_hash_2 = 10110
   //
   then with new_hash_1 = (Int32)old_hash, 
             new_hash_2 = (Int32)(old_hash | (1<<bits)), 
        synchronise_increasing_chunk(root,
                                     table_name,
                                     store,
                                     bits,
                                     new_bits,
                                     old_hash,
                                     new_hash_1,
                                     new_hash_2,
                                     *chunks_mv(old_hash),
                                     primary_hash)
   
   ////////////////////////////////////////////////////////////
   // decreasing:       old_hash =  ?110
   //                   new_hash =   110
   //                 old_hash_1 =  0110 (= old_hash)
   //                 old_hash_2 =  1110
   //
   else with   new_hash = old_hash & ((1<<new_bits) - 1), 
             old_hash_1 = (Int32)(new_hash), 
             old_hash_2 = (Int32)(new_hash | (1<<new_bits)),
        synchronise_decreasing_chunk(root,
                                     table_name,
                                     update, 
                                     store,
                                     bits, 
                                     new_bits,
                                     new_hash, 
                                     old_hash_1,
                                     old_hash_2,
                                     *chunks_mv(old_hash_1),
                                     *chunks_mv(old_hash_2),
                                     primary_hash,
                                     chunks_mv). 
       
   
   
   
         *** [8.2.3] All chunks. 
   
define One    
   synchronise_chunk_files
     (
       DB2Root                  root, 
       String                   table_name, 
       $HRow -> $Row            update, 
       $Row -> $HRow            store, 
       Int32                    bits, 
       Int32                    i, // hash of first chunk to be synchronised
       MVar(Chunk($Row))        chunks_mv,
       Maybe(Int32)             mb_bits_2,
       (Int32,$Row) -> Int32    primary_hash
     ) =
   if i >= (1<<bits) then unique else
   synchronise_chunk_file(root,
                          table_name,
                          store,
                          bits,
                          i, 
                          *chunks_mv(i));
   if mb_bits_2 is 
     {
       failure then unique, 
       success(new_bits) then 
         synchronise_new_chunk_file(root,
                                    table_name, 
                                    update, 
                                    store,
                                    bits,
                                    new_bits,
                                    i, 
                                    chunks_mv,
                                    primary_hash)
     };
   synchronise_chunk_files(root,
                           table_name, 
                           update, 
                           store,
                           bits,
                           i+1,
                           chunks_mv,
                           mb_bits_2,
                           primary_hash). 
                                        
                          
   
   
   
      *** [8.4] Synchronising everything. 
   
define One
   do_synchronise
     (
       LoadedTable($Row,$HRow)    the_table,
     ) =
   if the_table is 
     ltable(root,tn,acs,lu,nor,up,st,lk,cv,bits,chunks_mv,pin,pi,sis,mb_bits_2_v) then
   cv <- synchronising;   // may begin to synchronise
     synchronise_table_file(root,tn,*nor,bits,pin,pi,sis,*mb_bits_2_v);
     synchronise_chunk_files(root,tn,up,st,bits,0,chunks_mv,*mb_bits_2_v,pi); 
   cv <- unchanged.        // synchronisation completed
   
   
   
      *** [8.5] Asking for delayed synchronisation.

   If  an  operation  performs  a  modification  in  a table,  it  must  ask  for  delayed
   synchronisation of memory with disk. The function below is the tool for that purpose.
   
define One
   ask_for_delayed_synchronisation
     (
       LoadedTable($Row,$HRow)     the_table,
     ) =
   if the_table is 
     ltable(root,tn,acs,lu,nor,up,st,lk,cv,bits,chunks_mv,pin,pi,sis,mb_bits_2_v) then
   if *cv is 
     {
       unchanged then 
         cv <- changed; 
         delegate
           (
             sleep(delay(root)*1000);    // 'delay' in seconds, 'sleep' in milliseconds
             do_synchronise(the_table)
           ), 
         unique, 
   
       changed then unique, 
   
       synchronising then 
         checking every 1 millisecond,
         wait for *cv /= synchronising then 
         unique
     }. 
   
   
   
   
   
   *** [9] Changing the number of bits of hash. 

   
   
      *** [9.1] Hashing. 
   
   Tables are created  with 0 bits of  hash. Since the number of  chunks is 2^bits_of_hash
   (equal to 2^0 = 1 in this case), such  tables have only one chunk. When the size of the
   tables increases it is necessary to divide it into more chunks. To that end we increase
   the number of bits of hash, and we reorganize the table into a new set of chunks. 
   
       bits of hash                  number of chunks
      ----------------------------------------------------
       0                             1
       1                             2
       2                             4
       3                             8
       4                             16
       etc...

   The hash is computed by the function:
   
define Int32
   my_hash
     (
       Int32    bits, 
       $T       datum
     ) =
   simple_hash(32,datum) & ((1<<bits) - 1). 
   
   The  advantage  of this  function  over  'simple_hash' is  that  it  has the  following
   property:
   
                        my_hash(n+1,d) & ((1<<n) - 1)  =  my_hash(n,d)
   
   In other words, when the number of bits  of hash is changed, the bits of the hash which
   are  common  are  the  same  ones.   For  example,  if  my_hash(4,d)  is  '0110',  then
   'my_hash(5,d)' can be either '00110' or '10110'. 
   
   This means that when we need to increase the  number of bits of hash by 1, we just need
   to split  each chunk into two  chunks. Conversely, when the  number of bits  of hash is
   decreased by 1, we just have to join chunks two by two. 
   
   
   
      *** [9.2] Deciding to change the number of bits of hash. 
   
   Each  table computes  from  time to  time,  the average  size of  its  chunks (just  by
   averaging  the sizes  of the  chunk files).   There is  also in  each table  a declared
   average size of chunks. When the computed  average size of chunks becomes more than the
   double of  the declared  average size of  chunks, the  number of bits  of hash  must be
   increased by 1. Conversely, when the  computed average size of chunks becomes less than
   half the  declared size  of chunks, the  number of  bits of hash  must be  decreased by
   1. Notice that this  link between the actual  average size of chunks and  the number of
   bits of hash has  enough hysteresis, so that modifying the number  of bits of hash will
   not happen too often.
   
   
type ChangeBits:
   no_need_to_change, 
   increase,
   decrease. 
   
define ChangeBits
   needs_to_change_bits_of_hash
     (
       LoadedTable($Row,$HRow)     the_table
     ) =
   if the_table is 
     ltable(root,tn,acs,lu,nor,up,st,lk,cv,bits,chunks,pin,pi,sis,mb_bits_2_v) then 
   if root is dbroot(dir,delay,sd_v,warn) then 
   with    fileinfos = directory_full_list(dir,"c_"+bits+"_*_"+tn,"",""), 
        average_size = average(map((FileDescription d) |-> 
                           if d is 
                             {
                               no_info(_)        then 0, 
                               file(_,s,_,_)     then s, 
                               link(_,_,_,_)     then 0, 
                               directory(_,_,_)  then 0
                             },fileinfos)),
      if 2*average_size < acs
      then decrease
      else if 2*acs < average_size
           then increase
           else no_need_to_change. 
   
   

   
   
      *** [9.3] Performing a change. 
   
   When it has been decided to change the  number of bits of hash, we need to perform this
   transformation without disturbing the normal utilisation of the table. 
   
   The first  thing to do  is to change the  value of the  last field in the  loaded table
   'mb_bits_of_hash_2_v' from  'failure to  'success(n)', where 'n'  is the new  number of
   bits of hash. From now on, the table is called a 'moving table'.
   
define One
   begin_move_table
     (
       LoadedTable($Row,$HRow)  the_table,
       Int32                    new_bits
     ) =
   if the_table is 
     ltable(root,tn,acs,lu,nor,up,st,lk,cv,bits,chunks,pin,pi,sis,mb_bits_2_v) then 
   mb_bits_2_v <- success(new_bits). 
   
   
   Now,  rows  will be  present  in old  chunk  files  and in  new  chunk  files. If  some
   modification is performed,  the synchronisation must update old and  new chunk files at
   the same time. This is what it does actually (see above).