From - Sun Oct 05 20:45:19 1997 Return-Path: Received: from punt-2.mail.demon.net by mailstore for rleyton@dogbert.demon.co.uk id 876047869:06:00768:6; Sun, 05 Oct 97 11:37:49 BST Received: from mail.acm.org ([199.222.69.4]) by punt-2.mail.demon.net id aa1522131; 5 Oct 97 11:37 BST Received: from brookes.ac.uk (csmail.brookes.ac.uk [161.73.1.1]) by mail.acm.org (8.8.5/8.7.5) with ESMTP id GAA122454 for ; Sun, 5 Oct 1997 06:42:02 -0400 From: majordomo@brookes.ac.uk Received: by brookes.ac.uk (8.8.7/SMI-SVR4) id LAA22054; Sun, 5 Oct 1997 11:37:38 +0100 (BST) Date: Sun, 5 Oct 1997 11:37:38 +0100 (BST) Message-Id: <199710051037.LAA22054@brookes.ac.uk> To: rleyton@acm.org Subject: Majordomo file: list 'leap' file 'leap.9703' Reply-To: majordomo@brookes.ac.uk X-Mozilla-Status: 2001 -- >From leap-owner Sat Mar 1 17:10:29 1997 Received: by brookes.ac.uk (8.8.4/SMI-SVR4) id RAA00139; Sat, 1 Mar 1997 17:09:15 GMT Date: Sat, 1 Mar 1997 18:08:05 +0100 (MET) From: Richard Leyton Message-Id: <199703011708.SAA25760@orca.amsinc.com> Subject: leap list: Source code description Apparently-To: Sender: owner-leap@brookes.ac.uk Precedence: bulk Reply-To: leap@brookes.ac.uk Dear all, I have just finished this new addition to the LEAP documentation, and would like to give you a preview before 1.0 is released this month. It will be the file src/FILES in the 1.0 distribution. It goes over each of the source code modules in LEAP, and explains it's purpose in high level terms. The lower level, implementation specific items are in each source file, and are hopefully quite sufficent. Please let me know your comments on this file, if there is a need for more information, or for less, on any particular file. Regards, Richard. # This program is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation; either version 2 of the License, or # (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with this program; if not, write to the Free Software # Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. # # See the file COPYING for more information. # # Richard Leyton, c/o 3.Pelting Drove, Priddy, WELLS, # Somerset, BA5 3BA, England. E-Mail: rleyton@acm.org # and/or e0190404@brookes.ac.uk. http://www.brookes.ac.uk/~e0190404/leap.html Introduction ------------ This file contains a detailed description about each of the files in the standard LEAP source distribution. It is intended for developers who want to get an overview of the functionality of LEAP. It covers both the source file, and the header file. The files are in alphabetical order. main() is in leap.c, which contains the main loop. parser.c contains the main parser functions, which call the algebraic operators etc. in rtional.c attribs ------- attribs.c include/attribs.h This unit defines the operations necessary for dealing with an attribute. An attribute is a definition of a particular column in a relation. A tuple consists of an array of attribute pointers, and character pointers. In this manner, information about the attribute name, type, size etc. can easily be located. Attributes are found using a the findfirst/findnext functions, or the find operation. Attributes must be disposed of after creation, in order to release the memory used. There are macros to access the specific information held within the structure. consts ------ include/consts.h The constants used throughout LEAP are defined here, such as error numbers and token's. This is used throughout LEAP, and practically every source module uses this header file. database -------- database.c include/database.h This unit provides the data dictionary functionality. This unit will be expanded as LEAP supports more in the way of a data dictionary, but for now, when a database change is required, the change_db() function is called, which checks the specified database name against those defined in leapdata. Without a database name specified, the function simply lists the databases available. The other function that is available is get_keys(), which checks the local relation in each database which defines relationships between relations, and is used in the natural join operation. In subsequent versions of LEAP (starting with 1.1), the data dictionary functionality is made more accessible with a new function that allows simple selects/projects on a specific table, and handles the anticipated problems. This will open up the way for further functionality. dbase ----- dbase.c include/dbase.h DBase provides the operations necessary to creeate and destroy the master structure through which all database objects are accessed. The database contains pointers to the first and last relations in the list of relations within a database, the base directory of the database, and of course, the name of the database. The structure is in the dtypes.h file dtypes ------ include/dtypes.h The dtypes header file is very important, as it defines the majority of LEAP data structures. A reorganisation is under way to locate the definitions of data structures in the appropriate header file. This is the best file to look in for a detailed understanding of the internal structures used, and what the various fields are. globals ------- include/globals.h Global variables are all defined externally here. Most of the actual definitions which allocate the memory are made in util, or leap. hashing ------- hashing.c include/hashing.h The hashing functionality provides simply that, manipulation of the hash table. A hash key is calculated, and the value inserted into the appropriate position within the hash table. Each relation has a hash table associated with it, which, in the case of permanent relations, is also written to disk. Hash tables are conversly read off of the disk when the permanent relation is used. Earlier versions of LEAP would read the entire relation, and hash table at the outset, but this simple modification improves memory utilisation. In the case of a duplicate hash key being calculated, a chain node is created, and this is appended to the end of the chain appropriately. info ---- info.c include/info.h The info module provides various information pieces, such as the GNU Warranty/conditions of use, startup messages, and so forth. Not much of interest here. They are hardcoded simply to prevent the risk of somebody messing around with a source file and changing the message. leap ---- leap.c This is the main program of LEAP. main() performs the command line processing necessary, and calls initialisation routines that configure the system. The various startup/shutdown messages are displayed, before the main loop, do_leap() is called. do_leap() initialises the two database structures (master_db, and current_db), and contains the main loop through which commands are retrieved from the appropriate input file (normally this is stdin). Exiting from the main loop destroys the two databases, and then proceeds to close down and close files. parser ------ parser.c include/parser.h The parser module is at the heart of the LEAP system, and controls the way expressions are evaluated and algebraic operations are called. There are two main operations: process_query() and process_parse_tree(), which perform interrelated, but different operations. process_query() performs the main parsing process of breaking down an expression into an internal format that can then be used by process_parse_tree() It relies on the ordering of brackets to take values out of the entire expression, and breaks it down into seperate operations. All leaf nodes in an algebraic operation will therefore be relations. ie. project(a) (values) is not a branch node with two leafs, but a branch node with a left node. Each node should result in a relation being produced. This relation is passed back up the tree to the higher level operation. The root node result relation is therefore the result of the expression. It is process_parse_tree() that performs this operation. The parse tree is destroyed as it progresses through an expression, and there is a known bug in that memory is leaked by expressions not having there memory free'd if they contain an error and are not processed. The two other operations of note are new_parse_node() which creates the nodes at each point in the tree (note that there are no differences between leaf nodes and branch nodes, except in the contents). display_ptree() also displays the parse tree, and is used in tracing. p_stack ------- p_stack.c include/p_stack.h The p_stack module simply provides stack functionality for the parser routine. As an expression is processed, rather than recursing into the expression as the DOS version of LEAP originally did, the expression is pushed onto the stack. At some point in the future, this will be written to simply store an arbitrary pointer, and then it can be shared by other routines, with the value being appropriately typecase. relation -------- relation.c include/relation.h All routines necessary for the handling of relations are contained in this module. Relation creation, relation processing (to move through the list of relations pointed to from the database structure), disposal. A number of higher level operations provide operations to process a directory and read in the relations contained there. rtional ------- rtional.c include/rtional.h This unit provides the algebraic operators, ie. project, select, join, union, intersect, etc. and operates using the tuple unit to read tuples from relations, and perform the appropriate logic. For a detailed discussion of operation algorithms, consult a decent database book which discusses the relational algebra. Hashing is used in a many of the operations to ensure no duplicate tuples are inserted, which would violate the structural component of the relational model (this is something that many database vendors allow to be done, for various good reasons, but not here). Some support operations are also provided, namely creation of the result relation, which is the relation resulting from the operation. In many cases (such as union), the result is union-compatible with the argument relations. In others (project, join, product), it is not, ie. it differs in the type and size of the attribute definitions. Special operations are necessary which build this relation. tuples ------ tuples.c include/tuples.h The tuples unit reads the data contained within a relation from the disk, and builds and internal structure which is subsequently used principally by the rtional unit. The structure of a tuple is that of a fixed sized array with three components for each attribute. One is a pointer to the attribute structure that defines that particular attribute, the second is a fixed size character array used to store the data. Finally the third item is the relation from which the attribute was originated from (used in project, join and product, where two relations combine to form a new relation). Tuples are expensive in terms of memory used, principally because of the fixed size for data. This is something that will be addressed in subsequent versions of LEAP. However, a tuple can be reused, and the operations in the rtional unit give examples. In some situations a tuple is never reused, and can be destroyed immediately. An argument to the readfirst_tuple() function ensures that old tuples passed as parameters are reused, the same with readnext_tuple. This is a complex module, and you should consult the usage in the rtional unit for a better understanding of accessing and manipulating tuples. It will be tidied up somewhat in subsequent versions of LEAP, especially if caching is required, as the current approach does not lend itself to caching particularly well. util ---- util.c util.h Util contains a large number of operations for performing various miscellaneous items. For example, listing source files, opening input streams, displaying help pages, reporting errors, logging errors, processing strings. In addition, the definition of a number of global items is made here. vars ---- vars.c include/vars.h The vars unit simply provides variable operations. A variable is used as a key to a fixed size array (again, an inflexible approach, but simplest), to access a particular value. In addition, the 0.11 status settings are now combined within the variables, so system settings can now be set simply with variables. The main user of this module is the util operation, which provides the system setting functions that manipulate the global variables enabling/disabling system settings. >From leap-owner Fri Mar 7 17:27:35 1997 Received: by brookes.ac.uk (8.8.4/SMI-SVR4) id RAA28757; Fri, 7 Mar 1997 17:23:59 GMT Message-Id: <33203251.6FF8@acm.org> Date: Fri, 07 Mar 1997 16:20:49 +0100 From: Richard Leyton Organization: AMS Management Systems X-Mailer: Mozilla 3.01 (X11; I; HP-UX B.10.20 9000/889) Mime-Version: 1.0 To: leap@brookes.ac.uk Subject: leap list: Remaining bugs in 0.12? Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-leap@brookes.ac.uk Precedence: bulk Reply-To: leap@brookes.ac.uk Dear all, Are you aware of any remaining bugs in 0.12? I want to try and release version 1.0 sometime next week. Drop me an e-mail, Thanks, Richard. -- Richard Leyton, AMS Management Systems Deutschland GmbH mailto:rleyton@acm.org http://www.brookes.ac.uk/~e0190404/leap.html Opinions are my own, and not representative of AMS. >From leap-owner Thu Mar 27 16:40:44 1997 Received: by brookes.ac.uk (8.8.4/SMI-SVR4) id QAA17902; Thu, 27 Mar 1997 16:37:48 GMT Message-Id: <333AA1F6.5524@acm.org> Date: Thu, 27 Mar 1997 17:36:06 +0100 From: Richard Leyton Organization: AMS Management Systems X-Mailer: Mozilla 3.01 (X11; I; HP-UX B.10.20 9000/889) Mime-Version: 1.0 To: leap@brookes.ac.uk Cc: rleyton@acm.org Subject: leap list: Easter LEAP Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-leap@brookes.ac.uk Precedence: bulk Reply-To: leap@brookes.ac.uk Dear all, Firstly, sorry for the delay in releasing version 1.0 of LEAP. Work has had the better of me, and I took a long overdue trip back to Britain for a long weekend. Anyway, I very much hope to be in a position to release it next week if all goes according to plan. Anyway, that is not the reason for my e-mail. There are in fact two reasons. The first is that I have noticed that the acronym "LEAP" is used by a number of other establishments for all sorts of things. Go to http://www.altavista.digital.com and search on LEAP to see the number! You get other software, Quantum LEAP fan pages, Alabama Dog Sanctuaries, and some! In case you're curious, LEAP was based on an idea from Dr Stefan Stanczyk at Brookes University when I was putting the first release together (almost TWO years ago!!!) and we needed a catchy name. It was originally LAP - Leyton's Algebraic Processor. Images of puppies came to my mind, so I added the E (for extendible/extensible), and had LEAP. Anyway, I wanted to ask you if you have any ideas for a potential rename of LEAP. I'm only playing with the idea at this stage, but your ideas/objections/name suggestions are more than welcome. Secondly, this I want to wish you all a happy Easter weekend, and to thank you all for your feedback. As always I'm very grateful. Cheerio, Richard. -- Richard Leyton, AMS Management Systems Deutschland GmbH mailto:rleyton@acm.org http://www.brookes.ac.uk/~e0190404/leap.html Opinions are my own, and not representative of AMS.