Repository: cayleygraph/cayley
Pull request #876 (2019-10-16 11:15:50)

Inference
This PR implements an in-memory store for the RDFS type system and functions used for inference.
`inference_test` covers 100% of the statements to make sure no edge case is missed.

<!-- 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/876)
<!-- Reviewable:end -->


iddan: @dennwc I think it is ready for rereview

Patch:
diff --git a/inference/inference.go b/inference/inference.go
new file mode 100644
index 0000000..4bcd872
--- /dev/null
+++ b/inference/inference.go
@@ -0,0 +1,444 @@
+// Package inference implements an in-memory store for inference.
+//
+// RDFS Rules:
+//
+//		1. (x p y) -> (p rdf:type rdf:Property)
+//		2. (p rdfs:domain c), (x p y) -> (x rdf:type c)
+//		3. (p rdfs:range c), (x p y) -> (y rdf:type c)
+//		4a. (x p y) -> (x rdf:type rdfs:Resource)
+//		4b. (x p y) -> (y rdf:type rdfs:Resource)
+//		5. (p rdfs:subPropertyOf q), (q rdfs:subPropertyOf r) -> (p rdfs:subPropertyOf r)
+//		6. (p rdf:type Property) -> (p rdfs:subPropertyOf p)
+//		7. (p rdf:subPropertyOf q), (x p y) -> (x q y)
+//		8. (c rdf:type rdfs:Class) -> (c rdfs:subClassOf rdfs:Resource)
+//		9. (c rdfs:subClassOf d), (x rdf:type c) -> (x rdf:type d)
+//		10. (c rdf:type rdfs:Class) -> (c rdfs:subClassOf c)
+//		11. (c rdfs:subClassOf d), (d rdfs:subClassOf e) -> (c rdfs:subClassOf e)
+//		12. (p rdf:type rdfs:ContainerMembershipProperty) -> (p rdfs:subPropertyOf rdfs:member)
+//		13. (x rdf:type rdfs:Datatype) -> (x rdfs:subClassOf rdfs:Literal)
+//
+// Exported from: https://www.researchgate.net/figure/RDF-RDFS-entailment-rules_tbl1_268419911
+//
+// Implemented here: 1 5 6 8 10 11
+package inference
+
+import (
+	"github.com/cayleygraph/quad"
+	"github.com/cayleygraph/quad/voc/rdf"
+	"github.com/cayleygraph/quad/voc/rdfs"
+)
+
+// classSet is a set of RDF Classes
+type classSet map[*Class]struct{}
+
+// propertySet is a set of RDF Properties
+type propertySet map[*Property]struct{}
+
+// Class represents a RDF Class with the links to classes and other properties
+type Class struct {
+	store      *Store
+	name       quad.Value
+	explicit   bool
+	references int
+	super      classSet
+	sub        classSet
+	ownProp    propertySet
+	inProp     propertySet
+}
+
+func (s *Store) newClass(name quad.Value, explicit bool) *Class {
+	c := &Class{
+		store:    s,
+		name:     name,
+		explicit: explicit,
+		super:    make(classSet),
+		sub:      make(classSet),
+		ownProp:  make(propertySet),
+		inProp:   make(propertySet),
+	}
+	s.classes[name] = c
+	return c
+}
+
+// Name returns the class's name
+func (c *Class) Name() quad.Value {
+	return c.name
+}
+
+// IsSubClassOf recursively checks whether class is a superClass
+func (c *Class) IsSubClassOf(super *Class) bool {
+	if c == super {
+		return true
+	}
+	if super.name == quad.IRI(rdfs.Resource) {
+		return true
+	}
+	if _, ok := c.super[super]; ok {
+		return true
+	}
+	for s := range c.super {
+		if s.IsSubClassOf(super) {
+			return true
+		}
+	}
+	return false
+}
+
+func (c *Class) isReferenced() bool {
+	return c.explicit || len(c.super) > 0 ||
+		len(c.sub) > 0 ||
+		len(c.ownProp) > 0 ||
+		len(c.inProp) > 0 ||
+		c.references > 0
+}
+
+func (c *Class) deleteIfUnreferenced() {
+	if c != nil && !c.isReferenced() {
+		c.store.deleteClass(c.name)
+	}
+}
+
+// Property represents a RDF Property with the links to classes and other properties
+type Property struct {
+	name       quad.Value
+	explicit   bool
+	references int
+	domain     *Class
+	prange     *Class
+	super      propertySet
+	sub        propertySet
+	store      *Store
+}
+
+func newProperty(name quad.Value, explicit bool, store *Store) *Property {
+	return &Property{
+		name:     name,
+		explicit: explicit,
+		super:    make(propertySet),
+		sub:      make(propertySet),
+		store:    store,
+	}
+}
+
+// Name returns the property's name
+func (p *Property) Name() quad.Value {
+	return p.name
+}
+
+// Domain returns the domain of the property
+func (p *Property) Domain() *Class {
+	return p.domain
+}
+
+// Range returns the range of the property
+func (p *Property) Range() *Class {
+	return p.prange
+}
+
+// IsSubPropertyOf recursively checks whether property is a superProperty
+func (p *Property) IsSubPropertyOf(super *Property) bool {
+	if p == super {
+		return true
+	}
+	if _, ok := p.super[super]; ok {
+		return true
+	}
+	for s := range p.super {
+		if s.IsSubPropertyOf(super) {
+			return true
+		}
+	}
+	return false
+}
+
+func (p *Property) isReferenced() bool {
+	return p.explicit || p.references > 0 ||
+		len(p.super) > 0 ||
+		len(p.sub) > 0
+}
+
+func (p *Property) deleteIfUnreferenced() {
+	if p != nil && !p.isReferenced() {
+		p.store.deleteProperty(p.name)
+	}
+}
+
+// Store is a struct holding the inference data
+type Store struct {
+	classes    map[quad.Value]*Class
+	properties map[quad.Value]*Property
+}
+
+// NewStore creates a new Store
+func NewStore() Store {
+	s := Store{
+		classes:    make(map[quad.Value]*Class),
+		properties: make(map[quad.Value]*Property),
+	}
+	s.ensureClass(quad.IRI(rdfs.Resource))
+	return s
+}
+
+// GetClass returns a class struct for class name, if it doesn't exist in the store then it returns nil
+func (s *Store) GetClass(name quad.Value) *Class {
+	return s.classes[name]
+}
+
+// GetProperty returns a class struct for property name, if it doesn't exist in the store then it returns nil
+func (s *Store) GetProperty(name quad.Value) *Property {
+	return s.properties[name]
+}
+
+func (s *Store) ensureClass(name quad.Value) {
+	if c, ok := s.classes[name]; ok {
+		c.explicit = true
+	} else {
+		_ = s.newClass(name, true)
+	}
+}
+
+func (s *Store) getOrCreateImplicitClass(name quad.Value) *Class {
+	c, ok := s.classes[name]
+	if !ok {
+		c = s.newClass(name, false)
+	}
+	return c
+}
+
+func (s *Store) createProperty(name quad.Value) {
+	if property, ok := s.properties[name]; ok {
+		property.explicit = true
+		return
+	}
+	s.properties[name] = newProperty(name, true, s)
+}
+
+func (s *Store) getOrCreateImplicitProperty(name quad.Value) *Property {
+	if p, ok := s.properties[name]; ok {
+		return p
+	}
+	p := newProperty(name, false, s)
+	s.properties[name] = p
+	return p
+}
+
+func (s *Store) addClassRelationship(child quad.Value, parent quad.Value) {
+	p := s.getOrCreateImplicitClass(parent)
+	c := s.getOrCreateImplicitClass(child)
+	if _, ok := p.sub[c]; !ok {
+		p.sub[c] = struct{}{}
+		c.super[p] = struct{}{}
+	}
+}
+
+func (s *Store) addPropertyRelationship(child quad.Value, parent quad.Value) {
+	p := s.getOrCreateImplicitProperty(parent)
+	c := s.getOrCreateImplicitProperty(child)
+	if _, ok := p.sub[c]; !ok {
+		p.sub[c] = struct{}{}
+		c.super[p] = struct{}{}
+	}
+}
+
+func (s *Store) setPropertyDomain(property quad.Value, domain quad.Value) {
+	p := s.getOrCreateImplicitProperty(property)
+	c := s.getOrCreateImplicitClass(domain)
+	// FIXME(iddan): Currently doesn't support multiple domains as they are very rare
+	p.domain = c
+	c.ownProp[p] = struct{}{}
+}
+
+func (s *Store) setPropertyRange(property quad.Value, prange quad.Value) {
+	p := s.getOrCreateImplicitProperty(property)
+	c := s.getOrCreateImplicitClass(prange)
+	p.prange = c
+	// FIXME(iddan): Currently doesn't support multiple ranges as they are very rare
+	c.inProp[p] = struct{}{}
+}
+
+func (s *Store) addClassInstance(name quad.Value) {
+	c := s.GetClass(name)
+	if c == nil {
+		c = s.getOrCreateImplicitClass(name)
+	}
+	c.references++
+}
+
+func (s *Store) addPropertyInstance(name quad.Value) {
+	p := s.GetProperty(name)
+	if p == nil {
+		p = s.getOrCreateImplicitProperty(name)
+	}
+	p.references++
+}
+
+// ProcessQuads is used to update the store with multiple quads
+func (s *Store) ProcessQuads(quads ...quad.Quad) {
+	for _, q := range quads {
+		s.processQuad(q)
+	}
+}
+
+// processQuad is used to update the store with a new quad
+func (s *Store) processQuad(q quad.Quad) {
+	pred, ok := q.Predicate.(quad.IRI)
+	if !ok {
+		return
+	}
+	sub, obj := q.Subject, q.Object
+	switch pred {
+	case rdf.Type:
+		switch obj := obj.(type) {
+		case quad.BNode:
+			s.addClassInstance(obj)
+		case quad.IRI:
+			switch obj {
+			case rdfs.Class:
+				s.ensureClass(sub)
+			case rdf.Property:
+				s.createProperty(sub)
+			default:
+				s.addClassInstance(obj)
+			}
+		}
+	case rdfs.SubPropertyOf:
+		s.addPropertyRelationship(sub, obj)
+	case rdfs.SubClassOf:
+		s.addClassRelationship(sub, obj)
+	case rdfs.Domain:
+		s.setPropertyDomain(sub, obj)
+	case rdfs.Range:
+		s.setPropertyRange(sub, obj)
+	default:
+		s.addPropertyInstance(pred)
+	}
+}
+
+func (s *Store) deleteClass(name quad.Value) {
+	c, ok := s.classes[name]
+	if !ok {
+		return
+	}
+	for sub := range c.sub {
+		delete(sub.super, c)
+	}
+	for super := range c.super {
+		delete(super.sub, c)
+	}
+	delete(s.classes, name)
+}
+
+func (s *Store) deleteProperty(name quad.Value) {
+	p, ok := s.properties[name]
+	if !ok {
+		return
+	}
+	for super := range p.super {
+		delete(super.sub, p)
+	}
+	for sub := range p.sub {
+		delete(sub.super, p)
+	}
+	delete(s.properties, name)
+}
+
+func (s *Store) deleteClassRel(child quad.Value, parent quad.Value) {
+	p := s.GetClass(parent)
+	c := s.GetClass(child)
+	if _, ok := p.sub[c]; ok {
+		delete(p.sub, c)
+		delete(c.super, p)
+		p.deleteIfUnreferenced()
+		c.deleteIfUnreferenced()
+	}
+}
+
+func (s *Store) deletePropertyRel(child quad.Value, parent quad.Value) {
+	p := s.GetProperty(parent)
+	c := s.GetProperty(child)
+	if _, ok := p.sub[c]; ok {
+		delete(p.sub, c)
+		delete(c.super, p)
+		p.deleteIfUnreferenced()
+		c.deleteIfUnreferenced()
+	}
+}
+
+func (s *Store) unsetPropertyDomain(property quad.Value, domain quad.Value) {
+	p := s.GetProperty(property)
+	c := s.GetClass(domain)
+	// FIXME(iddan): Currently doesn't support multiple domains as they are very rare
+	p.domain = nil
+	delete(c.ownProp, p)
+	p.deleteIfUnreferenced()
+	c.deleteIfUnreferenced()
+}
+
+func (s *Store) unsetPropertyRange(property quad.Value, prange quad.Value) {
+	p := s.GetProperty(property)
+	c := s.GetClass(prange)
+	p.prange = nil
+	// FIXME(iddan): Currently doesn't support multiple ranges as they are very rare
+	delete(c.inProp, p)
+	p.deleteIfUnreferenced()
+	c.deleteIfUnreferenced()
+}
+
+func (s *Store) deleteClassInstance(name quad.Value) {
+	c := s.GetClass(name)
+	if c == nil {
+		return
+	}
+	c.references--
+	c.deleteIfUnreferenced()
+}
+
+func (s *Store) deletePropertyInstance(name quad.Value) {
+	p := s.GetProperty(name)
+	if p == nil {
+		return
+	}
+	p.references--
+	p.deleteIfUnreferenced()
+}
+
+// UnprocessQuads is used to delete multiple quads from the store
+func (s *Store) UnprocessQuads(quads ...quad.Quad) {
+	for _, q := range quads {
+		s.unprocessQuad(q)
+	}
+}
+
+// unprocessQuad is used to delete a quad from the store
+func (s *Store) unprocessQuad(q quad.Quad) {
+	pred, ok := q.Predicate.(quad.IRI)
+	if !ok {
+		return
+	}
+	sub, obj := q.Subject, q.Object
+	switch pred {
+	case rdf.Type:
+		obj, ok := obj.(quad.IRI)
+		if !ok {
+			return
+		}
+		switch obj {
+		case rdfs.Class:
+			s.deleteClass(sub)
+		case rdf.Property:
+			s.deleteProperty(sub)
+		default:
+			s.deleteClassInstance(obj)
+		}
+	case rdfs.SubPropertyOf:
+		s.deletePropertyRel(sub, obj)
+	case rdfs.SubClassOf:
+		s.deleteClassRel(sub, obj)
+	case rdfs.Domain:
+		s.unsetPropertyDomain(sub, obj)
+	case rdfs.Range:
+		s.unsetPropertyRange(sub, obj)
+	default:
+		s.deletePropertyInstance(pred)
+	}
+}


Test patch:
diff --git a/inference/inference_test.go b/inference/inference_test.go
new file mode 100644
index 0000000..e2148f6
--- /dev/null
+++ b/inference/inference_test.go
@@ -0,0 +1,535 @@
+package inference
+
+import (
+	"testing"
+
+	"github.com/cayleygraph/quad"
+	"github.com/cayleygraph/quad/voc/rdf"
+	"github.com/cayleygraph/quad/voc/rdfs"
+	"github.com/stretchr/testify/require"
+)
+
+func triple(subject quad.Value, predicate quad.IRI, object quad.Value) quad.Quad {
+	return quad.Quad{Subject: subject, Predicate: predicate, Object: object}
+}
+
+var (
+	domain           = quad.IRI(rdfs.Domain)
+	prange           = quad.IRI(rdfs.Range)
+	ptype            = quad.IRI(rdf.Type)
+	class            = quad.IRI(rdfs.Class)
+	literal          = quad.IRI(rdfs.Literal)
+	property         = quad.IRI(rdf.Property)
+	subClassOf       = quad.IRI(rdfs.SubClassOf)
+	subPropertyOf    = quad.IRI(rdfs.SubPropertyOf)
+	alice            = quad.IRI("alice")
+	bob              = quad.IRI("bob")
+	engineer         = quad.IRI("Engineer")
+	information      = quad.IRI("information")
+	likes            = quad.IRI("likes")
+	name             = quad.IRI("name")
+	person           = quad.IRI("Person")
+	personal         = quad.IRI("personal")
+	softwareEngineer = quad.IRI("SoftwareEngineer")
+)
+var (
+	aliceIsPerson                    = triple(alice, ptype, person)
+	aliceLikesBob                    = triple(alice, likes, bob)
+	engineerClass                    = triple(engineer, ptype, class)
+	engineerSubClass                 = triple(engineer, subClassOf, person)
+	nameDomainPerson                 = triple(name, domain, person)
+	nameProperty                     = triple(name, ptype, property)
+	nameSubPropertyOfPersonal        = triple(name, subPropertyOf, personal)
+	personalProperty                 = triple(personal, ptype, property)
+	personalSubPropertyOfInformation = triple(personal, subPropertyOf, information)
+	personClass                      = triple(person, ptype, class)
+	softwareEngineerClass            = triple(softwareEngineer, ptype, class)
+)
+var (
+	engineerAndSoftwareEngineerSubClasses = []quad.Quad{
+		engineerSubClass,
+		triple(softwareEngineer, subClassOf, engineer),
+	}
+	engineerAndPersonClasses = []quad.Quad{
+		engineerClass,
+		personClass,
+	}
+)
+
+func TestClassName(t *testing.T) {
+	iri := alice
+	c := Class{name: iri}
+	require.Equal(t, c.Name(), iri, "Name was not set correctly for the class")
+}
+
+func TestPropertyName(t *testing.T) {
+	iri := likes
+	p := Property{name: iri}
+	require.Equal(t, p.Name(), iri, "Name was not set correctly for the property")
+}
+
+func TestReferencedType(t *testing.T) {
+	store := NewStore()
+	q := aliceIsPerson
+	store.ProcessQuads(q)
+	createdClass := store.GetClass(person)
+	require.NotNil(t, createdClass, "Class was not created")
+}
+
+func TestReferencedBNodeType(t *testing.T) {
+	store := NewStore()
+	name := quad.BNode("123")
+	q := triple(alice, ptype, name)
+	store.ProcessQuads(q)
+	createdClass := store.GetClass(name)
+	require.NotNil(t, createdClass, "Class was not created")
+}
+
+func TestReferencedProperty(t *testing.T) {
+	store := NewStore()
+	q := aliceLikesBob
+	store.ProcessQuads(q)
+	createdProperty := store.GetProperty(likes)
+	require.NotNil(t, createdProperty, "Property was not created")
+}
+
+func TestNewClass(t *testing.T) {
+	store := NewStore()
+	q := personClass
+	store.ProcessQuads(q)
+	createdClass := store.GetClass(person)
+	require.NotNil(t, createdClass, "Class was not created")
+}
+
+func TestNewBNodeClass(t *testing.T) {
+	store := NewStore()
+	name := quad.BNode("123")
+	q := triple(name, ptype, class)
+	store.ProcessQuads(q)
+	createdClass := store.GetClass(name)
+	require.NotNil(t, createdClass, "Class was not created")
+}
+
+func TestInvalidNewClass(t *testing.T) {
+	store := NewStore()
+	name := quad.String("Foo")
+	q := triple(alice, ptype, name)
+	store.ProcessQuads(q)
+	createdClass := store.GetClass(name)
+	require.Nil(t, createdClass, "Invalid class was created")
+}
+
+func TestNewProperty(t *testing.T) {
+	store := NewStore()
+	q := nameProperty
+	store.ProcessQuads(q)
+	createdProperty := store.GetProperty(name)
+	require.NotNil(t, createdProperty, "Property was not created")
+}
+
+func TestInvalidNewProperty(t *testing.T) {
+	store := NewStore()
+	name := quad.String("Foo")
+	q := quad.Quad{Subject: alice, Predicate: name, Object: bob}
+	store.ProcessQuads(q)
+	createdProperty := store.GetProperty(name)
+	require.Nil(t, createdProperty, "Invalid property was created")
+}
+
+func TestSubClass(t *testing.T) {
+	store := NewStore()
+	q := engineerSubClass
+	store.ProcessQuads(q)
+	createdClass := store.GetClass(engineer)
+	createdSuperClass := store.GetClass(person)
+	require.NotNil(t, createdClass, "Class was not created")
+	require.NotNil(t, createdSuperClass, "Super class was not created")
+	if _, ok := createdClass.super[createdSuperClass]; !ok {
+		t.Error("Super class was not registered for class")
+	}
+	if _, ok := createdSuperClass.sub[createdClass]; !ok {
+		t.Error("Class was not registered for super class")
+	}
+}
+
+func TestSubProperty(t *testing.T) {
+	store := NewStore()
+	q := nameSubPropertyOfPersonal
+	store.ProcessQuads(q)
+	createdProperty := store.GetProperty(name)
+	createdSuperProperty := store.GetProperty(personal)
+	require.NotNil(t, createdProperty, "Property was not created")
+	require.NotNil(t, createdSuperProperty, "Super property was not created")
+	if _, ok := createdProperty.super[createdSuperProperty]; !ok {
+		t.Error("Super property was not registered for property")
+	}
+	if _, ok := createdSuperProperty.sub[createdProperty]; !ok {
+		t.Error("Property was not registered for super property")
+	}
+}
+
+func TestPropertyDomain(t *testing.T) {
+	store := NewStore()
+	q := nameDomainPerson
+	store.ProcessQuads(q)
+	createdProperty := store.GetProperty(name)
+	createdClass := store.GetClass(person)
+	require.NotNil(t, createdProperty, "Property was not created")
+	require.NotNil(t, createdClass, "Domain class was not created")
+	if createdProperty.Domain() != createdClass {
+		t.Error("Domain class was not registered for property")
+	}
+	if _, ok := createdClass.ownProp[createdProperty]; !ok {
+		t.Error("Property was not registered for class")
+	}
+}
+
+func TestPropertyRange(t *testing.T) {
+	store := NewStore()
+	q := triple(name, prange, person)
+	store.ProcessQuads(q)
+	createdProperty := store.GetProperty(name)
+	createdClass := store.GetClass(person)
+	require.NotNil(t, createdProperty, "Property was not created")
+	require.NotNil(t, createdClass, "Range class was not created")
+	if createdProperty.Range() != createdClass {
+		t.Error("Range class was not registered for property")
+	}
+	if _, ok := createdClass.inProp[createdProperty]; !ok {
+		t.Error("Property was not registered for class")
+	}
+}
+
+func TestIsSubClassOf(t *testing.T) {
+	store := NewStore()
+	q := engineerSubClass
+	store.ProcessQuads(q)
+	if !store.GetClass(engineer).IsSubClassOf(store.GetClass(person)) {
+		t.Error("Class was not registered as subclass of super class")
+	}
+}
+
+func TestIsSubClassOfRecursive(t *testing.T) {
+	store := NewStore()
+	quads := engineerAndSoftwareEngineerSubClasses
+	store.ProcessQuads(quads...)
+	if !store.GetClass(softwareEngineer).IsSubClassOf(store.GetClass(person)) {
+		t.Error("Class was not registered as subclass of super class")
+	}
+}
+
+func TestIsSubClassOfItself(t *testing.T) {
+	store := NewStore()
+	q := personClass
+	store.ProcessQuads(q)
+	if !store.GetClass(person).IsSubClassOf(store.GetClass(person)) {
+		t.Error("IsSubClassOf itself doesn't work")
+	}
+}
+
+func TestIsSubClassOfResource(t *testing.T) {
+	store := NewStore()
+	q := personClass
+	store.ProcessQuads(q)
+	if !store.GetClass(person).IsSubClassOf(store.GetClass(quad.IRI(rdfs.Resource))) {
+		t.Error("ItSubClassOf rdfs:Resource doesn't work")
+	}
+}
+
+func TestIsSubPropertyOf(t *testing.T) {
+	store := NewStore()
+	q := nameSubPropertyOfPersonal
+	store.ProcessQuads(q)
+	if !store.GetProperty(name).IsSubPropertyOf(store.GetProperty(personal)) {
+		t.Error("Property was not registered as subproperty of super property")
+	}
+}
+
+func TestIsSubPropertyOfRecursive(t *testing.T) {
+	store := NewStore()
+	quads := []quad.Quad{
+		nameSubPropertyOfPersonal,
+		personalSubPropertyOfInformation,
+	}
+	store.ProcessQuads(quads...)
+	if !store.GetProperty(name).IsSubPropertyOf(store.GetProperty(information)) {
+		t.Error("Property was not registered as subproperty of super property")
+	}
+}
+
+func TestIsSubPropertyOfItself(t *testing.T) {
+	store := NewStore()
+	q := nameProperty
+	store.ProcessQuads(q)
+	if !store.GetProperty(name).IsSubPropertyOf(store.GetProperty(name)) {
+		t.Error("IsSubPropertyOf itself doesn't work")
+	}
+}
+
+func TestUnprocessInvalidQuad(t *testing.T) {
+	store := NewStore()
+	store.UnprocessQuads(quad.Quad{Subject: alice, Predicate: quad.String("Foo"), Object: person})
+}
+
+func TestUnprocessInvalidTypeQuad(t *testing.T) {
+	store := NewStore()
+	store.UnprocessQuads(quad.Quad{Subject: alice, Predicate: ptype, Object: quad.String("Foo")})
+}
+
+func TestDeleteReferencedType(t *testing.T) {
+	store := NewStore()
+	q := aliceIsPerson
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	createdClass := store.GetClass(person)
+	require.Nil(t, createdClass, "Class was not deleted")
+}
+
+func TestDeleteClassWithSubClass(t *testing.T) {
+	store := NewStore()
+	store.ProcessQuads(
+		engineerClass,
+		engineerSubClass,
+	)
+	q := personClass
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	subClass := store.GetClass(engineer)
+	if len(subClass.super) != 0 {
+		t.Error("Class was not unreferenced")
+	}
+}
+
+func TestDeleteClassWithSuperClass(t *testing.T) {
+	store := NewStore()
+	store.ProcessQuads(
+		personClass,
+		engineerSubClass,
+	)
+	q := engineerClass
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	superClass := store.GetClass(person)
+	if len(superClass.sub) != 0 {
+		t.Error("Class was not unreferenced")
+	}
+}
+
+func TestDeleteNewClass(t *testing.T) {
+	store := NewStore()
+	q := personClass
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	createdClass := store.GetClass(person)
+	require.Nil(t, createdClass, "Class was not deleted")
+}
+
+func TestDeleteNewProperty(t *testing.T) {
+	store := NewStore()
+	q := nameProperty
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	createdProperty := store.GetProperty(name)
+	require.Nil(t, createdProperty, "Property was not deleted")
+}
+
+func TestDeletePropertyWithSubProperty(t *testing.T) {
+	store := NewStore()
+	store.ProcessQuads(
+		nameProperty,
+		nameSubPropertyOfPersonal,
+	)
+	q := personalProperty
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	subProperty := store.GetProperty(name)
+	if len(subProperty.super) != 0 {
+		t.Error("Property was not unreferenced")
+	}
+}
+
+func TestDeletePropertyWithSuperProperty(t *testing.T) {
+	store := NewStore()
+	store.ProcessQuads(
+		personalProperty,
+		nameSubPropertyOfPersonal,
+	)
+	q := nameProperty
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	superProperty := store.GetProperty(personal)
+	if len(superProperty.sub) != 0 {
+		t.Error("Property was not unreferenced")
+	}
+}
+
+func TestDeleteSubClass(t *testing.T) {
+	store := NewStore()
+	store.ProcessQuads(engineerAndPersonClasses...)
+	q := engineerSubClass
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	createdClass := store.GetClass(engineer)
+	createdSuperClass := store.GetClass(person)
+	// TODO(iddan): what about garbage collection?
+	if _, ok := createdClass.super[createdSuperClass]; ok {
+		t.Error("Super class was not unregistered for class")
+	}
+	if _, ok := createdSuperClass.sub[createdClass]; ok {
+		t.Error("Class was not unregistered for super class")
+	}
+}
+
+func TestDeleteSubProperty(t *testing.T) {
+	store := NewStore()
+	store.ProcessQuads(
+		nameProperty,
+		personalProperty,
+	)
+	q := nameSubPropertyOfPersonal
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	createdProperty := store.GetProperty(name)
+	createdSuperProperty := store.GetProperty(personal)
+	// TODO(iddan): what about garbage collection?
+	if _, ok := createdProperty.super[createdSuperProperty]; ok {
+		t.Error("Super property was not unregistered for property")
+	}
+	if _, ok := createdSuperProperty.sub[createdProperty]; ok {
+		t.Error("Property was not unregistered for super property")
+	}
+}
+
+func TestDeletePropertyDomain(t *testing.T) {
+	store := NewStore()
+	store.ProcessQuads(
+		nameProperty,
+		personClass,
+	)
+	q := nameDomainPerson
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	createdProperty := store.GetProperty(name)
+	createdClass := store.GetClass(person)
+	// TODO(iddan): what about garbage collection?
+	if createdProperty.Domain() == createdClass {
+		t.Error("Domain class was not unregistered for property")
+	}
+	if _, ok := createdClass.ownProp[createdProperty]; ok {
+		t.Error("Property was not unregistered for class")
+	}
+}
+
+func TestDeletePropertyRange(t *testing.T) {
+	store := NewStore()
+	store.ProcessQuads(
+		nameProperty,
+		quad.Quad{Subject: literal, Predicate: ptype, Object: class},
+	)
+	q := quad.Quad{Subject: name, Predicate: prange, Object: literal}
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	createdProperty := store.GetProperty(name)
+	createdClass := store.GetClass(literal)
+	// TODO(iddan): what about garbage collection?
+	if createdProperty.Range() == createdClass {
+		t.Error("Range class was not unregistered for property")
+	}
+	if _, ok := createdClass.inProp[createdProperty]; ok {
+		t.Error("Property was not unregistered for class")
+	}
+}
+
+func TestDeleteIsSubClassOf(t *testing.T) {
+	store := NewStore()
+	store.ProcessQuads(engineerAndPersonClasses...)
+	q := engineerSubClass
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	if store.GetClass(engineer).IsSubClassOf(store.GetClass(person)) {
+		t.Error("Class was not unregistered as subclass of super class")
+	}
+}
+
+func TestDeleteIsSubClassOfRecursive(t *testing.T) {
+	store := NewStore()
+	store.ProcessQuads(
+		engineerClass,
+		personClass,
+		softwareEngineerClass,
+	)
+	quads := engineerAndSoftwareEngineerSubClasses
+	store.ProcessQuads(quads...)
+	store.UnprocessQuads(quads...)
+	if store.GetClass(softwareEngineer).IsSubClassOf(store.GetClass(person)) {
+		t.Error("Class was not unregistered as subclass of super class")
+	}
+}
+
+func TestDeleteIsSubPropertyOf(t *testing.T) {
+	store := NewStore()
+	store.ProcessQuads(
+		nameProperty,
+		personalProperty,
+	)
+	q := nameSubPropertyOfPersonal
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	if store.GetProperty(name).IsSubPropertyOf(store.GetProperty(personal)) {
+		t.Error("Property was not unregistered as subproperty of super property")
+	}
+}
+
+func TestDeleteIsSubPropertyOfRecursive(t *testing.T) {
+	store := NewStore()
+	store.ProcessQuads(
+		nameProperty,
+		personalProperty,
+		quad.Quad{Subject: information, Predicate: ptype, Object: property},
+	)
+	quads := []quad.Quad{
+		nameSubPropertyOfPersonal,
+		personalSubPropertyOfInformation,
+	}
+	store.ProcessQuads(quads...)
+	store.UnprocessQuads(quads...)
+	if store.GetProperty(name).IsSubPropertyOf(store.GetProperty(information)) {
+		t.Error("Property was not unregistered as subproperty of super property")
+	}
+}
+
+func TestClassIsReference(t *testing.T) {
+	store := NewStore()
+	q := aliceIsPerson
+	store.ProcessQuads(q)
+	class := store.GetClass(person)
+	if !class.isReferenced() {
+		t.Error("Class should be referenced")
+	}
+}
+
+func TestPropertyIsReference(t *testing.T) {
+	store := NewStore()
+	q := aliceLikesBob
+	store.ProcessQuads(q)
+	property := store.GetProperty(likes)
+	if !property.isReferenced() {
+		t.Error("Property should be referenced")
+	}
+}
+
+func TestClassUnreference(t *testing.T) {
+	store := NewStore()
+	q := aliceIsPerson
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	require.Nil(t, store.GetClass(person), "class was not garbage collected")
+}
+
+func TestPropertyUnreference(t *testing.T) {
+	store := NewStore()
+	q := aliceLikesBob
+	store.ProcessQuads(q)
+	store.UnprocessQuads(q)
+	require.Nil(t, store.GetProperty(likes), "property was not garbage collected")
+}