Graph Object Functional Dependencies

To express the dependencies in an LPG relevant for normalization, in addition to the expressions used in the paper, we defined an ASCII syntax, whose grammar is shown below.

For the evaluation in the paper, we implemented the GO-FDs in form of a Python package, which can be found here.

Grammar

For parsing GO-FDs an ANTLR grammar has been written, which is shown below. The Python implementation of GO-FDs (:class:gnfd.GNFD) is relying on this grammar.

grammar gnfd ;

AMPERSAND : '&' ;
COLON : ':' ;
COMMA : ',' ;
DASH : '-' ;
DETERMINES : '=>' ;
DOT : '.' ;
IDENTIFIER : [a-zA-Z] ([a-zA-Z0-9] | '_')* ;
LANGLE: '<' ;
LBRACK : '[' ;
LPAR : '(' ;
RANGLE : '>' ;
RBRACK : ']' ;
RPAR : ')' ;

dependency : pattern COLON COLON left DETERMINES right EOF ;

left : reference (COMMA reference)* ;

right : reference (COMMA reference)* ;

reference : varName | property ;

property : varName DOT propertyKey ;

pattern: nodePattern
        | pattern LANGLE DASH LBRACK varName? ((labelList propertyList?) | (COLON propertyList))? RBRACK DASH pattern
        | pattern DASH LBRACK varName? ((labelList propertyList?) | (COLON propertyList))? RBRACK DASH RANGLE pattern
        | pattern COMMA pattern ;

labelList : COLON label (AMPERSAND label)* ;

propertyList : COLON propertyKey (AMPERSAND propertyKey)* ;

label : IDENTIFIER ;

varName : IDENTIFIER ;

propertyKey : IDENTIFIER ;

nodePattern : LPAR varName? ((labelList propertyList?) | (COLON propertyList))? RPAR ;