Multiple keys for a map

Multiple keys for a map

[Peter Brooks]

I know that maps in Containers.Hashed_Maps and Containers.Ordered_Map are designed as single-key look-up tables.

Is there an extension that allows multiple keys? 

I'd like to be able to do something like this:

procedure Insert (Container : in out Map;
                  key1, key2, key3       : in     Key_Type;
                  New_Item  : in     Element_Type;
                  Position  :    out Cursor;
                  Inserted  :    out Boolean);

allowing:

insert(my_map,"fox","jumps","dog","The quick brown fox jumps over the lazy dog",location,succeeded);
insert(my_map,"cow","jumps","moon","The cow jumps over the moon",location,succeeded);
insert(my_map,"dog","jumps","log","The lazy dog jumps over the small log",location,succeeded);
insert(my_map,"dog","jumps","bed","The very lazy dog jumps into bed",location,succeeded)

So that later, I can have:


Subject := find(my_map,"fox",-,-);
Verb := find(my_map,-,"jumps",-);
Object := find(my_map,-,-,"dog");

and, after this:

Subject = Verb = Object;

I know this could be done with three calls to Insert, but I also want to be able to call:

find(mymap,"fox","jumps","dog") => true

and

find(mymap,"dog","jumps","fox") => false

and, ideally,

find(myman,"dog",-,-) => 

"The Lazy dog jumps over the small log"
"The very lazy dog jumps into bed"

Any suggestions?

Re: Multiple keys for a map

[Dmitry A. Kazakov]

On Tue, 17 Sep 2013 07:51:24 -0700 (PDT), Peter Brooks wrote:

> I know that maps in Containers.Hashed_Maps and Containers.Ordered_Map are designed as single-key look-up tables.
[...]
> Any suggestions?

It looks like a relational table of three columns.

Maps can be used to index such a table, or red-black trees, or whatever.

You could also take an existing light-weight RDBMS, e.g. SQLite3 or
Berkeley DB. There exist many Ada bindings to SQLite3.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Multiple keys for a map

[Peter Brooks]

On Tuesday, 17 September 2013 18:52:37 UTC+2, Dmitry A. Kazakov  wrote:
>  
> Maps can be used to index such a table, or red-black trees, or whatever.
> 
> You could also take an existing light-weight RDBMS, e.g. SQLite3 or
> Berkeley DB. There exist many Ada bindings to SQLite3.
> 
Thank you, yes, I'm hoping to avoid that overhead.

Re: Multiple keys for a map

[Dmitry A. Kazakov]

On Tue, 17 Sep 2013 10:49:15 -0700 (PDT), Peter Brooks wrote:

> On Tuesday, 17 September 2013 18:52:37 UTC+2, Dmitry A. Kazakov  wrote:
>>  
>> Maps can be used to index such a table, or red-black trees, or whatever.
>> 
>> You could also take an existing light-weight RDBMS, e.g. SQLite3 or
>> Berkeley DB. There exist many Ada bindings to SQLite3.
>> 
> Thank you, yes, I'm hoping to avoid that overhead.

If you want a better than O(n) search you need a map (or an equivalent of)
for each search criterion. With wildcarded triplets it gives 7
maps/indices:

   x,y,z -> Element
   *,y,z -> Bucket of (x,y,z) keys or other references to elements in above
   x,*,z
   x,y,*
   x,*,*
   *,y,*
   *,*,z

It is quite straightforward to implement.

An alternative could be a kd-tree. (I am not sure how good a kd-tree is for
search in a plane, which would be an equivalent of wildcard search).

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Multiple keys for a map

[Peter Brooks]

On Wednesday, 18 September 2013 09:22:33 UTC+2, Dmitry A. Kazakov  wrote:
> On Tue, 17 Sep 2013 10:49:15 -0700 (PDT), Peter Brooks wrote:
> 
> 
> 
> > On Tuesday, 17 September 2013 18:52:37 UTC+2, Dmitry A. Kazakov  wrote:
> 
> >>  
> 
> >> Maps can be used to index such a table, or red-black trees, or whatever.
> 
> >> 
> 
> >> You could also take an existing light-weight RDBMS, e.g. SQLite3 or
> 
> >> Berkeley DB. There exist many Ada bindings to SQLite3.
> 
> >> 
> 
> > Thank you, yes, I'm hoping to avoid that overhead
> 
> If you want a better than O(n) search you need a map (or an equivalent of)
> for each search criterion. With wildcarded triplets it gives 7
> maps/indices:
> 
>    x,y,z -> Element
>    *,y,z -> Bucket of (x,y,z) keys or other references to elements in above
>    x,*,* 
>    x,y,*
>    x,*,*
>    *,y,*
>    *,*,z
> 
> It is quite straightforward to implement.
> 
That makes good sense - with a graph as well, it'd go up to 14, which is still quite reasonable in terms of overhead. I'll look into it. I see that it's quite easy to make it all memory resident, so there doesn't need to be any disc overhead.

Re: Multiple keys for a map

[gautier_niouzes]

Hello,
If you can stick with one answer per query, you can always glue several keys into one, like
  key1 & '#' key2 & '#' & key3
for strings or
  type Key_triplet is array(1..3) of Key_Type;
and use Key_triplet instead of Key_type.
For multiple answers... it is different. If keys are enumerated types you could loop through the type and collect answers. Otherwise, it's perhaps better to consider a DB.
_________________________
Gautier's Ada programming
http://gautiersblog.blogspot.com/search/label/Ada
NB: follow the above link for a valid e-mail address

Re: Multiple keys for a map

[Peter Brooks]

On Tuesday, 17 September 2013 20:57:17 UTC+2, gautier...@hotmail.com  wrote:
> Hello,
> 
> If you can stick with one answer per query, you can always glue several keys into one, like
> 
>   key1 & '#' key2 & '#' & key3
> 
> for strings or
> 
>   type Key_triplet is array(1..3) of Key_Type;
> 
> and use Key_triplet instead of Key_type.
> 
> For multiple answers... it is different. If keys are enumerated types you could loop through the type and collect answers. Otherwise, it's perhaps better to consider a DB.
> 
Nice idea, thank you. I'll try the array idea, that looks as if it might be ideal. It should be fast too.

Re: Multiple keys for a map

[Shark8]

On Tuesday, September 17, 2013 8:51:24 AM UTC-6, Peter Brooks wrote:
> I know that maps in Containers.Hashed_Maps and Containers.Ordered_Map are designed as single-key look-up tables.
> 
> Is there an extension that allows multiple keys? 
> 
> I'd like to be able to do something like this:
> 
> procedure Insert (Container : in out Map;
>                   key1, key2, key3       : in     Key_Type;
>                   New_Item  : in     Element_Type;
>                   Position  :    out Cursor;
>                   Inserted  :    out Boolean);
> 
> allowing:
> 
> insert(my_map,"fox","jumps","dog","The quick brown fox jumps over the lazy dog",location,succeeded);
> insert(my_map,"cow","jumps","moon","The cow jumps over the moon",location,succeeded);
> insert(my_map,"dog","jumps","log","The lazy dog jumps over the small log",location,succeeded);
> insert(my_map,"dog","jumps","bed","The very lazy dog jumps into bed",location,succeeded)
> 
> So that later, I can have:
> Subject := find(my_map,"fox",-,-);
> Verb := find(my_map,-,"jumps",-);
> Object := find(my_map,-,-,"dog");
> 
> and, after this:
> Subject = Verb = Object;
> 
> I know this could be done with three calls to Insert, but I also want to be able to call:
> 
> find(mymap,"fox","jumps","dog") => true
> and
> find(mymap,"dog","jumps","fox") => false
> and, ideally,
> find(myman,"dog",-,-) => 
> 
> "The Lazy dog jumps over the small log"
> "The very lazy dog jumps into bed"
> 
> Any suggestions?

I'm vaguely reminded of Prolog by this question: this problem was basically the intro for the book I had.

Re: Multiple keys for a map

[Peter Brooks]

On Wednesday, 18 September 2013 07:19:18 UTC+2, Shark8  wrote:
>  
> I'm vaguely reminded of Prolog by this question: this problem was basically the intro for the book I had.
>
Well remembered! It's exactly the sort of question Prolog was designed to answer. Actually, Prolog might be a much better front-end to a triplestore than SPARQL. I'm not sure, I'll look into it. I see that there's a simple Prolog interpreter with an Ada API here: xhttp://goanna.cs.rmit.edu.au/~dale/software/ it might be just the thing.

Anyway, that's for a bit later, I'm still, obviously, working to get the structure right.

Unfortunately the array of hash-keys doesn't work with the with Ada.Containers.Hashed_Maps package.

It looks as if the sensible thing will to create a container for the subject, then simply point the predicate, object and group items to it. It makes some sense as the object space is much smaller than subject space, and the predicate space is very small and the graph space tiny.

It probably makes sense to have graphs and predicates in a simple array, there are so few of them, and only have efficient searching for subjects and objects. It makes the model much simpler. Even if all three have the same treatment, it makes sense for them to occupy separate spaces because that makes the chance of duplicates turning up even smaller.