tree-specification-pruning

Tree-specification-pruning

This library allows to prune relations based on the TREE specification.

installation:

``npm install`

usage

`import { canPruneRelation } from 'tree-spec-pruning'

let relation = { '@context': 'https://w3id.org/tree#' '@type': 'tree:PrefixRelation' 'path': 'http://example.com/name' 'value': "Gent" 'node': 'http://example.com/Node2' }

let query = { 'PREFIX rdf: \ PREFIX ex: \ SELECT ?s WHERE { \ ?s ?name ; \ Filter(strstarts(str(?name), "Gent-")) \ } LIMIT 10' }

let result = canPruneRelation(relation, query) // result = true`

Supported SHACL path types used in relations of the TREE specification

| path | supported | JSON-LD example | |------|-----------|-----------------| | shacl:predicatePath | :heavy_check_mark: | 'shacl:path': 'ex:predicate' | | shacl:sequencePath | :heavy_check_mark: | 'shacl:path': { 'rdf:first': 'ex:predicate1','rdf:rest': { 'rdf:first': 'ex:predicate2', 'rdf:rest': 'rdf:nil' } } | | shacl:alternativePath | :heavy_check_mark: | 'shacl:path': { 'shacl:alternativePath': { 'rdf:first': 'ex:predicate1','rdf:rest': { 'rdf:first': 'ex:predicate2', 'rdf:rest': 'rdf:nil' } } } | | shacl:inversePath | :heavy_multiplication_x: | { shacl:path: { 'shacl:inversePath': 'ex:predicate' } } | | shacl:zeroOrOnePath | :heavy_multiplication_x: | { shacl:path: { 'shacl:zeroOrOnePath': 'ex:predicate' } } | | shacl:zeroOrMorePath | :heavy_multiplication_x: | { shacl:path: { 'shacl:zeroOrMorePath': 'ex:predicate' } } | | shacl:oneOrMorePath | :heavy_multiplication_x: | { shacl:path: { 'shacl:oneOrMorePath': 'ex:predicate' } } |

Supported SPARQL path expressions that will enable tree pruning

| path | supported | JSON-LD example | |------|-----------|-----------------| | predicate path | :heavy_check_mark: | ex:predicate | | sequence path | :heavy_check_mark: | ex:predicate1 / ex:predicate2| | alternative path | :heavy_check_mark: | ex:predicate1 \| ex:predicate2 | | inverse path | :heavy_multiplication_x: | ^ex:predicate | | zero or one path | :heavy_multiplication_x: | ex:predicate? | | zero or more path | :heavy_multiplication_x: | ex:predicate* | | one or more path | :heavy_multiplication_x: | ex:predicate+ |

Pruning rules (shacl paths written in sparql path syntax for visual clarity!)

| relation path | SPARQL query path | can prune relation| |------|-----------|-----------------| | ex:predicate | ex:predicate | :heavy_check_mark: | | ex:predicate1 | ex:predicate2 | :heavy_multiplication_x: | | ex:predicate1 / ex:predicate2 / ex:predicate3 | ex:predicate1 / ex:predicate2 / ex:predicate3 | :heavy_check_mark: | | ex:predicate2 / ex:predicate3 | ex:predicate1 / ex:predicate2 / ex:predicate3 | :heavy_multiplication_x: | | ex:predicate1 / ex:predicate2 / ex:predicate3 | ex:predicate2 / ex:predicate3 | :heavy_multiplication_x: | | ex:predicate1 / ex:predicate2 / ex:predicate3 | ex:predicate4 / ex:predicate2 / ex:predicate3 | :heavy_multiplication_x: | | ex:predicate1 \| ex:predicate2 | ex:predicate1 \| ex:predicate2 | :heavy_check_mark: | | ex:predicate1 | ex:predicate1 \| ex:predicate2 | :heavy_multiplication_x: | | ex:predicate2 | ex:predicate1 \| ex:predicate2 | :heavy_multiplication_x: | | ex:predicate1 \| ex:predicate2 | ex:predicate1 | :heavy_multiplication_x: | | ex:predicate1 \| ex:predicate2 | ex:predicate2 | :heavy_multiplication_x: |

Notes on pruning rules In the case of sequence paths, a relation can only be pruned if it exactly matches the path of a query. In case the query path is more specific than the relation path: e.g. we query for items with a specific value for a path`ex:city / rdf:label`, we cannot prune a relation with a path `rdf:label`, as this may contain items with a `ex:streetname / rdf:label`property, over which no assumptions can be made. In the case the relation path is more specific than the query path: e.g. we query for items for a path`rdf:label`, a relations with a path `ex:city / rdf:label` cannot be pruned, as it an item may contain both properties `ex:city / rdf:label` and `ex:streetname / rdf:label`, and we cannot make any assumptions over the value of the streetname label, so this relation can not be pruned. Combining both these findings, we can decide that only exact matches in the query path and relation path allow for a relation to be pruned.

In the case of alternative path, we do not entirely follow the SPARQL specification for property paths, that dictates that all possibilities should be tried. This would have as a consequence that when querying for items with a path `rdf:label | foaf:name`, a relation with a path `rdf:label` cannot be pruned, as it may contain items with a `foaf:name`property that does match the given query. Instead, we process an alternative path by trying to match the different paths one by one, from left to right.

If however in a relation an alternative path is specified, this relation can only be pruned in the case that the query also specifies an alternative path where all possible paths of specified int the relation are also specified in the query. If this is not the case: e.g. The relation specifies a path~~`rdf:label | foaf:name`, and the query searches for items matching a value for `rdf:label`, then we cannot prune this relation, as we have no guarantee that an~~

Supported SPARQL filter expressions As SPARQL is an extensive framework, we currently only support a small subset of the filtering functionality that is available to decide whether to prune a relation. This functionality is based on the current relations that are defined in the TREE Specification, and which filter options are relevant to prune relations during the traversal of a search tree.

Type conversions Implementation according to SPARQL1.1 spec :heavy_check_mark: implemented :heavy_multiplication_x: not implemented / impossible :question: dependent on lexical value

Implemented functions and compatibility

| datatype \ Compatible relation | PrefixRelation | SubstringRelation | LesserThanRelation | LesserThanOrEqualRelation | EqualsRelation | GreaterOrEqualThanRelation | GreaterThanRelation | GeospatiallyContainsRelation | |--|--|--|--|--|--|--|--|--| | xsd:string | |

Support for UNION is currently not yet implemented.

Tree-specification-pruning

This library allows to prune relations based on the TREE specification.

installation:

`` npm install `

usage

` import { canPruneRelation } from 'tree-spec-pruning'

let relation = { '@context': 'https://w3id.org/tree#' '@type': 'tree:PrefixRelation' 'path': 'http://example.com/name' 'value': "Gent" 'node': 'http://example.com/Node2' }

let query = { 'PREFIX rdf: \ PREFIX ex: \ SELECT ?s WHERE { \ ?s ?name ; \ Filter(strstarts(str(?name), "Gent-")) \ } LIMIT 10' }

let result = canPruneRelation(relation, query) // result = true `

Supported SHACL path types used in relations of the TREE specification

Supported SPARQL path expressions that will enable tree pruning

Pruning rules (shacl paths written in sparql path syntax for visual clarity!)

Notes on pruning rules In the case of sequence paths, a relation can only be pruned if it exactly matches the path of a query. In case the query path is more specific than the relation path: e.g. we query for items with a specific value for a path `ex:city / rdf:label`, we cannot prune a relation with a path `rdf:label`, as this may contain items with a `ex:streetname / rdf:label` property, over which no assumptions can be made. In the case the relation path is more specific than the query path: e.g. we query for items for a path `rdf:label`, a relations with a path `ex:city / rdf:label` cannot be pruned, as it an item may contain both properties `ex:city / rdf:label` and `ex:streetname / rdf:label`, and we cannot make any assumptions over the value of the streetname label, so this relation can not be pruned. Combining both these findings, we can decide that only exact matches in the query path and relation path allow for a relation to be pruned.

In the case of alternative path, we do not entirely follow the SPARQL specification for property paths, that dictates that all possibilities should be tried. This would have as a consequence that when querying for items with a path `rdf:label | foaf:name`, a relation with a path `rdf:label` cannot be pruned, as it may contain items with a `foaf:name` property that does match the given query. Instead, we process an alternative path by trying to match the different paths one by one, from left to right.

If however in a relation an alternative path is specified, this relation can only be pruned in the case that the query also specifies an alternative path where all possible paths of specified int the relation are also specified in the query. If this is not the case: e.g. The relation specifies a path `rdf:label | foaf:name`, and the query searches for items matching a value for `rdf:label`, then we cannot prune this relation, as we have no guarantee that an

Type conversions Implementation according to SPARQL1.1 spec :heavy_check_mark: implemented :heavy_multiplication_x: not implemented / impossible :question: dependent on lexical value

Implemented functions and compatibility

Support for UNION is currently not yet implemented.