GQLite

GQLite is a graph database for testing abilities in ending device. The target is to make a small, fast, light-weight graph database.

• 1. Designed
• 2. Build
  • 2.1. ubuntu
  • 2.2. macos
  • 2.3. windows
  • 2.4. android
• 3. How to use in C/C++
• 4. Graph Query Language(Unstable)
  • 4.1. Create Graph
  • 4.2. Data Types
  • 4.3. Add Vertex & Edge
  • 4.4. Remove Vertex & Edge
  • 4.5. Query
    • 4.5.1. intrinct function
    • 4.5.2. condition
• 5. Reference Paper

1. Designed

Here is GQlite's framework:

2. Build

Use command with git clone --recursive https://github.com/webbery/gqlite.git to clone this repository.

2.1. ubuntu

Install latest version of bison.

# Build type can be Release or Debug. If Build type is `Debug`, 'gcorv' should be install before build.
cmake -DCMAKE_BUILD_TYPE=Release gqlite_root_dir

2.2. macos

Install latest version of bison.

2.3. windows

An version of flex&bison is placed in dir tool. So it's not need to install dependency.

2.4. android

C++: 17
Please use cross-compile tools on Ubuntu/MacOS. Some mistakes of libzstd occur on Windows.

3. How to use in C/C++

An simple example shows how to use in your program is here:

#include "gqlite.h"

int gqlite_exec_callback(gqlite_result* params)
{
  if (params) {
    switch (params->type)
    {
    case gqlite_result_type_node:
    {
      gqlite_node* node = params->nodes;
      while (node) {
        switch (node->_type)
        {
        case gqlite_node_type_vertex:
        {
          gqlite_vertex* v = node->_vertex;
          if (v->type == gqlite_id_type::integer) {
            printf("[%d, %s]\n", v->uid, v->properties);
          }
          else {
            printf("[%s, %s]\n", v->cid, v->properties);
          }
        }
          break;
        case gqlite_node_type_edge:
          break;
        default:
          break;
        }
        node = node->_next;
      }
    }
      break;
    case gqlite_result_type_cmd:
      for (size_t idx = 0; idx < params->count; ++idx) {
        printf("%s\n", params->infos[idx]);
      }
      break;
    default:
      break;
    }
  }
  return 0;
}

int main() {
  gqlite* pHandle = 0;
  gqlite_open(&pHandle);
  char* ptr = nullptr;
  gqlite_exec(pHandle,
    "{create: 'example_db'};",
    gqlite_exec_callback, nullptr, &ptr);
  gqlite_free(ptr);
  gqlite_close(pHandle);
}

4. Graph Query Language

4.1. Create Graph

Create a graph is simply use create keyword. The keyword of group, means that all entity node which group belongs to. If we want to search vertex by some property, index keyword will regist it.

{
    create: 'movielens',
    group: [
        {movie: ['title', 'genres']},
        {tag: ['user_id', 'tag', 'movie_id'], index: ['tag']},  // <-- relationship's property must write center if it is a edge
        {rate: ['user_id', 'rate', 'movie_id']}
    ]
};

Here we create an index called tag. The tag will create revert index from tag to group tag's id.
So after upset a new tag, the revert index will be added.

4.2. Data Types

Normaly, basic data type as follows:
string: 'string'
number: 10 means integer, 10.0 means real number.
array: start as [ and end with ]
binary: start with 0b, then follow as base64 string, it will save as binary data. Such as 0b'df32099'
datetime: start with 0d, then will try to convert following string to datetime, such as 0d1642262159
vector: a special type of array, which items are same type.
hash: a special type of string, start with 0h like 0h'hash'

4.3. Add Vertex & Edge

add or update vertex:

{
    upset: 'movie',
    vertex:[
        [21, {'title': 'Get Shorty', genres: ['Comedy', 'Crime', 'Thriller']}],
        [53, {title: 'Lamerica (1994)', genres: ['Adventure','Drama']}],
        [88, {title: 'Black Sheep (1996)'}]
    ]
};

Note that current graph is created graph before called movielens. The 3 of vertexes is added to group movie.

add or update edge:

{
    upset: 'tag',
    edge: [
        [{user_id: 2}, {'--': 'Martin Scorsese'}, {movie_id: [106782, 89774]}],
        [{user_id: 21}, {'--': ['romantic comedy', 'wedding']}, {movie_id: 1569}],
    ]
};

For simply use, it can be write as follows, but id is automatic generated by database:

{
    upset: 'edge',
    edge: [
        ['Tom', ->, 'Lamerica'],
        ['Kitty', <-, 'Black Sheep'],
    ]
};

or simply use bidirection:

{
    upset: 'tag',
    edge: [
        ['Tom', --, 'Lamerica'],
        ['Kitty', --, 'Black Sheep'],
    ]
};

4.4. Remove Vertex & Edge

{remove: 'graph', vertex: [21, 88]};

4.5. Query

4.5.1. intrinct function

count()

{// this is used to count the number of vertex
    query: count(vertex),
    group: 'movie'
};

4.5.2. condition

query all movie that has tag:

{
    query: [movie.title, movie.genres],
    where: [
        [user_id, {--: *}, movie_id]        // here is an edge condition, user_id and movie_id are in group `tag`, * represent all relationship here.
    ],
    in: 'movielens' // the graph instance can be written here or not.
};

Or:

{
    query: movie,
    where: {tag: ['black comedy']}
};

query points from graph by relationship:

{
    query: user,
    where: {
        ->: 'son'
    }
};

{
    query: user,
    where: [
        {
            user: function(user) { return user.age > 10}
        }
    ],
};

query a list of neighbors, where 1 mean 1'st neighbors:

{query: user, from: 'v1', where: {--: 1}};

In order to get a search way

4.6. Inference

Here we define a kind of inference operator, and apply it to a graph.
HMM:

{
    query: hidden_variant,
    event: [{e1: 'sun'}, {e2: 'rain'}, {e3: 'wind'}],
    where: [
        [hidden_variant.v1, {->: 0.2}, e1],
        [hidden_variant.v2, {->: gassian(0.2, 0.1)}, e2],
        [hidden_variant.v3, {->: gassian(0.2, 0.1)}, e3],
        [hidden_variant.v1, {->: 0.2}, hidden_variant.v2],
        [hidden_variant.v2, {->: 0.2}, hidden_variant.v3],
        [hidden_variant.v1, {->: 0.2}, hidden_variant.v4],
    ]
};

5. Utility

5.1. Show Graphs

show graph
show graph 'xxx'

Use Graph

use graph 'xxx'

6. Reference Papers

1. Yihan Sun, Daniel Ferizovic, Guy E. Belloch. PAM: Parallel Augmented Maps.
2. Laxman Dhulipala, Guy Blelloch, Yan Gu, Yihan Sun. PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections.
3. Amine Ghrab, Oscar Romero, Sabri Skhiri etc. GRAD: On Graph Database Modeling.
4. 向量索引算法HNSW和NSG的比较
5. Daniel Lemirea, Leonid Boytsov. Decoding billions of integers per second through vectorization.
6. Thorup Mikkel. Undirected single-source shortest paths with positive integer weights in linear time.
7. Xuanhua Shi, Xuan Luo, Junling Liang etc. Frog: Asynchronous Graph Processing on GPU with Hybrid Coloring Model.
8. Xuanhua Shi, Zhigao Zheng, Yongluan Zhou etc. Graph Processing on GPUs: A Survey.
9. Merrill Duane, Garland Michael, Grimshaw Andrew. High-Performance and Scalable GPU Graph Traversal.
10. Sakr Sherif, Pardede Eric. Graph Data Management: Techniques and Applications.