Mstore.pm (v0.1) -- *epsilon* graph store implemented on top of BerkeleyDB
Graph is in *epsilon* store represented as a table @stor storing edges of a graph in rows. Each edge is defined by triple including subject node (S), edge name or predicate (P), and, object node (O). Before entered into table @stor all names of nodes and edges are converted into integers by means of module KeyID.pm.
Each edge stored as a record in a table @stor has a unique identifier that allows referencing. Index access to stored graph is provided using all possible combinations of "keys" that can be the values of S, P, O, SP, SO, PO and SPO.
Mapping from keys to edge (triple) IDs is realized using an associative array %equi tied to a BerkeleyDB B-tree. Each key K is composed of a subset of SPO values comprising a triple. The value part of this entry includes a reference to the first edge (triple) in table @stor with a given key value K.
List of edges with a key value K can be accessed by means of a ring of edges. This is implemented by adding column(s) to @stor that include references to next edge with a key value K. The table @stor has therefore 6 additional columns for representation of S, P, O, SP, SO, PO, and SPO rings.
@storThe main table of *epsilon* graph store is implemented as a BerkeleDB table of fixed-length records. The records are accessible via the record number. Hence, each triple has a triple-id. A triple is stored in columns 0, 1, 2 of a table @stor. The columns 3,4,5,6,7,8 represent rings for S,P,O,SP,SO,PO,SPO keys, respectively.
$trcnTriple counter.
%equiA mapping from keys to ids is implemented in a BerkeleyDB B-tree. A key is composed of: 1. colum num from @stor used for index, 2. first key, and 3. second key (optional), 4. third key (optional) of the index.
A scan access can be used for accessing rings of a given key. Scan descriptors are stored in circular array @desc. Scan descriptors include data about current state of a scan.
@descCircular array of scan descriptors.
$dsidCurrent index of scan descriptor.
$dsnmMaximal number of scan descriptors.
ok = read(ix)Read triple with index ix from @stor into array a. Pointer to the array a is returned.
ok = write(pa,ix)Write array pointed to by parameter pa in @stor at index ix.
int = size_store(ix)Returns the size of @stor.
int = size_index(ix)Returns the size of %equi.
key = make_key(ix,id,id1,id2)Construct key from ix, id, id1, and id2. ix is index that identifies the column of @stor (3-9). id, id1 and id2 are index values for S,P,O. Function returns the constructed key.
key = make_keytype(ix,id,id1,id2)Construct key type from bu, ix, id, id1, and id2. bu is boolean value stating weather counting is bound or unbound. ix is index that identifies the column of @stor (3-9). id, id1 and id2 are index values for S,P,O. Function returns the constructed key.
kv = make_keyval(tri,ix,id,id1,id2)Construct key value kv from triple tri and ix. Insert kv to the statistics for given ix and classes id, id1, and id2.
key = create_key(ix,k1,k2,k3)Construct key from ix, k1, k2, and k3. ix is index that identifies the column of @stor (3-9). k1, k2 and k3 are string values for S,P,O. Function returns the constructed key.
ok = insert_key(ix, id, id1)Insert key ix-id[-id1] into key-value table %equi.
hd = open_scan(ix, id, id1)Open scan for index ix and key(s) id and, optionally, id1. Return pointer to descriptor.
$tid = scan_next($hd)Return handle ie. index in @desc.
bool = scan_eor($dsix)Return true if end of ring and false otherwise.
ok = print_store()Prints contents of $stor from 0 to $#stor.
ok = print_equi(id)Prints key-value mapping %equi where key is ix-id-[-id1] and id is index to @stor.
ok = print_ring(key)Prints ring defined by key.
ok = project_ring(key)Project ring defined by key into column.
ok = enter_triple($tri)Enter triple into KeyID and Mstore.
Iztok Savnik <iztok.savnik@upr.si>; Kiyoshi Nitta <knitta@yahoo-corp.jp>
Created 09/12/2014; modified 26/01/2015.