Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Associative Database

by blockcipher (Beadle)
on Mar 09, 2007 at 23:10 UTC ( #604084=CUFP: print w/ replies, xml ) Need Help??

All,

I built this a while ago because I wanted to better understand how an associative database works. Also, a product we're using where I work isn't available for anything but Windows, so I figured something cross-platform would be nice.

Anyway, this is a start. It's basically an in-memory database with the ability to store a snapshot of the data to disk. It seems to run very fast for small data sets, but I can see it slowing down severely for larger sets.

I'm posting it here today because I simply don't have the time to continue to develop it. Also, I didn't want this to just disappear, so I figured there may be an adventurous monk or two that can use this. I know it's not perfect, but I think it's a good start.

package AssocDB; use Data::Dumper; use Storable qw{freeze thaw store retrieve}; # Constructor sub new { my $self = {}; $self->{'entityhash'} = {}; $self->{'entityarray'} = (); $self->{'relationshiphash'} = {}; $self->{'predicatearray'} = (); $self->{'entitypool'} = (); bless($self, 'AssocDB'); } # Function to insert an entity into the database. # {{{ sub insertEntity { my $this = shift; my $entity = shift; if (@{$this->{'entitypool'}}) { my $newIndex = pop(@{$this->{'entitypool'}}); @{$this->{'entityarray'}}[$newIndex] = $entity; if (!exists($this->{'entityhash'}->{$entity})) { $this->{'entityhash'}->{$entity} = (); } push(@{$this->{'entityhash'}->{$entity}}, $newIndex + 1); } else { push(@{$this->{'entityarray'}}, $entity); my $length = @{$this->{'entityarray'}}; if (!exists($this->{'entityhash'}->{$entity})) { $this->{'entityhash'}->{$entity} = (); } push(@{$this->{'entityhash'}->{$entity}}, $length); } } # }}} # Function to insert a predicate into the database. # {{{ sub insertPredicate { my $this = shift; my $entity = shift; if (@{$this->{'entitypool'}}) { my $newIndex = pop(@{$this->{'entitypool'}}); @{$this->{'entityarray'}}[$newIndex] = $entity; if (!exists($this->{'entityhash'}->{$entity})) { $this->{'entityhash'}->{$entity} = (); } push(@{$this->{'entityhash'}->{$entity}}, $newIndex + 1); push(@{$this->{'predicatearray'}}, $newIndex + 1); } else { push(@{$this->{'entityarray'}}, $entity); my $length = @{$this->{'entityarray'}}; if (!exists($this->{'entityhash'}->{$entity})) { $this->{'entityhash'}->{$entity} = (); } push(@{$this->{'entityhash'}->{$entity}}, $length); push(@{$this->{'predicatearray'}}, $length); } } # }}} # Function to insert a relationship into the database. # {{{ sub insertRelationship { my $this = shift; my $subject = shift; my $predicate = shift; my $object = shift; my $key = qq{$subject:$predicate:$object}; $this->{'relationshiphash'}->{$key} = 1; } # }}} # Function to delete an entity from the database. # {{{ sub deleteEntityById { my $this = shift; my $entityId = shift; my @resultArray = grep { m{\d+:\d+:$entityId}xms } keys %{$this->{'relationshiphash'}}; return 0 if @resultArray; @resultArray = grep { m{$entityId}xms } @{$this->{'predicatearray' +}}; return 0 if @resultArray; my $entity = $this->{'entityarray'}->[$entityId - 1]; $this->{'entityarray'}->[$entityId - 1] = ''; push(@{$this->{'entitypool'}}, $entityId - 1); my @tempArray = @{$this->{'entityhash'}->{$entity}}; for (my $index; $index < @tempArray; $index++) { if ($tempArray[$index] == $entityId) { splice(@{$this->{'entityhash'}->{$entity}}, $index, 1); } } foreach my $index (keys %{$this->{'relationshiphash'}}) { delete($this->{'relationshiphash'}->{$index}) if $index =~ m{$entityId:\d+:\d+}xms; } delete($this->{'entityhash'}->{$entity}) if scalar @{$this->{'entityhash'}->{$entity}} == 0; return 1; } # }}} # Function to delete an predicate from the database. # {{{ sub deletePredicateById { my $this = shift; my $entityId = shift; my @resultArray = grep { m{\d+:$entityId:\d+}xms } keys %{$this->{'relationshiphash'}}; return 0 if @resultArray; my $entity = $this->{'entityarray'}->[$entityId - 1]; $this->{'entityarray'}->[$entityId - 1] = ''; push(@{$this->{'entitypool'}}, $entityId - 1); my @tempArray = @{$this->{'entityhash'}->{$entity}}; for (my $index; $index < @tempArray; $index++) { if ($tempArray[$index] == $entityId) { splice(@{$this->{'entityhash'}->{$entity}}, $index, 1); } } @tempArray = @{$this->{'predicatearray'}}; for (my $index; $index < @tempArray; $index++) { if ($tempArray[$index] == $entityId) { splice(@{$this->{'predicatearray'}}, $index, 1); } } delete($this->{'entityhash'}->{$entity}) if scalar @{$this->{'entityhash'}->{$entity}} == 0; return 1; } # }}} # Function to delete an relationship from the database. # {{{ sub deleteRelationship { my $this = shift; my $subject = shift; my $predicate = shift; my $object = shift; my $key = qq{$subject:$predicate:$object}; delete($this->{'relationshiphash'}->{$key}); } # }}} # Function to get an entity from the database using the name. # {{{ sub getEntityByName { my $this = shift; my $entity = shift; return @{$this->{'entityhash'}->{$entity}}; } # }}} # Function to get an entity from the database using the ID. # {{{ sub getEntityById { my $this = shift; my $entity = shift; return $this->{'entityarray'}->[$entity]; } # }}} # Function to get the predicates from the database. # {{{ sub getPredicates { my $this = shift; my @tempArray = @{$this->{'predicatearray'}}; my @resultArray = map { $_ . ':' . $this->{'entityarray'}->[$_ - 1 +] } @tempArray; return @resultArray; } # }}} # Function to get all relationships an entity is the Subject of. # {{{ sub getSubjectRel { my $this = shift; my $entityId = shift; my @resultArray = grep { m{$entityId:\d+:\d+}xms } keys %{$this->{'relationshiphash'}}; return @resultArray; } # }}} # Function to get all relationships an entity is the Object of. # {{{ sub getObjectRel { my $this = shift; my $entityId = shift; my @resultArray = grep { m{\d+:\d+:$entityId}xms } keys %{$this->{'relationshiphash'}}; return @resultArray; } # }}} # Function to write the data to disk using Storable. # {{{ sub storeData { my $this = shift; my $filename = shift;; my %dataHash; $dataHash{'entityhash'} = freeze($this->{'entityhash'}); $dataHash{'entityarray'} = freeze($this->{'entityarray'}); $dataHash{'relationshiphash'} = freeze($this->{'relationshiphash'}); $dataHash{'predicatearray'} = freeze($this->{'predicatearray'}); $dataHash{'entitypool'} = freeze($this->{'entitypool'}); store($this, $filename); } # }}} # Function to load the data from a file. # {{{ sub loadData { my $this = shift; my $filename = shift;; my $temp = retrieve($filename); $this->{'entityhash'} = $temp->{'entityhash'}; $this->{'relationshiphash'} = $temp->{'relationshiphash'}; $this->{'entityarray'} = $temp->{'entityarray'}; $this->{'predicatearray'} = $temp->{'predicatearray'}; $this->{'entitypool'} = $temp->{'entitypool'}; } # }}} 1;

Comment on Associative Database
Download Code
Re: Associative Database
by Anno (Deacon) on Mar 10, 2007 at 17:25 UTC
    A couple of rather unrelated remarks.

    In your constructor ->new you have the line

    bless($self, 'AssocDB');
    That is bad construction, it won't allow anyone to subclass AssocDB. You should bless into the class the constructor was called through:
    bless($self, shift);

    The term Associative Database, while suggestive, doesn't have an agreed-upon technical meaning (correct me if I'm wrong), so it would be necessary to add a minimum of documentation about the purpose and possible applications. As it is, the reader can pick up that such a beast has entities, predicates and relationships. You'd have to read the code to get an idea of how they interact to result in associations.

    To enable anyone to pick up the project with some confidence you'd have to add some documentation that explains these points.

    Anno

Re: Associative Database
by chanio (Priest) on Mar 11, 2007 at 06:25 UTC
    (From Wikipedia )
    | ... | The Associative Model of Data is an alternative | data model for database systems. | | Other data models, such as the relational model | and the object data model are record-based. | Record-based models involve encompassing | attributes about a thing, such as a car in a | record structure (where attributes might be | registration, colour, make, model, etc). | | In the associative model, everything which has | “discrete independent existence” is modeled as an | entity, and relationships between them are modeled | as associations. | ...

Re: Associative Database
by DrHyde (Prior) on Mar 12, 2007 at 10:22 UTC
      I think in a truly associative db, circular refs would be OK, and in DBM::Deep (which is really really cool btw), you cannot have any circular refs — without infinite loops anyway. Though, the same place I read that indicates they're working on it.

      From later in the .pod, though (around scalar refs and the like), I get the feeling that it might not update quite as expected.

      -Paul

Re: Associative Database
by halley (Prior) on Mar 14, 2007 at 16:44 UTC
    I know this is a bit off your intended topic, but I thought I'd put in my feedback anyway. In general, I see this stuff as distracting visual noise.
    # Function to... # {{{ # }}}
    Why not convert the useful portion of the comment you've provided (denoted by the ... above) into some Plain Old Documentation? See POD in 5 minutes for more.

    --
    [ e d @ h a l l e y . c c ]

      Hi halley,

      Having the opening and closing braces {{{ ... }}} can actually be pretty useful, if you're a vim/gvim user.

      It implements a mechanism called "folding", whereby one can "fold" multiple lines of text into a single physical line on the screen, making it easier to read the program as a whole.

      I can see why it might be distracting if you weren't a vim/gvim user, but its advantages, IMO, far outweigh its disadvantages for those who use this mechanism.


      s''(q.S:$/9=(T1';s;(..)(..);$..=substr+crypt($1,$2),2,3;eg;print$..$/
        My vim folds this:
        sub foo { yadda yadda yadda }
        just fine.
Re: Associative Database
by jwkrahn (Monsignor) on Mar 14, 2007 at 21:49 UTC
    106 my @tempArray = @{$this->{'entityhash'}->{$entity}}; 107 for (my $index; $index < @tempArray; $index++) 108 { 109 if ($tempArray[$index] == $entityId) 110 { 111 splice(@{$this->{'entityhash'}->{$entity}}, $index +, 1); 112 } 113 } 137 my @tempArray = @{$this->{'entityhash'}->{$entity}}; 138 for (my $index; $index < @tempArray; $index++) 139 { 140 if ($tempArray[$index] == $entityId) 141 { 142 splice(@{$this->{'entityhash'}->{$entity}}, $index +, 1); 143 } 144 }

    This code will only work correctly if there is only one element of the array that matches $entityId. You should put last; after the splice so that you don't try to remove more than one element.

    If you have mutliple elements that need to be removed then using grep would be simpler:

    @{ $this->{ entityhash }{ $entity } } = grep $_ != $entityId, @{ $this +->{ entityhash }{ $entity } };
    6 # Constructor 7 sub new 8 { 9 my $self = {}; 10 $self->{'entityhash'} = {}; 11 $self->{'entityarray'} = (); 12 $self->{'relationshiphash'} = {}; 13 $self->{'predicatearray'} = (); 14 $self->{'entitypool'} = (); 15 bless($self, 'AssocDB'); 16 }
    On your 'hash' keys you are assigning hashes so shouldn't you also assign arrays to the 'array' keys?
    # Constructor sub new { my $self = {}; $self->{'entityhash'} = {}; $self->{'entityarray'} = []; $self->{'relationshiphash'} = {}; $self->{'predicatearray'} = []; $self->{'entitypool'} = []; bless($self, 'AssocDB'); }
    28 if (!exists($this->{'entityhash'}->{$entity})) 29 { 30 $this->{'entityhash'}->{$entity} = (); 31 } 38 if (!exists($this->{'entityhash'}->{$entity})) 39 { 40 $this->{'entityhash'}->{$entity} = (); 41 } 57 if (!exists($this->{'entityhash'}->{$entity})) 58 { 59 $this->{'entityhash'}->{$entity} = (); 60 } 68 if (!exists($this->{'entityhash'}->{$entity})) 69 { 70 $this->{'entityhash'}->{$entity} = (); 71 }
    Perl uses autovivification so these lines are unnecessary and don't actually do what you seem to think they do.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://604084]
Approved by GrandFather
Front-paged by Arunbear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (5)
As of 2014-12-27 02:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (176 votes), past polls