Util/SemWeb/Reasoning.cs

   1 using System;
   2 using System.Collections;
   3
   4 namespace SemWeb.Reasoning {
   5         public class InferenceStore : Store {
   6
   7                 Store store;
   8                 ReasoningEngine engine;
   9
  10                 public InferenceStore(Store store, ReasoningEngine engine) {
  11                         this.store = store;
  12                         this.engine = engine;
  13                 }
  14
  15                 public Store Source { get { return store; } }
  16                 public ReasoningEngine Engine { get { return engine; } }
  17
  18                 public override int StatementCount { get { return store.StatementCount; } }
  19
  20                 public override void Clear() { store.Clear(); }
  21
  22                 public override Entity[] GetAllEntities() {
  23                         return store.GetAllEntities();
  24                 }
  25
  26                 public override Entity[] GetAllPredicates() {
  27                         return store.GetAllPredicates();
  28                 }
  29
  30                 public override void Add(Statement statement) {
  31                         store.Add(statement);
  32                 }
  33
  34                 public override void Remove(Statement statement) {
  35                         store.Remove(statement);
  36                 }
  37
  38                 public override void Import(StatementSource source) {
  39                         store.Import(source);
  40                 }
  41
  42                 public override void Select(Statement template, SelectPartialFilter partialFilter, StatementSink result) {
  43                         // If the template is a full statement (has a subject, predicate,
  44                         // and object), use the specialized routine to check if the statement
  45                         // is asserted in the source.
  46                         if (!template.AnyNull) {
  47                                 if (Contains(template))
  48                                         result.Add(template);
  49                                 return;
  50                         }
  51
  52                         // For each matching statement, find further entailments that match the template.
  53                         result = new ReasoningStatementSink(template, result, this);
  54                         Source.Select(template, partialFilter, result);
  55
  56                         // Do specialized querying based on the template.
  57                         Engine.Select(template, result, Source);
  58                 }
  59
  60                 public override void Select(Statement[] templates, SelectPartialFilter partialFilter, StatementSink result) {
  61                         throw new NotImplementedException();
  62                 }
  63
  64                 public override bool Contains(Statement statement) {
  65                         if (statement.AnyNull)
  66                                 throw new ArgumentNullException();
  67
  68                         if (Source.Contains(statement))
  69                                 return true;
  70
  71                         return Engine.IsAsserted(statement, Source);
  72                 }
  73
  74                 public override void Replace(Entity a, Entity b) {
  75                         store.Replace(a, b);
  76                 }
  77
  78                 public override void Replace(Statement find, Statement replacement) {
  79                         store.Replace(find, replacement);
  80                 }
  81
  82                 public override Entity[] FindEntities(Statement[] filters) {
  83                         return store.FindEntities(filters);
  84                 }
  85
  86                 private class ReasoningStatementSink : StatementSink {
  87                         Statement template;
  88                         StatementSink store;
  89                         InferenceStore inference;
  90
  91                         public ReasoningStatementSink(Statement template, StatementSink store, InferenceStore inference) { this.template = template; this.store = store; this.inference = inference; }
  92
  93                         public bool Add(Statement statement) {
  94                                 inference.Engine.SelectFilter(ref statement, inference.Source);
  95                                 store.Add(statement);
  96                                 inference.Engine.FindEntailments(statement, template, store, inference.Source);
  97                                 return true;
  98                         }
  99                 }
 100         }
 101
 102         public abstract class ReasoningEngine {
 103                 public virtual bool IsAsserted(Statement statement, Store source) {
 104                         return false;
 105                 }
 106
 107                 public virtual void FindEntailments(Statement statement, Statement template, StatementSink result, Store source) {
 108                 }
 109
 110                 public virtual void Select(Statement statement, StatementSink result, Store source) {
 111                 }
 112
 113                 public virtual void SelectFilter(ref Statement statement, Store source) {
 114                 }
 115         }
 116
 117         public class RDFSReasoning : ReasoningEngine {
 118                 public static readonly Entity rdfType = new Entity("http://www.w3.org/1999/02/22-rdf-syntax-ns#type");
 119                 public static readonly Entity rdfProperty = new Entity("http://www.w3.org/1999/02/22-rdf-syntax-ns#Property");
 120                 public static readonly Entity rdfsSubClassOf = new Entity("http://www.w3.org/2000/01/rdf-schema#subClassOf");
 121                 public static readonly Entity rdfsSubPropertyOf = new Entity("http://www.w3.org/2000/01/rdf-schema#subPropertyOf");
 122                 public static readonly Entity rdfsDomain = new Entity("http://www.w3.org/2000/01/rdf-schema#domain");
 123                 public static readonly Entity rdfsRange = new Entity("http://www.w3.org/2000/01/rdf-schema#range");
 124                 public static readonly Entity rdfsResource = new Entity("http://www.w3.org/2000/01/rdf-schema#Resource");
 125                 public static readonly Entity rdfsClass = new Entity("http://www.w3.org/2000/01/rdf-schema#Class");
 126                 public static readonly Entity rdfsLiteral = new Entity("http://www.w3.org/2000/01/rdf-schema#Literal");
 127
 128                 Hashtable closures = new Hashtable();
 129
 130                 private class PutInArraySink : StatementSink {
 131                         int spo;
 132                         ArrayList sink;
 133
 134                         public PutInArraySink(int spo, ArrayList sink) {
 135                                 this.spo = spo; this.sink = sink;
 136                         }
 137
 138                         public bool Add(Statement statement) {
 139                                 object obj = null;
 140                                 if (spo == 0) obj = statement.Subject;
 141                                 else if (spo == 1) obj = statement.Predicate;
 142                                 else if (spo == 2) obj = statement.Object;
 143                                 if (obj is Entity && !sink.Contains(obj))
 144                                         sink.Add(obj);
 145                                 return true;
 146                         }
 147                 }
 148
 149                 public ArrayList getClosure(Entity type, Store source, Entity relation, bool inverse) {
 150                         if (type.Uri == null) return new ArrayList();
 151
 152                         Hashtable closure = (Hashtable)closures[relation];
 153                         if (closure == null) {
 154                                 closure = new Hashtable();
 155                                 closures[relation] = closure;
 156                         }
 157
 158                         ArrayList items = (ArrayList)closure[type.Uri];
 159                         if (items != null) return items;
 160
 161                         items = new ArrayList();
 162
 163                         OWLReasoning.TransitiveSelect(type, type, relation, inverse, source, new PutInArraySink(inverse ? 0 : 2, items));
 164
 165                         // Everything is a subClassOf rdfs:Resource
 166                         if (relation == rdfsSubClassOf && !inverse && !items.Contains(rdfsResource))
 167                                 items.Add(rdfsResource);
 168
 169                         closure[type.Uri] = items;
 170                         return items;
 171                 }
 172
 173                 public ArrayList getSuperTypes(Entity type, Store source) {
 174                         return getClosure(type, source, rdfsSubClassOf, false);
 175                 }
 176                 public IList getSubTypes(Entity type, Store source) {
 177                         if (type.Uri == rdfsResource)
 178                                 return source.SelectSubjects(rdfType, rdfsClass);
 179                         return getClosure(type, source, rdfsSubClassOf, true);
 180                 }
 181                 public ArrayList getSuperProperties(Entity type, Store source) {
 182                         return getClosure(type, source, rdfsSubPropertyOf, false);
 183                 }
 184                 public ArrayList getSubProperties(Entity type, Store source) {
 185                         return getClosure(type, source, rdfsSubPropertyOf, true);
 186                 }
 187
 188                 public override bool IsAsserted(Statement statement, Store source) {
 189                         if (statement.Predicate == null || statement.Predicate.Uri == null) return false;
 190
 191                         // X rdf:type Y
 192                         if (statement.Predicate.Uri == rdfType && statement.Object is Entity) {
 193                                 Entity typeentity = rdfType;
 194
 195                                 // Check: Z rdf:subClassOf Y for all Z s.t. X rdf:type Z
 196                                 foreach (Resource type in source.SelectObjects(statement.Subject, typeentity)) {
 197                                         if (type is Entity && getSuperTypes((Entity)type, source).Contains(statement.Object))
 198                                                 return true;
 199                                 }
 200
 201                                 // Check: Z rdf:rdfType Y for all Z s.t. X rdf:subPropertyOf Z
 202                                 foreach (Resource type in source.SelectObjects(statement.Subject, rdfsSubPropertyOf)) {
 203                                         if (!(type is Entity)) continue;
 204                                         Statement st = new Statement((Entity)type, typeentity, statement.Object);
 205                                         if (source.Contains(st)) return true;
 206                                         if (IsAsserted(st, source)) return true;
 207                                 }
 208                         }
 209
 210                         // X rdfs:subClassOf Y
 211                         // Check if Y is in the supertypes array.
 212                         if (statement.Predicate.Uri == rdfsSubClassOf)
 213                                 return getSuperTypes(statement.Subject, source).Contains(statement.Object);
 214
 215                         // X rdfs:subPropertyOf Y
 216                         // Check if Y is in the superproperties array.
 217                         if (statement.Predicate.Uri == rdfsSubPropertyOf)
 218                                 return getSuperProperties(statement.Subject, source).Contains(statement.Object);
 219
 220                         // X rdfs:domain/range Y
 221                         // Check if Y is a subtype of any Z s.t. for any Q (X subPropertyOf Q) domain/range Z.
 222                         if ((statement.Predicate.Uri == rdfsDomain || statement.Predicate.Uri == rdfsRange) && statement.Object is Entity) {
 223                                 ArrayList supertypes = getSuperTypes((Entity)statement.Object, source);
 224                                 ArrayList preds = getSuperProperties(statement.Subject, source);
 225                                 preds.Add(statement.Predicate);
 226                                 foreach (Entity predicate in preds)
 227                                         foreach (Resource obj in source.SelectObjects(predicate, statement.Predicate))
 228                                                 if (supertypes.Contains(obj))
 229                                                         return true;
 230                         }
 231
 232                         return false;
 233                 }
 234
 235                 public override void Select(Statement template, StatementSink result, Store source) {
 236                         if (template.Predicate == null || template.Predicate.Uri == null) return;
 237
 238                         // X P Y
 239                         // Run a select for all Q s.t. Q subPropertyOf Y.
 240                         foreach (Entity predicate in getSubProperties(template.Predicate, source)) {
 241                                 source.Select(new Statement(template.Subject, predicate, template.Object), result);
 242                         }
 243
 244                         // X rdfs:domain/range Y
 245                         if ((template.Predicate.Uri == rdfsDomain || template.Predicate.Uri == rdfsRange) && template.Object != null && template.Object is Entity) {
 246                                 foreach (Entity type in getSuperTypes((Entity)template.Object, source))
 247                                         source.Select(new Statement(template.Subject, template.Predicate, type), result);
 248                         }
 249
 250                         // X rdf:type rdf:Property
 251                         // Return everything that is in the predicate position of a statement
 252                         if (template.Predicate.Uri == rdfType && template.Object != null && template.Object.Uri != null && template.Object.Uri == rdfProperty) {
 253                                 foreach (Entity predicate in source.GetAllPredicates())
 254                                         result.Add(new Statement(predicate, template.Predicate, template.Object));
 255                         }
 256                 }
 257
 258                 public override void FindEntailments(Statement statement, Statement template, StatementSink result, Store source) {
 259                         // X rdfs:subClassOf/subPropertyOf Y
 260                         // These are transitive, so add X p Z for all Z s.t. Y p Z.
 261                         if ((statement.Predicate.Uri == rdfsSubClassOf || statement.Predicate.Uri == rdfsSubPropertyOf) && statement.Object is Entity) {
 262                                 if (template.Object == null) {
 263                                         // Find forward transitive entailments.
 264                                         OWLReasoning.TransitiveSelect(statement.Subject, (Entity)statement.Object, statement.Predicate, false, source, result);
 265                                 } else if (template.Subject == null) {
 266                                         // Find inverse transitive entailments.
 267                                         OWLReasoning.TransitiveSelect((Entity)statement.Object, statement.Subject, statement.Predicate, true, source, result);
 268                                 }
 269                         }
 270
 271                         // X P Y
 272                         // Add X Q Y for all Q s.t. P rdfs:subPropertyof Q
 273                         foreach (Entity predicate in getSuperProperties(statement.Predicate, source))
 274                                 result.Add(new Statement(statement.Subject, predicate, statement.Object));
 275
 276                         // X rdfs:domain/range Y
 277                         // If the template is empty on the object, add all object subtypes.
 278                         // If the template is empty on the subject, all all subject subproperties.
 279                         if ((statement.Predicate.Uri == rdfsDomain || statement.Predicate.Uri == rdfsRange) && statement.Object is Entity) {
 280                                 if (template.Object == null)
 281                                         foreach (Entity type in getSubTypes((Entity)statement.Object, source))
 282                                                 result.Add(new Statement(statement.Subject, statement.Predicate, type));
 283                                 if (template.Subject == null)
 284                                         foreach (Entity type in getSubProperties(statement.Subject, source))
 285                                                 result.Add(new Statement(type, statement.Predicate, statement.Object));
 286                         }
 287                 }
 288
 289                 public override void SelectFilter(ref Statement statement, Store source) {
 290                         // When a literal without a datatype is selected, attempt to determine
 291                         // the data type from the rdfs:range of the predicate.
 292                         Literal lit = statement.Object as Literal;
 293                         if (lit != null && lit.DataType == null) {
 294                                 ArrayList predrange = new ArrayList();
 295                                 predrange.Add(statement.Predicate);
 296                                 predrange.AddRange(getSuperProperties(statement.Predicate, source));
 297                                 foreach (Entity predicate in predrange) {
 298                                         string newtype = null;
 299                                         foreach (Resource range in source.SelectObjects(predicate, rdfsRange)) {
 300                                                 if (range.Uri != null && range.Uri != rdfsLiteral) {
 301                                                         if (newtype == null)
 302                                                                 newtype = range.Uri;
 303                                                         else // Multiple types match -- not sure which this value falls in
 304                                                                 return;
 305                                                 }
 306                                         }
 307                                         if (newtype != null) {
 308                                                 statement = new Statement(statement.Subject, statement.Predicate, new Literal(lit.Value, lit.Language, newtype), statement.Meta);
 309                                                 return;
 310                                         }
 311                                 }
 312                         }
 313                 }
 314         }
 315
 316         public class OWLReasoning : ReasoningEngine {
 317                 public static readonly Entity rdfType = new Entity("http://www.w3.org/1999/02/22-rdf-syntax-ns#type");
 318                 public static readonly Entity owlInverseOf = new Entity("http://www.w3.org/2002/07/owl#inverseOf");
 319                 public static readonly Entity owlTransitive = new Entity("http://www.w3.org/2002/07/owl#TransitiveProperty");
 320                 public static readonly Entity owlSymmetric = new Entity("http://www.w3.org/2002/07/owl#SymmetricProperty");
 321                 public static readonly Entity owlFunctional = new Entity("http://www.w3.org/2002/07/owl#FunctionalProperty");
 322                 public static readonly Entity owlInverseFunctional = new Entity("http://www.w3.org/2002/07/owl#InverseFunctionalProperty");
 323
 324                 public static void TransitiveSelect(Entity subject, Entity start, Entity predicate, bool inverse, Store source, StatementSink result) {
 325                         new TransitiveFilter(source, result, subject, start, predicate, inverse);
 326                 }
 327
 328                 private class TransitiveFilter : StatementSink {
 329                         Store source;
 330                         StatementSink sink;
 331                         Entity subject, predicate;
 332                         bool inverse, checkSymmetric;
 333                         Hashtable seen = new Hashtable();
 334                         ArrayList newobjects = new ArrayList();
 335
 336                         public TransitiveFilter(Store source, StatementSink sink, Entity subject, Entity start, Entity predicate, bool inverse) {
 337                                 this.source = source; this.sink = sink; this.subject = subject; this.predicate = predicate;
 338
 339                                 seen[start] = seen;
 340                                 newobjects.Add(start);
 341                                 while (newobjects.Count > 0) {
 342                                         ArrayList list = (ArrayList)newobjects.Clone();
 343                                         newobjects.Clear();
 344                                         foreach (Entity e in list) {
 345                                                 this.inverse = inverse;
 346                                                 this.checkSymmetric = false;
 347                                                 source.Select(new Statement(!inverse ? e : null, predicate, inverse ? e : null), this);
 348
 349                                                 this.inverse = !inverse;
 350                                                 this.checkSymmetric = true;
 351                                                 source.Select(new Statement(inverse ? e : null, predicate, !inverse ? e : null), this);
 352                                         }
 353                                 }
 354                         }
 355                         public bool Add(Statement statement) {
 356                                 if (checkSymmetric) {
 357                                         bool isSym = source.Contains(new Statement(statement.Predicate, rdfType, owlSymmetric));
 358                                         if (!isSym) return true;
 359                                 }
 360
 361                                 Resource r = !inverse ? statement.Object : statement.Subject;
 362                                 if (statement.Object is Entity && !seen.ContainsKey(r)) {
 363                                         newobjects.Add(r);
 364                                         sink.Add(new Statement(!inverse ? subject : (Entity)r, predicate, inverse ? subject : (Entity)r));
 365                                 }
 366                                 seen[r] = seen;
 367                                 return true;
 368                         }
 369                 }
 370
 371                 public override void FindEntailments(Statement statement, Statement template, StatementSink result, Store source) {
 372                         // X P Y
 373                         // Where P is a owlTransitive
 374                         if (statement.Object is Entity && source.Contains(new Statement(statement.Predicate, rdfType, owlTransitive))) {
 375                                 if (template.Subject == null)
 376                                         TransitiveSelect((Entity)statement.Object, statement.Subject, statement.Predicate, true, source, result);
 377                                 if (template.Object == null) {
 378                                         TransitiveSelect(statement.Subject, (Entity)statement.Object, statement.Predicate, false, source, result);
 379                                 }
 380                         }
 381                 }
 382
 383
 384                 public override void Select(Statement template, StatementSink result, Store source) {
 385                         if (template.Predicate == null) return;
 386
 387                         // Run inverse properties and symmetric properties backwards
 388                         if (template.Object == null || template.Object is Entity) {
 389                                 // Create a filter that reverses the subject and object.
 390                                 InverseFilter filter = null;
 391
 392                                 // Find all Y Q X where P owl:inverseOf Q
 393                                 foreach (Resource inverse in source.SelectObjects(template.Predicate, owlInverseOf)) {
 394                                         if (filter == null) filter = new InverseFilter(template.Predicate, result);
 395                                         if (inverse is Entity)
 396                                                 source.Select(new Statement((Entity)template.Object, (Entity)inverse, template.Subject), filter );
 397                                 }
 398
 399                                 // Find all Y Q X where Q owl:inverseOf P
 400                                 foreach (Entity inverse in source.SelectSubjects(owlInverseOf, template.Predicate)) {
 401                                         if (filter == null) filter = new InverseFilter(template.Predicate, result);
 402                                         source.Select(new Statement((Entity)template.Object, inverse, template.Subject), filter );
 403                                 }
 404
 405                                 // If P owl:Symmetric, find all Y P X.
 406                                 if (source.Contains(new Statement(template.Predicate, rdfType, owlSymmetric))) {
 407                                         if (filter == null) filter = new InverseFilter(template.Predicate, result);
 408                                         source.Select(new Statement((Entity)template.Object, template.Predicate, template.Subject), filter );
 409                                 }
 410                         }
 411                 }
 412
 413                 internal class InverseFilter : StatementSink {
 414                         StatementSink sink;
 415                         Entity predicate;
 416                         public InverseFilter(Entity predicate, StatementSink sink) { this.predicate = predicate; this.sink = sink; }
 417                         public bool Add(Statement statement) {
 418                                 if (statement.Object is Entity)
 419                                         sink.Add(new Statement((Entity)statement.Object, predicate, statement.Subject));
 420                                 return true;
 421                         }
 422                 }
 423
 424         }
 425 }