v2.0 Query Evaluation

The main feature of this major release is the introduction of a complete highly optimised and easily extensible query evaluation pipeline for CPQ and RPQ queries, essentially turning gMark into a simple Graph Database. This pipeline is built on top of the abstract syntax trees (AST), introduced in the previous release and makes use of the theory introduced in: Graph Database & Query Evaluation Terminology.

Some key features:

• A complete query evaluation pipeline for CPQ and RPQ queries:
  • The pipeline has support for evaluating the following operations: concatenation/join, intersection/conjunction, forward/inverse edge/label traversal, identity, Kleene/transitive closure, and disjunction.
  • Any AST representing a reachability query built from these operations can be evaluated by the evaluation pipeline.
  • In addition, the evaluation pipeline also natively supports bound source and/or target nodes for queries.
  • The evaluation pipeline was also built with performance in mind and uses efficient data structures and algorithms.
• The CLI interface was extended to handle query evaluation:
  • You can either evaluate a single query or pass an entire workload of queries to evaluate.
  • The existing workload generation CLI client is still available and was cleaned up a bit.
• The GUI interface was extended for query evaluation:
  • Queries can easily be constructed and evaluated directly in the GUI.
  • Command line instructions for query evaluation are also available in the GUI as well as a small sample graph.
• Various new internal utilities/changes:
  • Most notably the query evaluation pipeline can be used programmatically.
  • Some additional convenience methods were added to parse queries (optionally with known label sets).
  • The random RPQ generator was updated to not generate directly nested transitive closures (i.e., ((q)*)*).
  • Some additional utility methods were added for RPQ construction.
  • An efficient bit set implementation was added to the utilities.
  • Utilities were added to read graphs and query workloads from files.
  • An adjacency list based directed labelled graph implementation was added to the utilities (with integer based vertices and labels).
  • The internals were also restructured to better fit the current setup of gMark.

Downloads

Requires Java 17 or higher

• Windows executable
• Runnable Java Archive

v1.3 Operations & RPQ

This release focusses on making all the components that make up a query language more explicit and identifiable by introducing operations. This is an important step towards bridging the gap between the query language theory and evaluation in a database. A short report was also written to explain the general concepts and terminology in more detail: Graph Database & Query Evaluation Terminology.

Notable changes:

• Fully implement support for RPQ as a query language complete with its own API:
  • Support for programmatically constructing RPQs.
  • Support for parsing RPQs from text.
  • Support for random RPQ generation.
  • Support for RPQ to SQL conversion.
• Implement abstract syntax trees (AST), which CPQ and RPQ can be converted to (and constructed from).
• Prettier SQL output (properly indented now and no longer a single line).
• Add formal as an output format for the formal logic form of queries.
• Support xml as an output format for individually exporting queries as XML.
• Update the readme to better match the current state of the repository.
• Make it clear in the GUI that RPQ workloads are not yet supported.
• Build & project setup improvements.

v1.2 CPQ Cores

This release again focuses on introducing a number of CPQ related utilities, most notably CPQ core computation. These features were added for use in my Master's Thesis project.

Notable changes:

• CPQ Core computation.
• CPQ Homomorphism testing.
• The Graph class was renamed to UniqueGraph.
• Added SimpleGraph which is more performant than UniqueGraph but also limited to unlabelled undirected graphs without parallel edges.
• Tree implementation for tree graphs.
• Various utility extensions to the existing CPQ and QueryGraphCPQ APIs.
  • Getting the diameter of a CPQ.
  • Checking if a CPQ is a loop.
  • More CPQ construction subroutines.
  • Option to reverse a query graph.
  • Support for parsing text form CPQs.
• GraphPanel now supports undirected graphs.
• GraphPanel factory methods to quickly show CPQs/query graphs/unique graphs.
• Tree decomposition algorithm implementation for graphs of treewidth at most 2.
• Support to copy unique graphs, rename nodes in them and restore deleted edges.
• Maximal matching algorithm implementation
• Cartesian product algorithm implementation
• All subsets algorithm implementation.
• Update to Java 17 and minor code improvements.

v1.1 CPQ Utilties

This release includes various utilities for working with CPQs. Notably, random CPQ generation and CPQ query graph generation. Most of these features were introduced for the CPQ Keys project: https://cpqkeys.roanh.dev/

v1.0 Initial Release

The initial public release of the gMark rewrite. This version only has support for CPQ based queries but does provide a graphical interface. There is no support for graph generation or RPQ based queries in this version.