I would suggest that Google does not have its own intelligence. If I search for say ‘Arnold Schwarzenegger and Harvard’, Google will only suggest documents that contain BOTH Arnold Schwarzenegger and Harvard. I might be lucky that someone has digested these facts and produced a single web page with the knowledge I want. I might, however, just as easily find a page of fake knowledge relating Arnold to Harvard.

It is undoubtedly true that Google can provide individual facts such as:

  1. Arnold married to Shriver
  2. Shriver daughter Joseph
  3. Joseph alma mater Harvard

However, intelligence is the ability to connect individual facts into knowledge.

Graph models can provide the facts to answer these questions. PathPatternQL provides an easy way to discover knowledge by describing paths through these facts.

Genealogical Example

Genealogy is a grandfather of graphs, it is therefore natural to organize family trees as a knowledge graph.  A typical PathPatternQL question to ask would then be: who are the parents of a maternal grandfather, born in Maidstone, of this individual? 

Industrial Internet of Things (IIoT) Example

Industrial Internet of Things (IIot) are best modelled as an interconnected graph of ‘thing’ nodes. These things might be sensors producing measurements, the equipment to which the sensors are attached, or how the equipment is interconnected to form a functioning plant. However the ‘intelligence’ about why the plant is interconnected is what an experienced (aka intelligent, knowledgable) process engineer offers. To support such intelligence with a knowledge graph requires answering PathPatternQL questions such as

  1. If the V101 bottoms pump stops how does this affect the product flow from this production unit?
  2. If the FI101 instrument fails how does this affect the boiler feed temperature?
  3. What upstream could possibly be affecting this streams quality?
  4. … and so on.

Why PathPatternQL?

SPARQL is a superb graph pattern query language, so why create another?

PathPatternQL started out as the need to traverse the nodes and edges in a triplestore both without the benefit of SPARQL and within a scripting language: IntelligentGraph. IntelligentGraph works by embedding the calculations within the graph. Therefore, just like a spreadsheet calculation can access other ‘cells’ within its spreadsheet, IntelligentGraph needed a way of traversing the graph through interconnected nodes and edges to other nodes from where relevant values can be retrieved.

I didn’t want to create a new language, but it was essential that the IntelligentGraphprovided a very easy way to navigate a path through a graph. It then became clear that, as powerful as SPARQL is for graph pattern matching, it can be verbose for matching path patterns. PathPatternQL was born, but not without positive prodding from my colleague Phil Ashworth.

Path Patterns

PathPatterns are inspired by SPARQL and propertyPaths, but a richer, more expressive, pathPattern was required for the IntelligentGraph. It is best explained by examples.

PathPattern Examples

Examples of pathPatterns, used as a argument to IntelligentGraph getFact function,  are as follows:

$this.getFact(“:hasParent”)

will return the first parent of $this.

$this.getFact(“^:hasParent”)

will return the first child of $this.

$this.getFacts(“:hasParent/:hasParent”)

will return the grandparents of $this.

$this.getFacts(“:hasParent/^:hasParent”)

will return the siblings of $this.

$this.getFacts(“:hasParent[:gender :female]/:hasParent”)

will return the maternal grandparents of $this

$this.getFacts(“:hasParent[:gender :female]/:hasParent[:gender :male]”)

will return the maternal grandfather of $this.

$this.getFacts(“:hasParent[:gender [ rdfs:label “female”]]”)

will return the mother of $this but using the label instead of the IRI.

$this.getFacts(“:hasParent[eq :Peter]/:hasParent[:gender :male]”)

will return the grandfather of $this, who is the parent of :Peter.

$this.getFacts(“:hasParent[ne :Peter]/:hasParent[:gender :male]”)

will return grandfathers of $this, who are not the parent of :Peter.

The following diagram visualizes a path through a genealogical graph, from $this to the find the parents of a maternal grandfather born in Maidstone:

$this.getFacts(“:parent[:gender :female]/:parent[:gender :male, :birthplace [rdfs:label ‘Maidstone’]]/:parent”)

 

Figure 1: PathPatternQL Example

Formal Syntax

The parts of a PathPattern are defined below. The formal syntax in BNF is here: PathPattern Formal Syntax

IRIRef:

The simplest pathPattern is an IRI of the predicate, property, or edge:

:hasParent

An un-prefixed qname using the default namespace.

ft:hasParent

A prefixed qname using the namespace model.

<http://inova8.com/ft/hasParent>

A full IRI.

PathAlternative:

A pathPattern can consist of a set of alternative edges:

:hasParent|:hasChild

Alternative edges  to ‘close relatives’ of the :subjectThing.

PathSequence:

A pathPattern can consist of a sequence of edges:

:hasParent/:hasChild

 sequence of edges to the set of siblings of the start thing.

Inverse Modifier:

A modifier prefix to a predicate indicating that it should be navigated in the reverse direction (object to subject) instead of subject to object:

:hasParent/^:hasParent

 A sequence of edges to the set of siblings of the start thing since ^:hasParent is equivalent to :hasChild.

Reified Modifier:

A modifier prefix to a predicate indicating that it should be assumed that the subject-predicate-object is reified.

@:marriedTo

navigates from the :subjectThing to the :objectThing when the edge has been reified as: 

[] rdf:subject :subjectThing ;
   rdf:predicate :marriedTo ;
   rdf:object :objectThing .

Inverse modifier can also be applied to navigate from the :objectThing to :subjectthing:

^@:marriedTo

navigates from the :objectThing to the :subjectThing

Extended Reification Modifier:

The reification type and the predicate of an extended reification:

:Marriage@:civilPartnership

navigates from the :subjectThing to the :objectThing when the edge has been reified as a class that is a :Marriage, which is rdfs:subClassOf rdf:Statement with a predicate of :civilPartnership. For example: 

 [] a :Marriage
   :partner :subjectThing ;
   :marriageType :civilPartnership ;
   :otherPartner :objectThing .

:partner :rdf:subPropertyOf rdf:subject .
:marriageType :rdf:subPropertyOf rdf:predicate.
:otherPartner :rdf:subPropertyOf rdf:object .

An inverse modifier can also be applied to navigate from the :objectThing to :subjectThing

^:Marriage@:marriedTo

navigates from the :objectThing to the :subjectThing in the extended reification.

Dereification Modifier:

Instead of navigating to the objectThing of a reification, the dereification operator navigates to the reification thing:

@:marriedTo#

navigates from the :subjectThing to the :marriage object.

@:marriedTo#/:at

navigates from the :subjectThing to the location :at which the marriage took place

@:marriedTo#/:when

navigates from the :subjectThing to the date :when the marriage took place

Path Filter:

A path filter can be applied to any point in a pathPattern to limit the subsequent paths. A path filter is like a SPARQL PropertyListNotEmpty graph pattern. However, it includes comparison operators lt, gt etc

:hasParent[:gender :male]

Navigates to the male parent.

:hasParent[:gender :male]/:hasParent[:gender :female]

Navigates to the paternal grandmother.

:volumeFlow[gt “50”]

Navigates only if the value is greater than “50”.

:appearsOn[eq :calc2graph1]

Navigates only if the objectNode value is :calc2graph1.

:appearsOn[ eq [rdfs:label "Calc2Graph1"]]

Navigates only if the objectNode is a node whose label is “Calc2Graph1”.

Mapping PathPatternQL to SPARQL

It is important to start that much of  PathPatternQL is nothing more than syntactic sugar for an equivalent SPARQL expression. The mapping is illustrated by the following examples:

Example 1:

PathPattern:

:BatteryLimit1
   ^def:hasFeedBatteryLimit/def:hasProductBatteryLimit
   [ rdfs:label "BatteryLimit3"]
   / def:massFlow

SPARQL Graph Pattern:

{
   VALUES(?this){( :BatteryLimit1 )}
   #Path_1
   ?this ^def:hasFeedBatteryLimit ?n1 .
   ?n1 def:hasProductBatteryLimit ?n2 .
   #Filter
   ?n2  rdfs:label "BatteryLimit3" .
   #Path_2
   ?n2 def:massFlow ?result
}

Example 2:

PathPattern:

:BatteryLimit1
   ^def:hasFeedBatteryLimit/def:hasProductBatteryLimit
   [ ^def:location.of.Item [  def:location.Map [ rdfs:label "Calc2Graph1" ]]] /def:massFlow

SPARQL Graph Pattern:

{
   VALUES(?this){( :BatteryLimit1 )}
   #Path_1
   ?this ^def:hasFeedBatteryLimit ?n1 .
   ?n1 def:hasProductBatteryLimit ?n2 .
   #Filter
   ?n2  ^def:location.of.Item ?n2_f1  .
   ?n2_f1 def:location.Map ?n2_f2 .
   ?n2_f2 rdfs:label "Calc2Graph1" .
   #Path_2
   ?n2 def:massFlow ?n3
}

Example 3:

PathPattern:

:BatteryLimit1
   ^def:hasFeedBatteryLimit/def:hasProductBatteryLimit
   [rdfs:label "BatteryLimit3" ; ^def:location.of.Item [  def:location.Map [ rdfs:label "Calc2Graph1" ]]]
   /def:massFlow

SPARQL Graph Pattern:

{
   VALUES(?this){( :BatteryLimit1 )}
   #Path_1
   ?this ^def:hasFeedBatteryLimit ?n1 .
   ?n1 def:hasProductBatteryLimit ?n2 .
   #Filter
   ?n2  rdfs:label "BatteryLimit3" .
   ?n2  ^def:location.of.Item ?n2_f1  .
   ?n2_f1 def:location.Map ?n2_f2 .
   ?n2_f2 rdfs:label "Calc2Graph1" .
   #Path_2
   ?n2 def:massFlow ?n3
}

PathPatternQL Formal Syntax

The formal syntax of the PathPatternQL is defined as follows using ANTLR4 BNF notation:

grammar PathPattern;
 
pathPattern :            pathPatterns;
pathPatterns :           pathEltOrInverse
                         pathPatterns '|'  pathPatterns 
                         pathPatterns '/'  pathPatterns 
                         '(' pathPatterns ')'  ;
pathEltOrInverse :       INVERSE? predicate ;
predicate :              ( reifiedPredicate | predicateRef | rdfType ) factFilterPattern? ;
reifiedPredicate :       iriRef? REIFIER predicateRef  factFilterPatterndereifier? ;
predicateRef :           IRI_REF  |  qname | pname_ns ;
iriRef  :                IRI_REF  |  qname | pname_ns ; 
dereifier :              DEREIFIER ;
factFilterPattern :      '['  propertyListNotEmpty   ']';
propertyListNotEmpty :   verbObjectList ( ';' ( verbObjectList )? )* ; 
verbObjectList :         verb objectList;
verb :                   operator | pathEltOrInverse ;
objectList :             object ( ',' object )*;
object :                 iriRef  | literal | blankNodePropertyListPath ;
blankNodePropertyListPath: '[' propertyListNotEmpty ']' ;
name :                   PNAME_NS PN_LOCAL;
pname_ns :               PNAME_NS
literal :                LITERAL ;
operator :               OPERATOR ;
rdfType :                RDFTYPE ;

 

// LEXER RULES

INVERSE :                '^';
REIFIER :                '@';
DEREIFIER :              '#';
RDFTYPE :                'a';
OPERATOR :               'lt'|'gt'|'le'|'ge'|'eq'|'ne';
LITERAL:                 '"' (~('"' | '\\' | '\r' | '\n') | '\\' ('"' | '\\'))* '"';
IRI_REF :                '<' ( ~('<' | '>' | '"' | '{' | '}' | '|' | '^' | '\\' | '`')
                         | (PN_CHARS))* '>'
PNAME_NS :               PN_PREFIX? ':'  ;  
VARNAME :                '?' [a-zA-Z]+ ;   
fragment
PN_CHARS_U :             PN_CHARS_BASE | '_' ;
fragment  
PN_CHARS :               PN_CHARS_U
                         | '-'
                         | DIGIT
                         ;
fragment
PN_PREFIX :              PN_CHARS_BASE ((PN_CHARS|'.')* PN_CHARS)? ;
PN_LOCAL :               ( PN_CHARS_U | DIGIT ) ((PN_CHARS|'.')* PN_CHARS)? ;
fragment
PN_CHARS_BASE
                        : 'A'..'Z'
                        | 'a'..'z'
                        | '\u00C0'..'\u00D6'
                        | '\u00D8'..'\u00F6'
                        | '\u00F8'..'\u02FF'
                        | '\u0370'..'\u037D'
                        | '\u037F'..'\u1FFF'
                        | '\u200C'..'\u200D'
                        | '\u2070'..'\u218F'
                        | '\u2C00'..'\u2FEF'
                        | '\u3001'..'\uD7FF'
                        | '\uF900'..'\uFDCF'
                        | '\uFDF0'..'\uFFFD'
                        ;
fragment
DIGIT :                 '0'..'9';
WS :                    [ \t\r\n]+ -> skip

The Future of PathPatternQL

The next step is include path modifiers as proposed in the original propertyPath specification. This will then allow expressions such as answers to the question: find any grandfathers on the maternal line of this individual:

$this.getFacts(“:parent[:gender :female]/:parent[:gender :male]{1,5}”)

Another development is to include shortest paths: what is the path to the first grandfather born in Maidstone:

$this.getPath(":parent{1,*}/:parent[:gender :male, :birthplace [rdfs:label ‘Maidstone’]]")

Leave a Reply