CFPQ_Data

Graphs and grammars for experimental analysis of context-free path querying algorithms.

Prerequirements

• GCC
• Python 3

Installing

python3 -m pip install cfpq_data
python3
>>> import cfpq_data
>>> help(cfpq_data)

Integration with Neo4j

To load RDF data into Neo4j database one can use Neosemantix plugin for Neo4j.

Dataset

Set contains both real-world data and synthetic graphs for several specific cases. All graphs are represented in RDF format to unify loading process.

Query format

Queries are represented as context-free grammars in the following format:

• Line 0: a set of variable symbols delimited by spaces, the first one is the starting symbol

• Line 1: a set of terminal symbols delimited by spaces

• The rest of the lines are productions in the form:

  head -> body | body | ... | body

  where each body can contain basic regular expression, allowed operators:

  • The concatenation, the default operator, which can by represented either by a space or a dot (.)
  • The union, represented by |
  • The ? quantifier
  • The kleene star, represented by *

  Epsilon symbol should be represented by eps

Example query in such format:

S
a b
S -> a S b S
S -> eps

Grammar can be converted to CNF with src/tools/grammar2cnf, which uses pyformlang library to perform context-free grammar modifications.

$ python3 main.py grammar2cnf file [PATH_TO_GRAMMAR] --output [PATH_TO_OUTPUT]

Dataset structure

Graphs and grammars can be found in data — all graphs are divided into groups, which are placed in different directories. Each data/[GroupName]/Matrices contains graph descriptions and data/[GroupName]/Grammars — descriptions of queries.

RDF — fixed versions of real-world RDF files (links are provided for updating purposes only!):

• Small graphs is a set of popular semantic web ontologies. This set is introduced by Xiaowang Zhang in "Context-Free Path Queries on RDF Graphs" :

  • skos
  • foaf
  • wine
  • pizza
  • generations
  • travel
  • univ-bench
  • people-pets

• Bigger graphs:

  • geospecies – graph related to taxonomic hierarchy and geographical information of animal species, download here: http://rdf.geospecies.org/geospecies.rdf.gz. Introduced in "An Experimental Study of Context-Free Path Query Evaluation Methods"
  • a set of graphs from the Uniprot protein sequences database, download here: ftp://ftp.uniprot.org/pub/databases/uniprot/current_release/rdf
    • go
    • go-hierarchy
    • pathways
    • taxonomy
    • taxonomy-hierarchy
    • core
    • enzime
  • eclass_514en

Grammars list contains the following variants of same-generation query over different relation tipes.

• g1 — same-generation query over type and subclass-of relations. Introduced in "Context-Free Path Queries on RDF Graphs"
• g2 — same-generation query over type and subclass-of relations. Introduced in "Context-Free Path Queries on RDF Graphs"
• geo — same-generation query over broader-transitive relation.

MemoryAliases — real-world data for points-to analysis of C code.

• First part is a dataset form Graspan tool. The original data is placed here. This part is placed in Graspan folder.
• Second part is a part of dataset form "Demand-driven alias analysis for C". This part is placed in small folder.

Both grammars g1 and g2 specify the same language which is described in related papers. These two grammars were written in a different way in order to investigate dependencies on query specification format.

WorstCase — graphs with two cylces; the query Brackets is a grammar for the language of correct bracket sequences.

SparseGraph — graphs generated with NetworkX to emulate sparse data. The grammar provided is a variant of the same-generation query.

ScaleFree — graphs generated by using the Barab'asi-Albert model of scale-free networks. Use with grammar ** an_bm_cm_dn**, which is a query for A_nB_mC_mD_n language.

FullGraph — cycle graphs, all edges are labeled with the same token. Use with A_star queries, which produce full graph on that dataset.

LUBM - the Lehigh University Benchmark graphs.

Graphs information

RDF

MemoryAliases

Papers on CFPQ

List of CFPQ-related works. The list is not full, work in progress.

Graph databases

• M. Yannakakis. "Graph-theoretic methods in database theory".
• P. Sevon and L. Eronen. "Subgraph queries by context-free grammars".
• J. Kuijpers, G. Fletcher, N. Yakovets, and T. Lindaaker. "An experimental study of context-free path query evaluation methods".
• H. Miao and A. Deshpande. "Understanding Data Science Lifecycle Provenance via Graph Segmentation and Summarization".
• TBD

Static code analysis

• T. Reps. "Program analysis via graph reachability".
• X. Zheng and R. Rugina. "Demand-driven alias analysis for C".
• TBD

Papers using this dataset

• Evaluation of the Context-Free Path Querying Algorithm Based on Matrix Multiplication