Repository: cayleygraph/cayley
Pull request #905 (2019-12-28 13:41:56)

LinkedQL: Match
Depends on #904 
Define a `Match` step in LinkedQL that accepts a subgraph pattern and return entities matching the graph.
Example:
```go
Vertex().Match({ "http://example.org/likes": "http://example.org/bob" })
```
Will return all the entities which have a property pointing to Bob.

<!-- Reviewable:start -->
---
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/cayleygraph/cayley/905)
<!-- Reviewable:end -->


iddan: Quoting the Zen of Python: "There should be one—and preferably only one—obvious way to do it.". Should we remove steps that can be replaced with `.match()`?
Steps that can be replaced with `.match()`:
 - `.Is()`
 - `.Entity()`
 - `.Entities()`
 - `.Has()`
 - `.HasReverse()`

Patch:
diff --git a/internal/linkedql/schema/schema.go b/internal/linkedql/schema/schema.go
index b3c3aab..575f6c9 100644
--- a/internal/linkedql/schema/schema.go
+++ b/internal/linkedql/schema/schema.go
@@ -3,6 +3,7 @@ package schema
 import (
 	"encoding/json"
 	"reflect"
+	"strconv"
 
 	"github.com/cayleygraph/cayley/query/linkedql"
 	_ "github.com/cayleygraph/cayley/query/linkedql/steps"
@@ -13,6 +14,13 @@ import (
 	"github.com/cayleygraph/quad/voc/xsd"
 )
 
+// rdfgGraph is the W3C type for named graphs
+const (
+	rdfgNamespace = "http://www.w3.org/2004/03/trix/rdfg-1/"
+	rdfgPrefix    = "rdfg:"
+	rdfgGraph     = rdfgPrefix + "Graph"
+)
+
 var (
 	pathStep         = reflect.TypeOf((*linkedql.PathStep)(nil)).Elem()
 	iteratorStep     = reflect.TypeOf((*linkedql.IteratorStep)(nil)).Elem()
@@ -21,12 +29,16 @@ var (
 	operator         = reflect.TypeOf((*linkedql.Operator)(nil)).Elem()
 	propertyPath     = reflect.TypeOf((*linkedql.PropertyPath)(nil)).Elem()
 	stringMap        = reflect.TypeOf(map[string]string{})
+	graphPattern     = reflect.TypeOf(linkedql.GraphPattern(nil))
 )
 
 func typeToRange(t reflect.Type) string {
 	if t == stringMap {
 		return "rdf:JSON"
 	}
+	if t == graphPattern {
+		return rdfgGraph
+	}
 	if t.Kind() == reflect.Slice {
 		return typeToRange(t.Elem())
 	}
@@ -89,6 +101,46 @@ func newSingleCardinalityRestriction(prop string) cardinalityRestriction {
 	}
 }
 
+type owlPropertyRestriction struct {
+	ID       string     `json:"@id"`
+	Type     string     `json:"@type"`
+	Property identified `json:"owl:onProperty"`
+}
+
+func newOWLPropertyRestriction(prop string) owlPropertyRestriction {
+	return owlPropertyRestriction{
+		ID:       newBlankNodeID(),
+		Type:     owl.Restriction,
+		Property: identified{ID: prop},
+	}
+}
+
+// minCardinalityRestriction is used to indicate a how many values can a property get at the very least
+type minCardinalityRestriction struct {
+	owlPropertyRestriction
+	MinCardinality int `json:"owl:minCardinality"`
+}
+
+// maxCardinalityRestriction is used to indicate a how many values can a property get at most
+type maxCardinalityRestriction struct {
+	owlPropertyRestriction
+	MaxCardinality int `json:"owl:maxCardinality"`
+}
+
+func newMinCardinalityRestriction(prop string, minCardinality int) minCardinalityRestriction {
+	return minCardinalityRestriction{
+		owlPropertyRestriction: newOWLPropertyRestriction(prop),
+		MinCardinality:         minCardinality,
+	}
+}
+
+func newSingleMaxCardinalityRestriction(prop string) maxCardinalityRestriction {
+	return maxCardinalityRestriction{
+		owlPropertyRestriction: newOWLPropertyRestriction(prop),
+		MaxCardinality:         1,
+	}
+}
+
 // getOWLPropertyType for given kind of value type returns property OWL type
 func getOWLPropertyType(kind reflect.Kind) string {
 	if kind == reflect.String || kind == reflect.Bool || kind == reflect.Int64 || kind == reflect.Int {
@@ -191,8 +243,22 @@ func (g *generator) addTypeFields(name string, t reflect.Type, indirect bool) []
 			continue
 		}
 		prop := linkedql.Prefix + f.Tag.Get("json")
+		var hasMinCardinality bool
+		v, ok := f.Tag.Lookup("minCardinality")
+		if ok {
+			minCardinality, err := strconv.Atoi(v)
+			if err != nil {
+				panic(err)
+			}
+			hasMinCardinality = true
+			super = append(super, newMinCardinalityRestriction(prop, minCardinality))
+		}
 		if f.Type.Kind() != reflect.Slice {
-			super = append(super, newSingleCardinalityRestriction(prop))
+			if hasMinCardinality {
+				super = append(super, newSingleMaxCardinalityRestriction(prop))
+			} else {
+				super = append(super, newSingleCardinalityRestriction(prop))
+			}
 		}
 		typ := getOWLPropertyType(f.Type.Kind())
 
@@ -289,6 +355,7 @@ func (g *generator) Generate() []byte {
 			"owl":      owl.NS,
 			"xsd":      xsd.NS,
 			"linkedql": linkedql.Namespace,
+			"rdfg":     rdfgNamespace,
 		},
 		"@graph": graph,
 	})
diff --git a/query/linkedql/graph_pattern.go b/query/linkedql/graph_pattern.go
new file mode 100644
index 0000000..ad481df
--- /dev/null
+++ b/query/linkedql/graph_pattern.go
@@ -0,0 +1,4 @@
+package linkedql
+
+// GraphPattern represents a JSON-LD document
+type GraphPattern = map[string]interface{}
diff --git a/query/linkedql/registry.go b/query/linkedql/registry.go
index 260380e..ebcc11d 100644
--- a/query/linkedql/registry.go
+++ b/query/linkedql/registry.go
@@ -52,6 +52,7 @@ func Register(typ RegistryItem) {
 }
 
 var (
+	graphPattern   = reflect.TypeOf(GraphPattern(nil))
 	quadValue      = reflect.TypeOf((*quad.Value)(nil)).Elem()
 	quadSliceValue = reflect.TypeOf([]quad.Value{})
 	quadIRI        = reflect.TypeOf(quad.IRI(""))
@@ -90,6 +91,14 @@ func Unmarshal(data []byte) (RegistryItem, error) {
 		}
 		fv := item.Field(i)
 		switch f.Type {
+		case graphPattern:
+			var a interface{}
+			err := json.Unmarshal(v, &a)
+			if err != nil {
+				return nil, err
+			}
+			fv.Set(reflect.ValueOf(a))
+			continue
 		case quadValue:
 			var a interface{}
 			err := json.Unmarshal(v, &a)
diff --git a/query/linkedql/steps/match.go b/query/linkedql/steps/match.go
new file mode 100644
index 0000000..da2bedf
--- /dev/null
+++ b/query/linkedql/steps/match.go
@@ -0,0 +1,127 @@
+package steps
+
+import (
+	"fmt"
+
+	"github.com/cayleygraph/cayley/graph"
+	"github.com/cayleygraph/cayley/query"
+	"github.com/cayleygraph/cayley/query/linkedql"
+	"github.com/cayleygraph/cayley/query/path"
+	"github.com/cayleygraph/quad"
+	"github.com/cayleygraph/quad/jsonld"
+	"github.com/cayleygraph/quad/voc"
+	"github.com/cayleygraph/quad/voc/rdf"
+	"github.com/cayleygraph/quad/voc/rdfs"
+)
+
+func init() {
+	linkedql.Register(&Match{})
+}
+
+var _ linkedql.IteratorStep = (*Match)(nil)
+var _ linkedql.PathStep = (*Match)(nil)
+
+// Match corresponds to .has().
+type Match struct {
+	From    linkedql.PathStep     `json:"from" minCardinality:"0"`
+	Pattern linkedql.GraphPattern `json:"pattern"`
+}
+
+// Description implements Step.
+func (s *Match) Description() string {
+	return "filters all paths which are, at this point, on the subject for the given predicate and object, but do not follow the path, merely filter the possible paths. Usually useful for starting with all nodes, or limiting to a subset depending on some predicate/value pair."
+}
+
+// BuildIterator implements linkedql.IteratorStep.
+func (s *Match) BuildIterator(qs graph.QuadStore, ns *voc.Namespaces) (query.Iterator, error) {
+	return linkedql.NewValueIteratorFromPathStep(s, qs, ns)
+}
+
+// BuildPath implements linkedql.PathStep.
+func (s *Match) BuildPath(qs graph.QuadStore, ns *voc.Namespaces) (*path.Path, error) {
+	var p *path.Path
+	if s.From != nil {
+		fromPath, err := s.From.BuildPath(qs, ns)
+		if err != nil {
+			return nil, err
+		}
+		p = fromPath
+	} else {
+		p = path.StartPath(qs)
+	}
+
+	// Get quads
+	quads, err := parsePattern(s.Pattern, ns)
+
+	if err != nil {
+		return nil, err
+	}
+
+	// Group quads to subtrees
+	entities := make(map[quad.Value]map[quad.Value][]quad.Value)
+	for _, q := range quads {
+		entity := linkedql.AbsoluteValue(q.Subject, ns)
+		property := linkedql.AbsoluteValue(q.Predicate, ns)
+		value := linkedql.AbsoluteValue(q.Object, ns)
+		properties, ok := entities[entity]
+		if !ok {
+			properties = make(map[quad.Value][]quad.Value)
+			entities[entity] = properties
+		}
+		if isSingleEntityQuad(q) {
+			continue
+		}
+		properties[property] = append(properties[property], value)
+	}
+
+	for entity, properties := range entities {
+		if iri, ok := entity.(quad.IRI); ok {
+			p = p.Is(iri)
+		}
+		// FIXME(iddan): this currently flattens all nested objects, which is totally incorrect; recurse or limit allowed json-ld
+		for property, values := range properties {
+			p = p.Has(property, values...)
+		}
+	}
+
+	return p, nil
+}
+
+func parsePattern(pattern linkedql.GraphPattern, ns *voc.Namespaces) ([]quad.Quad, error) {
+	context := make(map[string]interface{})
+	for _, namespace := range ns.List() {
+		context[namespace.Prefix] = namespace.Full
+	}
+	patternClone := linkedql.GraphPattern{
+		"@context": context,
+	}
+	for key, value := range pattern {
+		patternClone[key] = value
+	}
+	reader := jsonld.NewReaderFromMap(patternClone)
+	quads, err := quad.ReadAll(reader)
+	if err != nil {
+		return nil, err
+	}
+	if id, ok := patternClone["@id"]; ok && len(quads) == 0 {
+		idString, ok := id.(string)
+		if !ok {
+			return nil, fmt.Errorf("Unexpected type for @id %T", idString)
+		}
+		quads = append(quads, makeSingleEntityQuad(quad.IRI(idString)))
+	}
+	if len(quads) == 0 && len(pattern) != 0 {
+		return nil, fmt.Errorf("Pattern does not parse to any quad. `{}` is the only pattern allowed to not parse to any quad")
+	}
+	return quads, nil
+}
+
+func makeSingleEntityQuad(id quad.IRI) quad.Quad {
+	return quad.Quad{Subject: id, Predicate: quad.IRI(rdf.Type), Object: quad.IRI(rdfs.Resource)}
+}
+
+func isSingleEntityQuad(q quad.Quad) bool {
+	// rdf:type rdfs:Resource is always true but not expressed in the graph.
+	// it is used to specify an entity without specifying a property.
+	return q.Predicate == quad.IRI(rdf.Type) && q.Object == quad.IRI(rdfs.Resource)
+}


Test patch:
diff --git a/query/linkedql/steps/steps_test.go b/query/linkedql/steps/steps_test.go
index 629e658..99aea0d 100644
--- a/query/linkedql/steps/steps_test.go
+++ b/query/linkedql/steps/steps_test.go
@@ -596,6 +596,35 @@ var testCases = []struct {
 			map[string]string{"@id": "http://example.org/alice"},
 		},
 	},
+	{
+		name: "Match @id",
+		data: []quad.Quad{
+			quad.MakeIRI("http://example.org/alice", "http://example.org/likes", "http://example.org/bob", ""),
+			quad.MakeIRI("http://example.org/bob", "http://example.org/likes", "http://example.org/alice", ""),
+		},
+		query: &Match{
+			From:    &Vertex{},
+			Pattern: linkedql.GraphPattern{"@id": "http://example.org/alice"},
+		},
+		results: []interface{}{
+			map[string]string{"@id": "http://example.org/alice"},
+		},
+	},
+	{
+		name: "Match property",
+		data: []quad.Quad{
+			quad.MakeIRI("http://example.org/alice", "http://example.org/likes", "http://example.org/bob", ""),
+			quad.MakeIRI("http://example.org/bob", "http://example.org/likes", "http://example.org/alice", ""),
+		},
+		query: &Match{
+			From:    &Vertex{},
+			Pattern: linkedql.GraphPattern{"http://example.org/likes": map[string]interface{}{"@id": "http://example.org/alice"}},
+		},
+		results: []interface{}{
+			map[string]string{"@id": "http://example.org/bob"},
+		},
+	},
+	// FIXME(iddan): add test for match nested objects.
 }
 
 func TestLinkedQL(t *testing.T) {