http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/01489efb/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/Fact.java ---------------------------------------------------------------------- diff --git a/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/Fact.java b/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/Fact.java new file mode 100644 index 0000000..75c3a78 --- /dev/null +++ b/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/Fact.java @@ -0,0 +1,514 @@ +package mvm.rya.reasoning; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.io.DataInput; +import java.io.DataOutput; +import java.io.IOException; +import java.nio.charset.StandardCharsets; + +import mvm.rya.api.domain.RyaStatement; +import mvm.rya.api.resolver.RyaToRdfConversions; + +import org.apache.hadoop.io.WritableComparable; +import org.openrdf.model.Literal; +import org.openrdf.model.Resource; +import org.openrdf.model.Statement; +import org.openrdf.model.URI; +import org.openrdf.model.Value; +import org.openrdf.model.ValueFactory; +import org.openrdf.model.impl.ContextStatementImpl; +import org.openrdf.model.impl.StatementImpl; +import org.openrdf.model.impl.ValueFactoryImpl; +import org.openrdf.model.vocabulary.RDF; + +/** + * Represents a fact used and/or generated by the reasoner. + */ +public class Fact implements WritableComparable<Fact>, Cloneable { + Statement triple; + + // If this is a derived fact: + Derivation derivation; + + // Potentially useful for future derivations + boolean useful = true; + + // An empty fact + public static final Fact NONE = new Fact(); + + private static final String SEP = "\u0000"; + + /** + * Default constructor, contains no information + */ + public Fact() { } + + /** + * A fact containing a triple and no generating rule. + */ + public Fact(Statement stmt) { + this.triple = stmt; + } + + /** + * A fact containing a triple and no generating rule. + */ + public Fact(Resource s, URI p, Value o) { + this.triple = new StatementImpl(s, p, o); + } + + /** + * A fact which contains a triple and was generated using a + * particular rule by a reasoner for a particular node. + */ + public Fact(Resource s, URI p, Value o, int iteration, + OwlRule rule, Resource node) { + this.triple = new StatementImpl(s, p, o); + this.derivation = new Derivation(iteration, rule, node); + } + + public Statement getTriple() { + return triple; + } + + public Resource getSubject() { + if (triple == null) { + return null; + } + else { + return triple.getSubject(); + } + } + + public URI getPredicate() { + if (triple == null) { + return null; + } + else { + return triple.getPredicate(); + } + } + + public Value getObject() { + if (triple == null) { + return null; + } + else { + return triple.getObject(); + } + } + + /** + * Get the derivation if it exists, or the empty derivation otherwise. + */ + public Derivation getDerivation() { + if (derivation == null) { + return Derivation.NONE; + } + else { + return derivation; + } + } + + public boolean isInference() { + return derivation != null; + } + + public boolean isUseful() { + return useful; + } + + public boolean isEmpty() { + return triple == null; + } + + /** + * Assign a particular statement to this fact. + */ + public void setTriple(Statement stmt) { + triple = stmt; + } + + /** + * Assign a particular statement to this fact. + */ + public void setTriple(RyaStatement rs) { + setTriple(RyaToRdfConversions.convertStatement(rs)); + } + + /** + * Set a flag if this triple *could* be used in future derivations + * (may only actually happen if certain other facts are seen as well.) + */ + public void setUseful(boolean useful) { + this.useful = useful; + } + + /** + * Set derivation. Allows reconstructing a fact and the way it was produced. + */ + public void setDerivation(Derivation d) { + this.derivation = d; + } + + /** + * Set derivation to null and return its former value. Allows decoupling + * of the fact from the way it was produced. + */ + public Derivation unsetDerivation() { + Derivation d = getDerivation(); + this.derivation = null; + return d; + } + + /** + * Generate a String showing this fact's derivation. + * @param multiline Print a multi-line tree as opposed to a nested list + * @param schema Use schema knowledge to further explain BNodes + */ + public String explain(boolean multiline, Schema schema) { + return explain(multiline, "", schema); + } + + /** + * Generate a String showing this fact's derivation. Does not incorporate + * schema information. + * @param multiline Print a multi-line tree as opposed to a nested list + */ + public String explain(boolean multiline) { + return explain(multiline, "", null); + } + + /** + * Recursively generate a String to show this fact's derivation. + */ + String explain(boolean multiline, String prefix, Schema schema) { + StringBuilder sb = new StringBuilder(); + String sep = " "; + if (multiline) { + sep = "\n" + prefix; + } + if (triple == null) { + sb.append("(empty)").append(sep); + } + else { + Resource s = getSubject(); + URI p = getPredicate(); + Value o = getObject(); + sb.append("<").append(s.toString()).append(">").append(sep); + sb.append("<").append(p.toString()).append(">").append(sep); + sb.append("<").append(o.toString()).append(">"); + // Restrictions warrant further explanation + if (schema != null && p.equals(RDF.TYPE)) { + Resource objClass = (Resource) o; + if (schema.hasRestriction(objClass)) { + sb.append(" { "); + sb.append(schema.explainRestriction(objClass)); + sb.append(" }"); + } + } + sb.append(sep); + } + if (isInference()) { + sb.append(derivation.explain(multiline, prefix, schema)); + } + else { + sb.append("[input]"); + } + return sb.toString(); + } + + /** + * Represent the content only, not the derivation. + */ + @Override + public String toString() { + StringBuilder sb = new StringBuilder(); + if (triple != null) { + sb.append("<").append(getSubject().toString()).append("> "); + sb.append("<").append(getPredicate().toString()).append("> "); + if (getObject() instanceof Literal) { + sb.append(getObject().toString()); + } + else { + sb.append("<").append(getObject().toString()).append(">"); + } + } + return sb.append(" .").toString(); + } + + @Override + public void write(DataOutput out) throws IOException { + if (triple == null) { + out.writeInt(0); + } + else { + StringBuilder sb = new StringBuilder(); + if (triple.getContext() != null) { + sb.append(triple.getContext().toString()); + } + sb.append(SEP).append(getSubject().toString()); + sb.append(SEP).append(getPredicate().toString()); + sb.append(SEP).append(getObject().toString()); + byte[] encoded = sb.toString().getBytes(StandardCharsets.UTF_8); + out.writeInt(encoded.length); + out.write(encoded); + } + out.writeBoolean(useful); + // Write the derivation if there is one + boolean derived = isInference(); + out.writeBoolean(derived); + if (derived) { + derivation.write(out); + } + } + + @Override + public void readFields(DataInput in) throws IOException { + derivation = null; + int tripleLength = in.readInt(); + if (tripleLength == 0) { + triple = null; + } + else { + byte[] tripleBytes = new byte[tripleLength]; + in.readFully(tripleBytes); + String tripleString = new String(tripleBytes, StandardCharsets.UTF_8); + String[] parts = tripleString.split(SEP); + ValueFactory factory = ValueFactoryImpl.getInstance(); + String context = parts[0]; + Resource s = null; + URI p = factory.createURI(parts[2]); + Value o = null; + // Subject: either bnode or URI + if (parts[1].startsWith("_")) { + s = factory.createBNode(parts[1].substring(2)); + } + else { + s = factory.createURI(parts[1]); + } + // Object: literal, bnode, or URI + if (parts[3].startsWith("_")) { + o = factory.createBNode(parts[3].substring(2)); + } + else if (parts[3].startsWith("\"")) { + //literal: may have language or datatype + int close = parts[3].lastIndexOf("\""); + int length = parts[3].length(); + String label = parts[3].substring(1, close); + if (close == length - 1) { + // Just a string enclosed in quotes + o = factory.createLiteral(label); + } + else { + String data = parts[3].substring(close + 1); + if (data.startsWith("@")) { + String lang = data.substring(1); + o = factory.createLiteral(label, lang); + } + else if (data.startsWith("^^<")) { + o = factory.createLiteral(label, factory.createURI( + data.substring(3, data.length() - 1))); + } + } + } + else { + o = factory.createURI(parts[3]); + } + // Create a statement with or without context + if (context.isEmpty()) { + triple = new StatementImpl(s, p, o); + } + else { + triple = new ContextStatementImpl(s, p, o, factory.createURI(context)); + } + } + useful = in.readBoolean(); + if (in.readBoolean()) { + derivation = new Derivation(); + derivation.readFields(in); + } + } + + /** + * Defines an ordering based on equals. + * Two ReasonerFacts belong together if they represent the same + * triple (regardless of where it came from). If they both are empty + * (represent no triple), compare their derivations instead. + */ + @Override + public int compareTo(Fact other) { + if (this.equals(other)) { + return 0; + } + else if (other == null) { + return 1; + } + if (this.triple == null) { + if (other.triple == null) { + // The only case where Derivation matters + return this.getDerivation().compareTo(other.getDerivation()); + } + else { + // triple > no triple + return -1; + } + } + else if (other.triple == null) { + // triple > no triple + return 1; + } + // Compare two triples, ignoring where the information came from + int result = this.getSubject().toString().compareTo( + other.getSubject().toString()); + if (result == 0) { + result = this.getPredicate().toString().compareTo( + other.getPredicate().toString()); + if (result == 0) { + result = this.getObject().toString().compareTo( + other.getObject().toString()); + } + } + return result; + } + + /** + * Two ReasonerFacts are equivalent if they represent the same triple + * (regardless of where it came from). If they don't contain triples, + * compare their derivations. + */ + @Override + public boolean equals(Object o) { + if (this == o) { + return true; + } + if (o == null || this.getClass() != o.getClass()) { + return false; + } + Fact other = (Fact) o; + if (this.triple == null) { + if (other.triple == null) { + // Derivations only matter if both facts are empty + return this.getDerivation().equals(other.getDerivation()); + } + else { + return false; + } + } + else { + return this.triple.equals(other.triple); + } + } + + /** + * Two statements are the same as long as they represent the same triple. + * Derivation matters if and only if there is no triple. + */ + @Override + public int hashCode() { + if (triple == null) { + return getDerivation().hashCode(); + } + else { + return triple.hashCode(); + } + } + + @Override + public Fact clone() { + Fact other = new Fact(); + other.triple = this.triple; + other.useful = this.useful; + if (this.derivation != null) { + other.derivation = this.derivation.clone(); + } + return other; + } + + /** + * Specify a source. Wrapper for Derivation.addSource. Instantiates a + * derivation if none exists. + */ + public void addSource(Fact other) { + if (derivation == null) { + derivation = new Derivation(); + } + derivation.addSource(other); + } + + /** + * If this is a derived fact, get the iteration it was derived, otherwise + * return zero. + */ + public int getIteration() { + if (derivation == null) { + return 0; + } + else { + return derivation.getIteration(); + } + } + + /** + * Return whether this fact has itself as a source. + */ + public boolean isCycle() { + return derivation != null && derivation.hasSource(this); + } + + /** + * Return whether a particular fact is identical to one used to derive this. + * Wrapper for Derivation.hasSource. + */ + public boolean hasSource(Fact other) { + return derivation != null && derivation.hasSource(other); + } + + /** + * Return whether this fact was derived using a particular rule. + */ + public boolean hasRule(OwlRule rule) { + return derivation != null && derivation.getRule() == rule; + } + + /** + * Get the size of the derivation tree, computed by counting up the number + * of distinct nodes that are part of this edge or were used to produce this + * fact, minus 1. An input triple has span 1, a triple derived in one reduce + * step has span 2, etc. Related to the derivation's span, but takes + * subject and object of this fact into account. + */ + public int span() { + if (isInference()) { + int d = derivation.span() + 1; + if (derivation.hasSourceNode(getSubject())) { + d--; + } + if (derivation.hasSourceNode(getObject())) { + d--; + } + return d; + } + else { + return 1; + } + } +}
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/01489efb/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/LocalReasoner.java ---------------------------------------------------------------------- diff --git a/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/LocalReasoner.java b/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/LocalReasoner.java new file mode 100644 index 0000000..41ac734 --- /dev/null +++ b/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/LocalReasoner.java @@ -0,0 +1,667 @@ +package mvm.rya.reasoning; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.HashMap; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.Set; + +import org.openrdf.model.Literal; +import org.openrdf.model.Resource; +import org.openrdf.model.URI; +import org.openrdf.model.Value; +import org.openrdf.model.vocabulary.OWL; +import org.openrdf.model.vocabulary.RDF; + +/** + * Perform reasoning with respect to a particular node, given a global schema. + * Assumes that incoming input triples will be provided first (i.e. triples + * where this node is the object) in order to perform some joins. + * <p> + * Rules implemented so far: + * <p> + * Simple rules implemented here: + * <ul> + * <li>prp-dom: domain: infer subject's type from predicate's domain + * <li>prp-rng: range: infer object's type from predicate's range + * <li>prp-irp: If p is irreflexive, (x p x) is inconsistent + * <li>prp-symp: If p is symmetric, (x p y) implies (y p x) + * <li>prp-spo1: subPropertyOf semantics: inherit superproperties + * <li>prp-inv1: If p1 inverseOf p2, (x p1 y) implies (y p2 x) + * <li>prp-inv2: If p1 inverseOf p2, (x p2 y) implies (y p1 x) + * <li>cls-svf2: If [x someValuesFrom owl:Thing onProperty p], + * (u p v) implies (u type x) + * <li>cls-hv2: If [x hasValue v onProperty p], (u p v) implies + * (u type x) + * </ul> + * <p> + * Join rules implemented here: + * <ul> + * <li>prp-asyp: If p is asymmetric, (x p y) and (y p x) is inconsistent + * <li>prp-trp: If p is transitive, (x p y) and (y p z) implies (x p z) + * <li>prp-pdw: If p is disjoint with q, (x p y) and (x q y) is + * inconsistent + * <li>cls-svf1: If [x someValuesFrom y onProperty p], + * (u p v) and (v type y) imply (u type x) + * <li>cls-avf: If [x allValuesFrom y onProperty p], + * (u p v) and (u type x) imply (v type y) + * <li>cls-maxc1: (x p y) is inconsistent if p has maxCardinality 0 + * <li>cls-maxqc2: ...or if p has maxQualifiedCardinality 0 on owl:Thing + * </ul> + * <p> + * Simple and join rules handled in {@link TypeReasoner}: + * <ul> + * <li>cax-sco: subClassOf semantics: inherit supertypes + * <li>cls-hv1: If [x hasValue v onProperty p], (u type x) implies + * (u p v) + * <li>cls-nothing2: type owl:Nothing is automatically inconsistent + * <li>cls-com: If c1 has complement c2, having both types is + * inconsistent + * <li>cax-dw: If c1 and c2 are disjoint, having both types is + * inconsistent + * </ul> + */ +public class LocalReasoner extends AbstractReasoner { + public enum Relevance { + NONE, SUBJECT, OBJECT, BOTH; + static Relevance get(boolean s, boolean o) { + if (s && o) return BOTH; + else if (s) return SUBJECT; + else if (o) return OBJECT; + else return NONE; + } + public boolean subject() { return this == SUBJECT || this == BOTH; } + public boolean object() { return this == OBJECT || this == BOTH; } + } + + /** + * Determine whether a fact is a triple which might be used by a local + * reasoner for its subject and/or object. + * @param fact Fact to be evaluated + * @param schema Global schema + * @return Relevance to subject and/or object. Relevance means that it's a + * triple that *could* be used in reasoning. It may only be useful + * when combined with other facts, which may or may not exist + * somewhere, so this doesn't guarantee that information will be + * derived. + */ + public static Relevance relevantFact(Fact fact, Schema schema) { + // If this is schema information, we know it's already + // contained in the schema object. + if (Schema.isSchemaTriple(fact.getTriple())) { + return Relevance.NONE; + } + // Otherwise, consider the semantics of the statement: + Resource subject = fact.getSubject(); + URI predURI = fact.getPredicate(); + Value object = fact.getObject(); + boolean relevantToSubject = false; + boolean relevantToObject = false; + // Literals don't get reasoners, so determine whether object is a uri: + boolean literalObject = object instanceof Literal; + + // Type statements could be relevant to the subject, if the schema gives + // them any meaning: + if (predURI.equals(RDF.TYPE)) { + // Assume the object is a valid URI + Resource typeURI = (Resource) fact.getObject(); + if (typeURI.equals(OWL.NOTHING) + || schema.hasClass(typeURI)) { + relevantToSubject = true; + } + } + + // If the schema knows about the property: + if (schema.hasProperty(predURI)) { + OwlProperty prop = schema.getProperty(predURI); + + // Relevant to both: + // Any statement with an asymmetric property + if (prop.isAsymmetric() + // Any statement with a transitive property + || prop.isTransitive() + // Statements involving restricted properties + || !prop.getRestrictions().isEmpty()) { + relevantToSubject = true; + relevantToObject = !literalObject; + } + + // Relevant to subject: + if (!relevantToSubject && // skip these checks if it already is + // Any statement whose property has a domain. + (!prop.getDomain().isEmpty() + // Choose to apply superproperties here + // (every property is its own superproperty; ignore that) + || prop.getSuperProperties().size() > 1 + // Choose to apply disjoint properties here + || !prop.getDisjointProperties().isEmpty())) { + relevantToSubject = true; + } + + // Relevant to object if the object is not a literal and one other + // condition matches: + if (!literalObject && !relevantToObject && + // Any statement whose property has a defined range + (!prop.getRange().isEmpty() + // Choose to apply inverse rule in the object's reasoner + || !prop.getInverseProperties().isEmpty() + // Choose to apply symmetry in the object's reasoner + || prop.isSymmetric() + // Choose to check irreflexivity in the object's reasoner + || prop.isIrreflexive() && subject.equals(object))) { + relevantToObject = true; + } + } + return Relevance.get(relevantToSubject, relevantToObject); + } + + /** + * Determine whether a fact is a triple which might be used in some join + * rule for its subject and/or object. + */ + public static Relevance relevantJoinRule(Fact fact, Schema schema) { + // If this is schema information, we know it's already + // contained in the schema object. + if (Schema.isSchemaTriple(fact.getTriple())) { + return Relevance.NONE; + } + // Otherwise, consider the semantics of the statement: + URI predURI = fact.getPredicate(); + Value object = fact.getObject(); + boolean relevantToSubject = false; + boolean relevantToObject = false; + // Literals don't get reasoners, so determine whether object is a uri: + boolean literalObject = object instanceof Literal; + + // Type statements can be joined if... + if (predURI.equals(RDF.TYPE)) { + Resource typeURI = (Resource) fact.getObject(); + if (schema.hasClass(typeURI)) { + OwlClass c = schema.getClass(typeURI); + // 1. the type is a property restriction + if (!c.getOnProperty().isEmpty() + // 2. the type is relevant to a property restriction + || !c.getSvfRestrictions().isEmpty() + || !c.getAvfRestrictions().isEmpty() + || !c.getQCRestrictions().isEmpty() + // 3. the type has complementary/disjoint types + || !c.getDisjointClasses().isEmpty() + || !c.getComplementaryClasses().isEmpty()) { + relevantToSubject = true; + } + } + } + + // If the schema knows about the property: + if (schema.hasProperty(predURI)) { + OwlProperty prop = schema.getProperty(predURI); + // transitivity: relevant to both + if (prop.isTransitive()) { + relevantToSubject = true; + relevantToObject = !literalObject; + } + else { + // disjoint properties: relevant to subject + if (!prop.getDisjointProperties().isEmpty()) { + relevantToSubject = true; + } + // Property restrictions: possibly relevant to either + for (Resource rURI : prop.getRestrictions()) { + OwlClass r = schema.getClass(rURI); + // allValuesFrom requires a join on the subject + // (if <subject type rURI>, infer object's type) + if (!r.allValuesFrom().isEmpty()) { + relevantToSubject = true; + } + // someValuesFrom requires a join on the object + // (if the object is the appropriate type, infer rURI) + // max cardinality requires a join on the subject + if (!literalObject && + (r.getMaxCardinality() >= 0 + || r.getMaxQualifiedCardinality() >= 0 + || !r.someValuesFrom().isEmpty())) { + relevantToObject = true; + } + if (relevantToSubject + && (relevantToObject || literalObject)) { + break; + } + } + } + } + return Relevance.get(relevantToSubject, relevantToObject); + } + + /** + * Use the semantics of a fact to determine whether it could be relevant + * to future reasoners, or whether we should assume we've extracted all + * the information implied by the fact during this iteration. Considers + * semantics but not age. + * @return true if this fact might still be used later. + */ + boolean relevantToFuture(Fact fact) { + // If it's a join rule, it needs to be kept no matter what + if (relevantJoinRule(fact, schema) != Relevance.NONE) { + return true; + } + // Otherwise, it can be skipped under certain circumstances. + Relevance general = relevantFact(fact, schema); + Resource s = fact.getSubject(); + Value o = fact.getObject(); + // Exception: if subject==object, recursive derivation is limited, so + // we can't make assumptions about what's already been done. + if (!s.equals(o)) { + // Otherwise, if this is a reasoner for the subject, and the fact + // is only relevant to the subject, we can assume this reasoner + // did all the reasoning we needed to. + if (general == Relevance.SUBJECT && node.equals(s)) { + return false; + } + // Same reasoning for the object: + if (general == Relevance.OBJECT && node.equals(o)) { + return false; + } + } + // If we can't skip it, return true if it's ever relevant + return general != Relevance.NONE; + } + + // Many rules derive types; keep track of them with a TypeReasoner + TypeReasoner types; + + // Keep track of statements whose properties might make them relevant later + Map<URI, List<Fact>> transitiveIncoming = new HashMap<>(); + Map<URI, List<Fact>> asymmetricIncoming = new HashMap<>(); + Map<URI, List<Fact>> disjointOutgoing = new HashMap<>(); + + // Only combine transitive paths of a certain size, based on the current + // iteration, to avoid duplicate derivations and unnecessary memory use. + int minTransitiveLeft; + int minTransitiveRight; + + /** + * Constructor. + * @param node Conduct reasoning about/around this node + * @param schema Global schema (class/property) information + * @param t Current iteration; any new facts will be generated with + * this number + * @param tSchema Iteration of latest schema update (0 if original + * schema is unchanged) + */ + public LocalReasoner(Resource node, Schema schema, int t, int tSchema) { + super(node, schema, t, tSchema); + types = new TypeReasoner(node, schema, t, tSchema); + // "Smart TC": combine incoming paths of length 2^(n-1) with outgoing + // paths of any length. + int n = t - tSchema; // count iterations since any schema change + minTransitiveLeft = (int) Math.pow(2, n-1); + minTransitiveRight = 1; + } + + /** + * Read in a fact involving this node and make any inferences we can. + * Assumes that incoming triples are received before outgoing triples. + * Recursively call processFact on new triples until nothing else is + * derived. + * @param fact Contains a triple assumed to be relevant to this reasoner + */ + public void processFact(Fact fact) { + Resource subject = fact.getSubject(); + URI pred = fact.getPredicate(); + Value object = fact.getObject(); + // Whether this is a recursive call on a fact that's just been inferred + boolean recursive = fact.getIteration() == currentIteration; + // Figure out what kind of edge this is with respect to this node + boolean incoming = object.equals(node); + boolean outgoing = subject.equals(node); + // Avoid some derivation chains on recursive calls to avoid cycles + boolean skipReflexive = incoming && outgoing && recursive; + // Perform reasoning (incoming before outgoing, so reflexive edges are + // handled in the right order) + if (incoming && !skipReflexive) { + processIncoming(fact); + } + if (outgoing) { + if (pred.equals(RDF.TYPE)) { + types.processType(fact); + } + else { + processOutgoing(fact); + } + } + // If newly-learned facts cause further derivations, apply them recursively + Set<Fact> resultsSoFar = getFacts(); + for (Fact newFact : resultsSoFar) { + processFact(newFact); + } + newFacts.addAll(resultsSoFar); + } + + /** + * Process a triple in which this node is the subject. + */ + private void processOutgoing(Fact fact) { + URI predURI = fact.getPredicate(); + Value object = fact.getObject(); + OwlProperty prop = schema.getProperty(predURI); + Set<Resource> restrictions = prop.getRestrictions(); + Set<URI> disjointProps = prop.getDisjointProperties(); + // RL rule prp-dom: Apply domain(s), if appropriate + for (Resource type : prop.getDomain()) { + types.processType(type, OwlRule.PRP_DOM, fact); + } + // RL rule prp-spo1: assert superproperties + // Assume we have the full property hierarchy in the schema, so that + // if the input fact was derived using this rule, we must have gotten + // all the superproperties and don't need to apply them again. + if (!fact.hasRule(OwlRule.PRP_SPO1)) { + for (URI superProp : prop.getSuperProperties()) { + // (everything is its own superproperty) + if (superProp.equals(predURI)) { + continue; + } + collect(triple(node, superProp, object, OwlRule.PRP_SPO1, fact)); + } + } + // RL rule prp-pdw: Check if this conflicts with any disjoint properties + if (!disjointProps.isEmpty()) { + for (URI disjointProp : disjointProps) { + if (disjointOutgoing.containsKey(disjointProp)) { + for (Fact other : disjointOutgoing.get(disjointProp)) { + if (object.equals(other.getObject())) { + Derivation pdwFact = inconsistency(OwlRule.PRP_PDW, fact); + pdwFact.addSource(other); + collectInconsistency(pdwFact); + } + } + } + } + if (!disjointOutgoing.containsKey(predURI)) { + disjointOutgoing.put(predURI, new LinkedList<Fact>()); + } + disjointOutgoing.get(predURI).add(fact); + } + // Property restriction rules: + for (Resource rNode : restrictions) { + OwlClass restriction = schema.getClass(rNode); + // RL rule cls-svf2: if (?x owl:someValuesFrom owl:Thing) + if (restriction.someValuesFrom().contains(OWL.THING)) { + // If there are any property restrictions stating that class + // x is equivalent to having someValuesFrom owl:Thing for this + // property, then this node is a member of type x + types.processType(rNode, OwlRule.CLS_SVF2, fact); + } + // RL rule cls-hv2: if (?x owl:hasValue <object>) + if (restriction.hasValue().contains(object)) { + //... then node (subject) satisfies/belongs to x + types.processType(rNode, OwlRule.CLS_HV2, fact); + } + // RL rule cls-avf: if x=[allValuesFrom ?c onProperty ?p]: + for (Resource c : restriction.allValuesFrom()) { + // If/when we learn this node is supposed to satisfy this + // restriction, and if object is a resource, assert + // (object type c). + if (object instanceof Resource) { + types.onType(rNode, triple((Resource) object, RDF.TYPE, + c, OwlRule.CLS_AVF, fact)); + } + } + // RL rule cls-maxc1: if x=[maxCardinality 0], subject can't be x + if (restriction.getMaxCardinality() == 0) { + types.inconsistentOnType(rNode, + inconsistency(OwlRule.CLS_MAXC1, fact)); + } + // RL rule cls-maxqc2: x=[maxQualifiedCardinality 0 on owl:Thing] + // (same as maxCardinality 0) + if (restriction.getMaxQualifiedCardinality() == 0 + && restriction.onClass().contains(OWL.THING)) { + types.inconsistentOnType(rNode, + inconsistency(OwlRule.CLS_MAXQC2, fact)); + } + } + // RL rule prp-trp (part 1/2): Apply against incoming statements + // with the same predicate (skip if this node is both the subject and + // object) . + // Assumes that input is sorted with incoming coming first, so we don't + // need to store this triple after joining. + if (prop.isTransitive() && !object.equals(node) + && checkTransitivityOutgoing(fact)) { + if (transitiveIncoming.containsKey(predURI)) { + for (Fact other : transitiveIncoming.get(predURI)) { + Resource otherSubject = other.getSubject(); + Fact trpFact = triple(otherSubject, predURI, object, + OwlRule.PRP_TRP, fact); + trpFact.addSource(other); + collect(trpFact); + } + } + } + // RL rule prp-asyp (part 2/2): Check against incoming statements with + // the same predicate. Don't store this one since we assume input is + // sorted by the direction of the edge. + if (prop.isAsymmetric() && asymmetricIncoming.containsKey(predURI)) { + for (Fact other : asymmetricIncoming.get(predURI)) { + if (object.equals(other.getSubject())) { + Derivation asypFact = inconsistency(OwlRule.PRP_ASYP, fact); + asypFact.addSource(other); + collectInconsistency(asypFact); + } + } + } + } + + /** + * Process a triple in which this node is the object. + */ + private void processIncoming(Fact fact) { + Resource subject = fact.getSubject(); + URI predURI = fact.getPredicate(); + OwlProperty prop = schema.getProperty(predURI); + // RL rule prp-rng: Apply range(s), if appropriate + for (Resource type : prop.getRange()) { + types.processType(type, OwlRule.PRP_RNG, fact); + } + // RL rules prp-inv1, prp-inv2: assert any inverse properties + for (URI inverseProp : prop.getInverseProperties()) { + collect(triple(node, inverseProp, subject, OwlRule.PRP_INV, fact)); + } + // RL rule prp-symp: Assert the symmetric statement if appropriate + if (prop.isSymmetric() + && !fact.hasRule(OwlRule.PRP_SYMP) + && !subject.equals(node)) { + collect(triple(node, predURI, subject, OwlRule.PRP_SYMP, fact)); + } + // RL rule prp-irp: (x p x) is inconsistent if p is irreflexive + if (prop.isIrreflexive() && subject.equals(node)) { + collectInconsistency(inconsistency(OwlRule.PRP_IRP, fact)); + } + // RL rule prp-trp (part 1/2): We assume triples are sorted with + // incoming first, so store this triple in case it needs to be joined + // with any later outgoing triples with the same property. + if (prop.isTransitive() && !subject.equals(node) + && checkTransitivityIncoming(fact)) { + if (!transitiveIncoming.containsKey(predURI)) { + transitiveIncoming.put(predURI, new LinkedList<Fact>()); + } + transitiveIncoming.get(predURI).add(fact); + } + // RL rule prp-asyp (part 1/2): Store this incoming edge so we can + // compare later outgoing edges against it. (Assume sorted input.) + if (prop.isAsymmetric()) { + if (!asymmetricIncoming.containsKey(predURI)) { + asymmetricIncoming.put(predURI, new LinkedList<Fact>()); + } + asymmetricIncoming.get(predURI).add(fact); + } + for (Resource rNode : prop.getRestrictions()) { + OwlClass restriction = schema.getClass(rNode); + // RL rule cls-svf1: Check for a someValuesFrom restriction + Set<Resource> valuesFrom = restriction.someValuesFrom(); + // type owl:Thing would be checked by cls-svf2 + valuesFrom.remove(OWL.THING); + for (Resource commonType : valuesFrom) { + // If we learn the type, assert the other node's membership in rNode + types.onType(commonType, triple(subject, RDF.TYPE, + rNode, OwlRule.CLS_SVF1, fact)); + } + } + } + + /** + * Collect all the derived type information in a single ResultSet. + */ + public void getTypes() { + types.collectTypes(); + newFacts.addAll(types.getFacts()); + } + + /** + * Determine whether an inconsistency has been found. + */ + @Override + public boolean hasInconsistencies() { + return types.hasInconsistencies() || !inconsistencies.isEmpty(); + } + + /** + * Get results, including those stored in the TypeReasoner. + */ + @Override + public Set<Fact> getFacts() { + Set<Fact> results = types.getFacts(); + if (hasNewFacts()) { + results.addAll(newFacts); + newFacts.clear(); + } + // If we can mark some facts as not needing to be processed during the + // next step, do so: + for (Fact result : results) { + result.setUseful(relevantToFuture(result)); + } + return results; + } + + /** + * Get inconsistencies, including those stored in the TypeReasoner. + */ + @Override + public Set<Derivation> getInconsistencies() { + Set<Derivation> results = types.getInconsistencies(); + if (hasInconsistencies()) { + results.addAll(inconsistencies); + inconsistencies.clear(); + } + return results; + } + + /** + * Get some diagnostic info for logging purposes. + */ + @Override + public String getDiagnostics() { + // Count the different types of triples in memory: + int sumIncomingAsymmetric = 0; + int sumOutgoingDisjoint = 0; + int sumIncomingTransitive = 0; + for (List<Fact> l : asymmetricIncoming.values()) { + sumIncomingAsymmetric += l.size();; + } + for (List<Fact> l : disjointOutgoing.values()) { + sumOutgoingDisjoint += l.size();; + } + int maxTransitiveSpan = (int) Math.pow(2, currentIteration); + int[] distribution = new int[maxTransitiveSpan+1]; + for (int i = 0; i <= maxTransitiveSpan; i++) { + distribution[i] = 0; + } + for (List<Fact> l : transitiveIncoming.values()) { + for (Fact fact : l) { + sumIncomingTransitive++; + int x = fact.span(); + if (x > 0 && x <= maxTransitiveSpan) { + distribution[x]++; + } + else { + distribution[0]++; + } + } + } + + // Collect totals: + StringBuilder sb = new StringBuilder(); + sb.append("Node: ").append(node.stringValue()).append("\n"); + sb.append(newFacts.size()).append(" new triples stored\n"); + sb.append(sumIncomingAsymmetric).append(" stored incoming triples w/ "); + sb.append(asymmetricIncoming.size()).append(" asymmetric properties\n"); + sb.append(sumOutgoingDisjoint).append(" stored outgoing triples w/ "); + sb.append(disjointOutgoing.size()).append(" disjoint properties\n"); + sb.append(sumIncomingTransitive).append(" stored incoming triples w/ "); + sb.append(transitiveIncoming.size()).append(" transitive properties\n"); + sb.append("Span of stored transitive triples:\n"); + for (int i = 0; i <= maxTransitiveSpan; i++) { + sb.append(" ").append(i).append(": ").append(distribution[i]); + sb.append("\n"); + } + sb.append(types.getDiagnostics()); + return sb.toString(); + } + + /** + * Get the total number of input facts cached. + */ + @Override + public int getNumStored() { + int total = 0; + for (List<Fact> l : asymmetricIncoming.values()) { + total += l.size();; + } + for (List<Fact> l : disjointOutgoing.values()) { + total += l.size();; + } + for (List<Fact> l : transitiveIncoming.values()) { + total += l.size(); + } + return total + types.getNumStored(); + } + + /** + * Determine whether transitivity should be applied to an incoming triple. + * Decide based on the distance of the relationship. For any length l, there + * should be a unique split l1 and l2 such that any connection of length l + * will be made only by combining a left-hand/incoming connection of length + * l1 and a right-hand/outgoing connection of length l2. + */ + boolean checkTransitivityIncoming(Fact fact) { + return fact.span() >= minTransitiveLeft; + } + + /** + * Determine whether transitivity should be applied to an outgoing triple. + * Decide based on the distance of the relationship. For any length l, there + * should be a unique split l1 and l2 such that any connection of length l + * will be made only by combining a left-hand/incoming connection of length + * l1 and a right-hand/outgoing connection of length l2. + */ + boolean checkTransitivityOutgoing(Fact fact) { + return fact.span() >= minTransitiveRight; + } +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/01489efb/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OWL2.java ---------------------------------------------------------------------- diff --git a/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OWL2.java b/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OWL2.java new file mode 100644 index 0000000..a4492e3 --- /dev/null +++ b/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OWL2.java @@ -0,0 +1,38 @@ +package mvm.rya.reasoning; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import org.openrdf.model.URI; +import org.openrdf.model.impl.ValueFactoryImpl; +import org.openrdf.model.vocabulary.OWL; + +/** + * Some useful OWL 2 URIs not in Sesame API. + */ +public class OWL2 { + private static URI uri(String local) { + return ValueFactoryImpl.getInstance().createURI(OWL.NAMESPACE, local); + } + public static final URI ASYMMETRICPROPERTY = uri("AsymmetricProperty"); + public static final URI IRREFLEXIVEPROPERTY = uri("IrreflexiveProperty"); + public static final URI PROPERTYDISJOINTWITH = uri("propertyDisjointWith"); + public static final URI ONCLASS = uri("onClass"); + public static final URI MAXQUALIFIEDCARDINALITY = uri("maxQualifiedCardinality"); +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/01489efb/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OwlClass.java ---------------------------------------------------------------------- diff --git a/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OwlClass.java b/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OwlClass.java new file mode 100644 index 0000000..64a19ba --- /dev/null +++ b/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OwlClass.java @@ -0,0 +1,489 @@ +package mvm.rya.reasoning; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.io.Serializable; +import java.util.HashSet; +import java.util.Set; + +import org.openrdf.model.Resource; +import org.openrdf.model.URI; +import org.openrdf.model.Value; +import org.openrdf.model.vocabulary.OWL; + +/** + * Contains all the schema information we might need about a class. + * <p> + * Rules applied dynamically by getter methods: + * <ul> + * <li> + * scm-cls States that every class is its own subclass and equivalent class, + * and is a subclass of owl:Thing. These facts are included by + * getSuperClasses and getEquivalentClasses. (It also states that + * owl:Nothing is a subclass of every class). + * <li> + * scm-eqc1 States that if two classes are equivalent, they are also + * subclasses. Equivalence is represented using subclass relations + * internally. + * <li> + * scm-eqc2 States that if two classes are each other's subclasses, they are + * also equivalent classes. + * </ul> + * Rules applied by explicitly calling methods once all data has been read in: + * <ul> + * <p> + * <li> + * scm-sco States that subClassOf is transitive. Computed by + * computeSuperClasses(). + * </ul> + */ +public class OwlClass implements Serializable { + private static final long serialVersionUID = 1L; + private Resource uri; + + // Relations to other classes: + private Set<OwlClass> superClasses = new HashSet<>(); + private Set<OwlClass> disjointClasses = new HashSet<>(); + private Set<OwlClass> complementaryClasses = new HashSet<>(); + + // If this class is referenced by property restrictions: + private Set<OwlClass> svfRestrictions = new HashSet<>(); + private Set<OwlClass> avfRestrictions = new HashSet<>(); + private Set<OwlClass> qcRestrictions = new HashSet<>(); + + // If this is a property restriction, Which propert(y/ies) does it apply to? + Set<OwlProperty> properties = new HashSet<OwlProperty>(); + // These represent the semantics of the restriction: + Set<OwlClass> svfClasses = new HashSet<>(); + Set<OwlClass> avfClasses = new HashSet<>(); + Set<OwlClass> qcClasses = new HashSet<>(); + Set<Value> values = new HashSet<>(); + int maxCardinality = -1; + int maxQualifiedCardinality = -1; + + OwlClass(Resource uri) { + this.uri = uri; + } + + public Resource getURI() { return uri; } + public void setURI(Resource uri) { this.uri = uri; } + + /** + * Add a superclass + */ + boolean addSuperClass(OwlClass c) { + return superClasses.add(c); + } + + /** + * Add an equivalent class + * RL rule scm-eqc1: Store equivalence as mutual subClassOf relations + */ + boolean addEquivalentClass(OwlClass c) { + boolean change = superClasses.add(c); + change = c.superClasses.add(this) || change; + return change; + } + /** + * Add a disjoint class + */ + boolean addDisjoint(OwlClass c) { return disjointClasses.add(c); } + /** + * Add a complementary class + */ + boolean addComplement(OwlClass c) { return complementaryClasses.add(c); } + /** + * Add a someValuesFrom restriction on this class + */ + boolean addSvfRestriction(OwlClass r) { return svfRestrictions.add(r); } + /** + * Add an allValuesFrom restriction on this class + */ + boolean addAvfRestriction(OwlClass r) { return avfRestrictions.add(r); } + /** + * Add a qualified cardinality restriction on this class + */ + boolean addQCRestriction(OwlClass r) { return qcRestrictions.add(r); } + + /** + * Apply RL rule scm-sco: subClassOf transitivity. + * Follows subClassOf chains to compute all the ancestor classes. Assumes + * the hierarchy is small enough that a simple BFS is fine. + * @return Whether new information was discovered + */ + boolean computeSuperClasses() { + Set<OwlClass> ancestors = new HashSet<OwlClass>(); + Set<OwlClass> frontier = new HashSet<OwlClass>(superClasses); + while (!frontier.isEmpty()) { + Set<OwlClass> next = new HashSet<OwlClass>(); + for (OwlClass ancestor : frontier) { + // This node is an ancestor; it's parents should be explored next + ancestors.add(ancestor); + next.addAll(ancestor.superClasses); + } + // Don't revisit nodes + next.removeAll(ancestors); + frontier = next; + } + boolean newInfo = !ancestors.equals(superClasses); + superClasses = ancestors; + return newInfo; + } + + /** + * Add all of this class' ancestors to the domain of a given property. + */ + void inheritDomains(OwlProperty prop) { + for (OwlClass superclass : this.superClasses) { + prop.addDomain(superclass); + } + } + + /** + * Add all of this class' ancestors to the range of a given property. + */ + void inheritRanges(OwlProperty prop) { + for (OwlClass superclass : this.superClasses) { + prop.addRange(superclass); + } + } + + /** + * Add "onProperty p" information, and tell p to point back here. + */ + public boolean addProperty(OwlProperty property) { + property.addRestriction(this); + return properties.add(property); + } + + /** + * Add "someValuesFrom c" information, and tell c to point back here. + */ + public boolean addSvf(OwlClass targetClass) { + targetClass.addSvfRestriction(this); + return svfClasses.add(targetClass); + } + + /** + * Add "allValuesFrom c" information, and tell c to point back here. + */ + public boolean addAvf(OwlClass targetClass) { + targetClass.addAvfRestriction(this); + return avfClasses.add(targetClass); + } + + /** + * Add "onClass c" information, and tell c to point back here. + */ + public boolean addClass(OwlClass targetClass) { + targetClass.addQCRestriction(this); + return qcClasses.add(targetClass); + } + + /** + * Add "hasValue v" information. + */ + public boolean addValue(Value v) { + return values.add(v); + } + + /** + * Set a maxCardinality. + */ + public boolean setMaxCardinality(Value v) { + int mc = Integer.parseInt(v.stringValue()); + if (maxCardinality < 0 || mc < maxCardinality) { + maxCardinality = mc; + return true; + } + return false; + } + + /** + * Set maxQualifiedCardinality. + */ + public boolean setMaxQualifiedCardinality(Value v) { + int mqc = Integer.parseInt(v.stringValue()); + if (maxQualifiedCardinality < 0 || mqc < maxQualifiedCardinality) { + maxQualifiedCardinality = mqc; + return true; + } + return false; + } + + + /** + * Get all the superclasses of this subclass. Includes self and owl:Thing. + */ + public Set<Resource> getSuperClasses() { + Set<Resource> ancestors = new HashSet<>(); + for (OwlClass ancestor : superClasses) { + ancestors.add(ancestor.uri); + } + // RL rule scm-cls: Every class is a subclass of itself and owl:Thing + ancestors.add(this.uri); + ancestors.add(OWL.THING); + return ancestors; + } + + /** + * Get all the equivalent classes, meaning those who are both subclasses + * and superclasses of this one. + */ + public Set<Resource> getEquivalentClasses() { + // RL rule scm-eqc2: mutual subClassOf relations imply equivalentClass + Set<Resource> equivalents = new HashSet<>(); + for (OwlClass other : superClasses) { + if (other.superClasses.contains(this)) { + equivalents.add(other.uri); + } + } + // RL rule scm-cls: Every class is its own equivalent + equivalents.add(this.uri); + return equivalents; + } + + /** + * Get all classes declared disjoint with this one. + */ + public Set<Resource> getDisjointClasses() { + Set<Resource> disjoint = new HashSet<>(); + for (OwlClass other : disjointClasses) { + disjoint.add(other.uri); + } + return disjoint; + } + + /** + * Get all classes declared complement to a specific class. + */ + public Set<Resource> getComplementaryClasses() { + Set<Resource> complements = new HashSet<>(); + for (OwlClass other : complementaryClasses) { + complements.add(other.uri); + } + return complements; + } + + /** + * Get all someValuesFrom restrictions on this class + */ + public Set<Resource> getSvfRestrictions() { + Set<Resource> restrictions = new HashSet<>(); + for (OwlClass r : svfRestrictions) { + restrictions.add(r.getURI()); + } + return restrictions; + } + + /** + * Get all allValuesFrom restrictions on this class + */ + public Set<Resource> getAvfRestrictions() { + Set<Resource> restrictions = new HashSet<>(); + for (OwlClass r : avfRestrictions) { + restrictions.add(r.getURI()); + } + return restrictions; + } + + /** + * Get all onClass (qualified cardinality) restrictions on this class + */ + public Set<Resource> getQCRestrictions() { + Set<Resource> restrictions = new HashSet<>(); + for (OwlClass r : qcRestrictions) { + restrictions.add(r.getURI()); + } + return restrictions; + } + + /** + * Get the onProperty relation(s) for this property restriction. + */ + public Set<URI> getOnProperty() { + Set<URI> onp = new HashSet<>(); + for (OwlProperty prop : properties) { + onp.add(prop.getURI()); + } + return onp; + } + + /** + * Get all someValuesFrom relations for this property restriction. + */ + public Set<Resource> someValuesFrom() { + Set<Resource> targets = new HashSet<>(); + for (OwlClass c : svfClasses) { + targets.add(c.getURI()); + } + return targets; + } + + /** + * Get all allValuesFrom relations for this property restriction. + */ + public Set<Resource> allValuesFrom() { + Set<Resource> targets = new HashSet<>(); + for (OwlClass c : avfClasses) { + targets.add(c.getURI()); + } + return targets; + } + + /** + * Get all onClass relations for this property restriction. + */ + public Set<Resource> onClass() { + Set<Resource> targets = new HashSet<>(); + for (OwlClass c : qcClasses) { + targets.add(c.getURI()); + } + return targets; + } + + /** + * Get all hasValue relations for this property restriction. + */ + public Set<Value> hasValue() { return new HashSet<Value>(values); } + + /** + * Get the maxCardinality. Negative means it was not specified, otherwise + * returns the lowest value ever given. + */ + public int getMaxCardinality() { return maxCardinality; } + + /** + * Get the maxQualifiedCardinality. Negative means it was not specified, + * otherwise returns the lowest value ever given. + */ + public int getMaxQualifiedCardinality() { return maxQualifiedCardinality; } + + /** + * Compares someValuesFrom target classes, and returns true if this one's + * is a subclass of the other's. + */ + boolean svfSubClass(OwlClass other) { + for (OwlClass svfClass : this.svfClasses) { + Set<Resource> intersection = svfClass.getSuperClasses(); + intersection.retainAll(other.someValuesFrom()); + if (!intersection.isEmpty()) { + return true; + } + } + return false; + } + + /** + * Compares someValuesFrom target classes, and returns true if this one's + * is a subclass of the other's. + */ + boolean avfSubClass(OwlClass other) { + for (OwlClass avfClass : this.avfClasses) { + Set<Resource> intersection = avfClass.getSuperClasses(); + intersection.retainAll(other.allValuesFrom()); + if (!intersection.isEmpty()) { + return true; + } + } + return false; + } + + /** + * Compares onProperty properties, and returns true if this one's + * is a subproperty of the other's. + */ + boolean onSubProperty(OwlClass other) { + Set<URI> otherProp = other.getOnProperty(); + for (OwlProperty prop : this.properties) { + Set<URI> intersection = prop.getSuperProperties(); + intersection.retainAll(otherProp); + if (!intersection.isEmpty()) { + return true; + } + } + return false; + } + + /** + * Apply property restriction rules that involve the same class/value + * and properties related by subPropertyOf. + * RL rule scm-hv: [subprop hasValue] subClassOf [superprop hasValue] + * RL rule scm-svf2: [subprop someValuesFrom x] subClassOf [superprop someValuesFrom x] + * RL rule scm-avf2: [superprop allValuesFrom x] subClassOf [subprop allValuesFrom x] + * Doesn't check subproperty transitivity. + * @return Whether any information was generated + */ + boolean compareRestrictions(OwlClass other) { + boolean newInfo = false; + // These rules apply iff the restrictions are on subprop and superprop + if (this.onSubProperty(other)) { + // scm-hv + Set<Value> sharedValues = new HashSet<>(this.values); + sharedValues.retainAll(other.values); + if (!sharedValues.isEmpty()) { + newInfo = this.addSuperClass(other) || newInfo; + } + else { + // scm-svf2 + // (same result as scm-hv, no need to derive twice) + Set<OwlClass> sharedSvf = new HashSet<>(this.svfClasses); + sharedSvf.retainAll(other.svfClasses); + if (!sharedSvf.isEmpty()) { + newInfo = this.addSuperClass(other) || newInfo; + } + } + // scm-avf2 + // (applies in the other direction) + Set<OwlClass> sharedAvf = new HashSet<>(this.avfClasses); + sharedAvf.retainAll(other.avfClasses); + if (!sharedAvf.isEmpty()) { + newInfo = other.addSuperClass(this) || newInfo; + } + } + return newInfo; + } + + /** + * Get all superclasses of the target(s) of any someValuesFrom relations + * this class has, including the target class itself and any transitive + * superclasses. + */ + Set<Resource> getSvfSuperClasses() { + Set<Resource> svfSuperClasses = new HashSet<>(); + for (OwlClass svfClass : svfClasses) { + svfSuperClasses.addAll(svfClass.getSuperClasses()); + } + return svfSuperClasses; + } + + /** + * Get all superclasses of the target(s) of any allValuesFrom relations + * this class has, including the target class itself and any transitive + * superclasses. + */ + Set<Resource> getAvfSuperClasses() { + Set<Resource> avfSuperClasses = new HashSet<>(); + for (OwlClass avfClass : avfClasses) { + avfSuperClasses.addAll(avfClass.getSuperClasses()); + } + return avfSuperClasses; + } +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/01489efb/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OwlProperty.java ---------------------------------------------------------------------- diff --git a/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OwlProperty.java b/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OwlProperty.java new file mode 100644 index 0000000..ed0a3f3 --- /dev/null +++ b/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OwlProperty.java @@ -0,0 +1,309 @@ +package mvm.rya.reasoning; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.io.Serializable; +import java.util.HashSet; +import java.util.Set; + +import org.openrdf.model.Resource; +import org.openrdf.model.URI; + +/** + * Contains all the schema information we might need about a property. + * + * Rules implemented dynamically by getter methods: + * + * scm-op States that every object property is its own subproperty and + * equivalent property. + * scm-dp States that every datatype property is its own subproperty and + * equivalent property. + * scm-eqp1 States that if two properties are equivalent, they are also + * subproperties. Equivalence is represented this way internally. + * scm-eqp2 States that if two properties are each other's subproperties, + * they are also equivalent properties. + * + * Rules implemented explicitly by calling methods once all the necessary data + * has been read in: + * + * scm-spo States that subPropertyOf is transitive; computed by + * computeSuperProperties(). + * scm-dom1 States that a property with domain c also has as domain any + * of c's superclasses. Computed in inheritDomainRange(). + * scm-dom2 States that a property inherits its superproperties' domains. + * Computed in inheritDomainRange(). + * scm-rng1 States that a property with range c also has as domain any + * of c's superclasses. Computed in inheritDomainRange(). + * scm-rng2 States that a property inherits its superproperties' ranges. + * Computed in inheritDomainRange(). + * svm-svf1 States that property restriction c1 is a subclass of another c2 if + * they are someValuesFrom restrictions on the same property where + * c1's target class is a subclass of c2's target class. + * Computed in compareRestrictions(), depends on subclass info. + * svm-avf1 States that property restriction c1 is a subclass of another c2 if + * they are allValuesFrom restrictions on the same property where + * c1's target class is a subclass of c2's target class. + * Computed in compareRestrictions(), depends on subclass info. + */ +public class OwlProperty implements Serializable { + private static final long serialVersionUID = 1L; + + private URI uri; + + // Boolean qualities the property might have + private boolean transitive = false; + private boolean symmetric = false; + private boolean asymmetric = false; + private boolean functional = false; + private boolean inverseFunctional = false; + private boolean irreflexive = false; + + // Relations to other properties + private Set<OwlProperty> superProperties = new HashSet<OwlProperty>(); + private Set<OwlProperty> disjointProperties = new HashSet<OwlProperty>(); + private Set<OwlProperty> inverseProperties = new HashSet<OwlProperty>(); + + // Relations to classes + private Set<OwlClass> domain = new HashSet<OwlClass>(); + private Set<OwlClass> range = new HashSet<OwlClass>(); + + // Restrictions on this property + private Set<OwlClass> restrictions = new HashSet<OwlClass>(); + + OwlProperty(URI uri) { + this.uri = uri; + } + + boolean addSuperProperty(OwlProperty p) { + return superProperties.add(p); + } + + /** + * Add an equivalient property + * RL rule scm-eqp1: Store equivalence as mutual subPropertyOf relations + */ + boolean addEquivalentProperty(OwlProperty p) { + boolean change = this.superProperties.add(p); + change = p.superProperties.add(this) || change; + return change; + } + + boolean addDisjoint(OwlProperty p) { return disjointProperties.add(p); } + boolean addInverse(OwlProperty p) { return inverseProperties.add(p); } + boolean addDomain(OwlClass c) { + return domain.add(c); + } + boolean addRange(OwlClass c) { + return range.add(c); + } + boolean addRestriction(OwlClass r) { return restrictions.add(r); } + + public void setURI(URI uri) { this.uri = uri; } + void setTransitive() { transitive = true; } + void setSymmetric() { symmetric = true; } + void setAsymmetric() { asymmetric = true; } + void setFunctional() { functional = true; } + void setInverseFunctional() { inverseFunctional = true; } + void setIrreflexive() { irreflexive = true; } + + public URI getURI() { return uri; } + public boolean isTransitive() { return transitive; } + public boolean isSymmetric() { return symmetric; } + public boolean isAsymmetric() { return asymmetric; } + public boolean isFunctional() { return functional; } + public boolean isInverseFunctional() { return inverseFunctional; } + public boolean isIrreflexive() { return irreflexive; } + + /** + * Apply RL rule scm-spo: subPropertyOf transitivity. + * Follows subPropertyOf chains to compute all the ancestor properties. + * Assumes the hierarchy is small enough that a simple BFS is fine. + * @return Whether new information was discovered + */ + boolean computeSuperProperties() { + Set<OwlProperty> ancestors = new HashSet<OwlProperty>(); + Set<OwlProperty> frontier = new HashSet<OwlProperty>(superProperties); + while (!frontier.isEmpty()) { + Set<OwlProperty> next = new HashSet<OwlProperty>(); + for (OwlProperty ancestor : frontier) { + // This node is an ancestor; it's parents should be explored next + ancestors.add(ancestor); + next.addAll(ancestor.superProperties); + } + // Don't revisit nodes + next.removeAll(ancestors); + frontier = next; + } + boolean newInfo = !ancestors.equals(superProperties); + superProperties = ancestors; + return newInfo; + } + + /** + * Infer domain and range from parents' domains and ranges. Only looks at + * those superproperties that are explicitly known; computeSuperProperties + * should generally be called first to get the full closure. + */ + void inheritDomainRange() { + //RL rule scm-dom2: (p2 domain c) && (p1 subPropertyOf p2) -> (p1 domain c) + //RL rule scm-rng2: (p2 range c) && (p1 subPropertyOf p2) -> (p1 range c) + for (OwlProperty ancestorProperty : superProperties) { + for (OwlClass c : ancestorProperty.domain) { + addDomain(c); + } + for (OwlClass c : ancestorProperty.range) { + addRange(c); + } + } + //RL rule scm-dom1: (p domain c1) && (c1 subClassOf c2) -> (p domain c2) + for (OwlClass domainClass : new HashSet<OwlClass>(this.domain)) { + domainClass.inheritDomains(this); + } + //RL rule scm-rng1: (p range c1) && (c1 subClassOf c2) -> (p range c2) + for (OwlClass rangeClass : new HashSet<OwlClass>(this.range)) { + rangeClass.inheritRanges(this); + } + } + + /** + * Get all the superproperties of this subproperty. + */ + public Set<URI> getSuperProperties() { + Set<URI> ancestors = new HashSet<>(); + for (OwlProperty ancestor : superProperties) { + ancestors.add(ancestor.uri); + } + // RL rules scm-op & scm-dp: Every property is a subproperty of itself + ancestors.add(this.uri); + return ancestors; + } + + /** + * Get all the equivalent properties for this property. + * Apply RL rules scm-op and scm-dp: Every property is its own equivalent. + */ + public Set<URI> getEquivalentProperties() { + Set<URI> equivalents = new HashSet<>(); + for (OwlProperty other : superProperties) { + if (other.superProperties.contains(this)) { + equivalents.add(other.uri); + } + } + // RL rules scm-op & scm-dp: Every property is equivalent to itself + equivalents.add(this.uri); + return equivalents; + } + + /** + * Get all properties declared disjoint with this one. + */ + public Set<URI> getDisjointProperties() { + Set<URI> disjoint = new HashSet<>(); + for (OwlProperty other : disjointProperties) { + disjoint.add(other.uri); + } + return disjoint; + } + + /** + * Get all properties declared inverse of this one. + */ + public Set<URI> getInverseProperties() { + Set<URI> inverse = new HashSet<>(); + for (OwlProperty other : inverseProperties) { + inverse.add(other.uri); + } + return inverse; + } + + /** + * Get the domain (set of class URIs/Resources). + */ + public Set<Resource> getDomain() { + Set<Resource> domain = new HashSet<>(); + for (OwlClass d : this.domain) { + domain.add(d.getURI()); + } + return domain; + } + + /** + * Get the range (set of class URIs/Resources). + */ + public Set<Resource> getRange() { + Set<Resource> range = new HashSet<>(); + for (OwlClass r : this.range) { + range.add(r.getURI()); + } + return range; + } + + /** + * Get the property restrictions relevant to this property. + */ + public Set<Resource> getRestrictions() { + Set<Resource> restrictions = new HashSet<>(); + for (OwlClass pr : this.restrictions) { + restrictions.add(pr.getURI()); + } + return restrictions; + } + + /** + * Apply property restriction rules that involve the same property. + * RL rule scm-svf1: [someValuesFrom sub] subClassOf [someValuesFrom super] + * RL rule scm-avf1: [allValuesFrom sub] subClassOf [allValuesFrom super] + * Doesn't check subclass transitivity. + * @return Whether any information was generated + */ + public boolean compareRestrictions() { + boolean newInfo = false; + for (OwlClass c1 : restrictions) { + // Get all superclasses of this restriction's avf target class(es) + // and avf target classes. + Set<Resource> avfSuperClasses = c1.getAvfSuperClasses(); + Set<Resource> svfSuperClasses = c1.getSvfSuperClasses(); + if (avfSuperClasses.isEmpty() && svfSuperClasses.isEmpty()) { + continue; + } + // Compare each other restriction's avf and svf targets to the + // appropriate set of superclasses. + for (OwlClass c2 : restrictions) { + //svm-svf1, svm-avf1 + if (c1 != c2) { + Set<Resource> avf2 = c2.allValuesFrom(); + avf2.retainAll(avfSuperClasses); + if (avf2.isEmpty()) { + Set<Resource> svf2 = c2.someValuesFrom(); + svf2.retainAll(svfSuperClasses); + if (svf2.isEmpty()) { + continue; + } + } + // If c2's target is one of the parent classes of c1's + // target, then c2 is a more general version of c1 and + // therefore a superclass of c1. + newInfo = c1.addSuperClass(c2) || newInfo; + } + } + } + return newInfo; + } +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/01489efb/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OwlRule.java ---------------------------------------------------------------------- diff --git a/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OwlRule.java b/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OwlRule.java new file mode 100644 index 0000000..efdb628 --- /dev/null +++ b/extras/rya.reasoning/src/main/java/mvm/rya/reasoning/OwlRule.java @@ -0,0 +1,78 @@ +package mvm.rya.reasoning; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +/** + * Represents the OWL RL/RDF rules used in reasoning. + */ +public enum OwlRule { + // Schema rules, handled by Schema: + SCM_CLS, + SCM_SCO, + SCM_EQC1, + SCM_EQC2, + SCM_OP, + SCM_DP, + SCM_SPO, + SCM_EQP1, + SCM_EQP2, + SCM_DOM1, + SCM_DOM2, + SCM_RNG1, + SCM_RNG2, + SCM_HV, + SCM_SVF1, + SCM_SVF2, + SCM_AVF1, + SCM_AVF2, + + // Instance rules, handled by LocalReasoner: + CLS_NOTHING2("No resource can have type owl:Nothing"), + PRP_IRP("owl:IrreflexiveProperty -- Resource can't be related to itself via irreflexive property"), + PRP_DOM("rdfs:domain -- Predicate's domain implies subject's type"), + PRP_RNG("rdfs:range -- Predicate's range implies object's type"), + CAX_SCO("owl:subClassOf -- Infer supertypes"), + // Combine prp-inv1 and prp-inv2, since inverseOf is symmetric: + PRP_INV("owl:inverseOf -- Relation via one property implies reverse relation via the inverse property"), + PRP_SPO1("rdfs:subPropertyOf -- Relation via subproperty implies relation via superproperty"), + PRP_SYMP("owl:SymmetricProperty -- Relation via this property is always bidirectional"), + CLS_SVF2("owl:someValuesFrom(owl:Thing) -- Infer membership in the set of resources related via this property to anything"), + CLS_HV2("owl:hasValue -- Infer membership in the set of all resources having a specific property+value"), + CLS_HV1("owl:hasValue -- Infer a specific property+value from the subject's membership in the set of resources with that property+value"), + + // Combine multiple instance triples, handled by LocalReasoner: + PRP_ASYP("owl:AsymmetricProperty -- Asymmetric property can't be bidirectional"), + PRP_PDW("owl:propertyDisjointWith -- Two disjoint properties can't relate the same subject and object"), + CAX_DW("owl:disjointWith -- Resource can't belong to two disjoint classes"), + CLS_COM("owl:complementOf -- Resource can't belong to both a class and its complement"), + CLS_MAXC1("owl:maxCardinality(0) -- Max cardinality 0 for this property implies subject can't have any relation via the property"), + CLS_MAXQC2("owl:maxQualifiedCardinality(0/owl:Thing) -- Max cardinality 0 (with respect to owl:Thing) implies subject can't have any relation via the property"), + PRP_TRP("owl:TransitiveProperty -- Infer transitive relation"), + CLS_SVF1("owl:someValuesFrom -- Infer membership in the set of resources related via this property to an instance of the appropriate type"), + CLS_AVF("owl:allValuesFrom -- Infer the object's type from the subject's membership in the set of resources whose values for this property all belong to one type"), + + NONE("No rule given"); + + public String desc; + OwlRule() { desc = this.toString(); } + OwlRule(String desc) { + this.desc = desc; + } +}
