creating database

creating database

[caellumx]

hi

I'm trying to create a database using ada. I'm struggling to work out
how to implement the record type and storage. The data only has to be
stored in main memory.

I was thinking of creating the ADT as a record with various fields, and
then an array with each element containing a record. However, I don't
know how many records there'll be so it seems inefficient to declare an
array of a particular size.

Any advice one how to implement the database would be very much
appreciated. As an ada novice, I'm struggling.

Re: creating database

[Ludovic Brenta]

 writes:
> hi
>
> I'm trying to create a database using ada. I'm struggling to work
> out how to implement the record type and storage. The data only has
> to be stored in main memory.
>
> I was thinking of creating the ADT as a record with various fields,
> and then an array with each element containing a record. However, I
> don't know how many records there'll be so it seems inefficient to
> declare an array of a particular size.
>
> Any advice one how to implement the database would be very much
> appreciated. As an ada novice, I'm struggling.

We do not do students' homework for them, so I'm not going to give you
"the answer" here (if you're not a student, this sentence is intended
for future readers who may be students).

Your question is not specific to Ada or any particular language.  It
is a design question.  If I understand well, you're trying to store a
variable (and unknown at compile time) number of "things" in memory.
There are many well-known data structures to choose from, or you could
roll your own.  The simplest data structure you can try is called a
"linked list".  Look it up on Google.  A linked list is simple and
efficient when adding new "things", but inefficient when searching for
one particular "thing".  Most industrial-strength database engines use
more sophisticated data structures such as B-trees (q.v., on Google).

HTH

-- 
Ludovic.

Re: creating database

[Jacob Sparre Andersen]

Ludovic Brenta writes:

> Your question is not specific to Ada or any particular language.  It
> is a design question.  If I understand well, you're trying to store
> a variable (and unknown at compile time) number of "things" in
> memory.  There are many well-known data structures to choose from,
> or you could roll your own.  The simplest data structure you can try
> is called a "linked list".  Look it up on Google.  A linked list is
> simple and efficient when adding new "things", but inefficient when
> searching for one particular "thing".  Most industrial-strength
> database engines use more sophisticated data structures such as
> B-trees (q.v., on Google).

And some of these types of data-structures exist as a part of the
standard library in the upcoming revision of the Ada standard.  If you
want to take a look at the current version of this extension of the
standard library, "AI302" and "Ada.Containers" are the keywords to
search for.

In one of the most recent Ada journals (I can't remember if it was the
ACM or the Ada Europe one), there was an overview of the trade-offs
related to selecting different kinds of containers.  That's probably a
good reference for anybody choosing which variant of "Ada.Containers"
to use.

Jacob
-- 
�By becoming continuous, war has fundamentally changed its character.
 In past ages, a war, almost by definition, was something that sooner
 or later came to an end, usually in unmistakable victory or defeat.�
                               -- Nineteen Eighty-Four, George Orwell
�I don't think you can win [the war on terror].�    -- George W. Bush

Re: creating database

[Matthew Heaney]

Jacob Sparre Andersen <sparre@nbi.dk> writes:

> And some of these types of data-structures exist as a part of the
> standard library in the upcoming revision of the Ada standard.  If you
> want to take a look at the current version of this extension of the
> standard library, "AI302" and "Ada.Containers" are the keywords to
> search for.

Ada.Containers are included in gcc 4.0, so you don't have to wait for
Ada 2005 to get a container library.

Re: creating database

[Jacob Sparre Andersen]

caellumx@yahoo.com writes:

> I was thinking of creating the ADT as a record with various fields,
> and then an array with each element containing a record. However, I
> don't know how many records there'll be so it seems inefficient to
> declare an array of a particular size.

Sensible thinking.

> Any advice one how to implement the database would be very much
> appreciated. As an ada novice, I'm struggling.

As you have already been told, this is not really an Ada specific
question.

Instead of allocating a fixed size array - which on unix systems isn't
quite as bad an idea as it sounds - you can allocate and reallocate
chunks of varying or fixed size (down to a single record element) with
pointers pointing to various other chunks.  Exactly how you do it
depends on your problem; the frequency of insertions, the frequency of
deletions, the frequency of searches and knowledge about the searches
which you can use to prearrange the elements for faster searching.

If you tell us what your problem is (and preferably also that it isn't
a homework problem), it is easier to give you specific advice.  And
even if it is a homework problem, there's probably somebody who can
point you to a good textbook or ask some leading questions.

Greetings,

Jacob
-- 
"War does not determine who is right - only who is left."
                                         -- Bertrand Russell

Re: creating database

[tmoran]

> > don't know how many records there'll be so it seems inefficient to
> > declare an array of a particular size.
>
> Sensible thinking.
> ...
> Instead of allocating a fixed size array - which on unix systems isn't
> quite as bad an idea as it sounds - you can allocate and reallocate
  A fixed array allocation may be the both the most efficient and the
simplest on a virtual memory system.  The parts you don't use don't
occupy any physical space, just address space, and the OS's allocation
of physical space may well be difficult to beat in efficiency.

Re: creating database

[Robert A Duff]

tmoran@acm.org writes:

> > > don't know how many records there'll be so it seems inefficient to
> > > declare an array of a particular size.
> >
> > Sensible thinking.
> > ...
> > Instead of allocating a fixed size array - which on unix systems isn't
> > quite as bad an idea as it sounds - you can allocate and reallocate
>   A fixed array allocation may be the both the most efficient and the
> simplest on a virtual memory system.  The parts you don't use don't
> occupy any physical space, just address space, and the OS's allocation
> of physical space may well be difficult to beat in efficiency.

But I believe that by default, on both Unix and Windows, the OS will
allocate backing store (i.e. space in the paging file).
That can be a problem for really huge arrays.

To avoid that on Unix, use mmap with the NORESERVE flag,
and map the file /dev/zero -- then you'll get allocate-on-write
pages of virtual address space.

On Windows, it's a bit more complicated: use VirtualAlloc to reserve
pages, and then when you actually want to use them, use VirtualAlloc
again to "commit" pages.

- Bob

Re: creating database

[Matthew Heaney]

caellumx@yahoo.com writes:

> I was thinking of creating the ADT as a record with various fields,
> and then an array with each element containing a record. However, I
> don't know how many records there'll be so it seems inefficient to
> declare an array of a particular size.

As someone else already pointed out, you should take a look at the
Ada.Container suite.  It sounds like you need a set or maybe a map.

The latest API is described here:

<http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-20302.TXT?rev=1.19>

You can find a reference implementation here:

<http://charles.tigris.org/source/browse/charles/src/ai302/>

gcc 4.0 includes the ada.container library, so you might have it on your
system already.

I recommend poking around the examples directory for some ideas:

<http://charles.tigris.org/source/browse/charles/src/ai302/examples/>

I also recommend reading the !examples section that follows the
normative section of the AI-302 draft.

Re: creating database

[brian.b.mcguinness]

I don't see deques listed.  Have they been removed
from the standard set of container clases?

--- Brian

Re: creating database

[Georg Bauhaus]

brian.b.mcguinness@lmco.com wrote:
> I don't see deques listed.  Have they been removed
> from the standard set of container clases?

Yes, probably in order to have a minimal set of
building blocks.


-- Georg 

Re: creating database

[Randy Brukardt]

<brian.b.mcguinness@lmco.com> wrote in message
news:1115830671.818914.303600@g49g2000cwa.googlegroups.com...
> I don't see deques listed.  Have they been removed
> from the standard set of container clases?

No. For the reason that "deque" was never in any proposal submitted to the
ARG. So there is no possibility of it being "removed". The only proposed
container that didn't ultimately get included was the multiset. Given that
the containers take up 50 pages of the proposed standard (roughly 40% of the
new material), they are already at the limit of effort available.

Beyond that, they are insufficiently different from the vectors and lists.
They have the same operation set as vectors and lists, and only for huge
numbers of elements would they have an appreciable advantage over those
other containers for any operation. And our goal for the standard containers
library was to avoid trying to solve all possible problems; rather, we tried
to solve the 80+% of problems where performance is not critical and
functionality is more important. When performance is truly critical, a
custom package would almost certainly be preferable over any general,
"canned" package. But that doesn't happen that often (and it probably is the
case that it happens far less than we like to think).

                            Randy Brukardt

Re: creating database

[Matthew Heaney]

brian.b.mcguinness@lmco.com writes:

> I don't see deques listed.  Have they been removed from the standard
> set of container clases?

Just a point of terminology: I am assuming that to "deque" you are
refering to the container in the C++ STL named "deque".

I had deques in my original proposal (the one that was 150 pgs), but I
removed them from my proposal at the request of the ARG, so that the
proposal would have a more modest size.

So a deque container was never actually in the standard library, and
hence wasn't in any sense ever "removed" from the standard.

-Matt

Re: creating database

[news.snafu.de]

<caellumx@yahoo.com> schrieb im Newsbeitrag 
news:1115570998.707181.84650@o13g2000cwo.googlegroups.com...
> hi
>
> I'm trying to create a database using ada. I'm struggling to work out
> how to implement the record type and storage. The data only has to be
> stored in main memory.


May be you should think about using an already existing RDBMS
procudt, e.g. MySQL or PostgreSQL etc. Bindings between Ada
and the corresponding natic bindings are available at various
places (e.g.  http://gnade.sourceforge.net/).

Regards
    M.Erdmann


PS: You will find also there odb which is a simple minded approach
to object persistency which might fit you ideas better then using and
rdbms.


>
> I was thinking of creating the ADT as a record with various fields, and
> then an array with each element containing a record. However, I don't
> know how many records there'll be so it seems inefficient to declare an
> array of a particular size.
>
> Any advice one how to implement the database would be very much
> appreciated. As an ada novice, I'm struggling.
> 

Re: creating database

[Matthew Heaney]

"news.snafu.de" <michael_erdmann@snafu.de> writes:

> May be you should think about using an already existing RDBMS product,
> e.g. MySQL or PostgreSQL etc.

I think the OP said that the database would only need to live in
non-persistent memory, so a "database" database might be overkill.  

I think he just needed a container which he could use do lookups, but
didn't use that term.  He probably needs a map, and the standard
container library has those.

The standard library is already showing up in gcc releases (it was
included in gcc 4.0).  There's also a reference implementation of the
library.  So availability shouldn't be an issue.

<http://charles.tigris.org/source/browse/charles/src/ai302/>

-Matt

Re: creating database

[Michael Erdmann]

"Matthew Heaney" <matthewjheaney@earthlink.net> schrieb im Newsbeitrag 
news:uwtq5jgxs.fsf@earthlink.net...
> "news.snafu.de" <michael_erdmann@snafu.de> writes:
>
>> May be you should think about using an already existing RDBMS product,
>> e.g. MySQL or PostgreSQL etc.
>
> I think the OP said that the database would only need to live in
> non-persistent memory, so a "database" database might be overkill.
ups, you are right, i got this wrong.


> <http://charles.tigris.org/source/browse/charles/src/ai302/>
>
> -Matt