Re: Looking for Indexed Sequential File Package

Re: Looking for Indexed Sequential File Package

[Matthew Heaney]

In article <33CCA95E.167EB0E7@avions.aerospatiale.fr>, Paul CHARDON
<paul.chardon@avions.aerospatiale.fr> wrote:

>        A friend of mine is lookink for a reusable Ada83 component to manage
>indexed sequential files. This package must give a quick access to a
>file of item (record). It could give access to those record sorted
>according to one or more keys (those keys are primary or secondary keys
>that are fields in the record).

Try this:

<http://www.cs.kuleuven.ac.be/~dirk/ada-belgium/software/>

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271

Looking for Indexed Sequential File Package

[Paul CHARDON]

Hello,

	I posted a few hours ago the same message in french, but it was a
mistake. I would like to send it to fr.comp.lang.ada, Sorry.
So, now, I'll ask you the same question in english :

	A friend of mine is lookink for a reusable Ada83 component to manage
indexed sequential files. This package must give a quick access to a
file of item (record). It could give access to those record sorted
according to one or more keys (those keys are primary or secondary keys
that are fields in the record).

	If you know where to find such a package, please email my friend
jean-michel.audoin@avions.aerospatiale.fr and I.

	Thanks in advance, Paul.

Re: Looking for Indexed Sequential File Package

[Larry Kilgallen]

In article <33CCA95E.167EB0E7@avions.aerospatiale.fr>, Paul CHARDON <paul.chardon@avions.aerospatiale.fr> writes:

> 	A friend of mine is lookink for a reusable Ada83 component to manage
> indexed sequential files. This package must give a quick access to a
> file of item (record). It could give access to those record sorted
> according to one or more keys (those keys are primary or secondary keys
> that are fields in the record).

If by "reusable" you mean portable to any Ada83 environment,
I do not believe it is possible to meet the "must give quick
access" requirement.  What must be done to achieve performance
goals varies quite a bit between operating systems.

You do not mention any reliability requirement, but if I were
in the market for such a thing I would likely be quite concerned
about ensuring that a write-through caching strategy was used.
Achieving that is beyond the control of the Ada environment,
and not going to be automatic if the operating systems involved
are Windows NT or Unix.

Larry Kilgallen

Re: Looking for Indexed Sequential File Package

[Robert Dewar]

Larry said

<<You do not mention any reliability requirement, but if I were
in the market for such a thing I would likely be quite concerned
about ensuring that a write-through caching strategy was used.
Achieving that is beyond the control of the Ada environment,
and not going to be automatic if the operating systems involved
are Windows NT or Unix.
>>


That's too simplistic. NT is a fully journaled file system. The exact
needs for integrity vary of course, but ensuring write through caching
is neither necessary nor sufficient for achieving file integrity in
any environment.

Generally a straightforward approach will work fine in practice over
a jornalled file system like the one in NT (some Unices but not all
also have reasonable file systems).

As for making a portable efficient indexed file access package. This is
perfectly possible (the package I did for Realia COBOL did not depend on
any OS specific features, and could be ported to other environments).

Re: Looking for Indexed Sequential File Package

[Michael F Brenner]

Indexed sequential files are not always called that anymore. An indexed
sequential file is a data structure with two components: an indexing
container which keeps a list of keys in sorted order, and a random
access container (falsely called sequential in the title Indexed Sequential).
For the indexing containter, a finite state machine lookup or hash function
may be used, or else you may use a partially balanced or fully balanced
tree, etc. For the random file, you may use an ordinary Ada Stream (unless
you are using the DOS version 3.07), or a large fixed array in virtual
memory, or a direct_IO file. An indexed_sequential_control package would
then simply combine these two containers and provide an interface 
like text_IO, except that the set_position would work, and there would
be insert_key, delete_key, get_position_from_key, get_key_from_position,
get_key_from_record, set_key_in_record, and of course, something like
set_index and get_index would have to work on the file.

Re: Looking for Indexed Sequential File Package

[Larry Kilgallen]

In article <5qlskj$3ka@top.mitre.org>, mfb@mbunix.mitre.org (Michael F Brenner) writes:
> Indexed sequential files are not always called that anymore. An indexed
> sequential file is a data structure with two components: an indexing
> container which keeps a list of keys in sorted order, and a random
> access container (falsely called sequential in the title Indexed Sequential).

I have always taken the "Sequential" part of the name to describe
the property that once a particular index has been selected and a
particular record fetched via that index it is possible to fetch
subsequent "sequential" records in the order of that index.

> For the indexing containter, a finite state machine lookup or hash function
> may be used, or else you may use a partially balanced or fully balanced
> tree, etc. For the random file, you may use an ordinary Ada Stream (unless
> you are using the DOS version 3.07), or a large fixed array in virtual
> memory, or a direct_IO file. An indexed_sequential_control package would
> then simply combine these two containers and provide an interface 
> like text_IO, except that the set_position would work, and there would
> be insert_key, delete_key, get_position_from_key, get_key_from_position,
> get_key_from_record, set_key_in_record, and of course, something like
> set_index and get_index would have to work on the file.

I don't see that capability in your list of primitive operations,
so I suppose the implementation you propose might not offer that
capability, in which case what you propose is not an indexed
_sequential_ package, but that does not mean that what the user
_wanted_ was not an indexed _sequential_ package.

I suppose another reading of the term is that "sequential" refers to the
underlying implementation, which is not a useful thing for a client
to mandate.

Your proposed implementation tying together two relatively high-level
seems to possibly not to provide atomic updates across machine
crashes, and even though our operating systems are all written in
perfect Ada, some of the hardware is imperfect.

Particularly the hardware at my local power company, but that is a
separate speech.

Larry Kilgallen

Re: Looking for Indexed Sequential File Package

[Robert Dewar]

Michael says

<<> Indexed sequential files are not always called that anymore. An indexed
> sequential file is a data structure with two components: an indexing
> container which keeps a list of keys in sorted order, and a random
> access container (falsely called sequential in the title Indexed Sequential).
>>


An indexed sequential file is one which is organized so that sequential
acesses are very rapid once an index location has been looked up. Typically
you can access sequentially on the basis of more than one index. So this
means that hash schemes are totally useless for example.

The structures used for these files on modern operating systems are
extremely sophisticated, involving interaction with the virtual memory
system, and also elaborate methods of key compression (the average size
of a key in Realia COBOL for example is about 12 bits -- this is independent
of the actual key length).