Top Engine Code

/////////////////////////////////////////////////////////////////////////////////////////////////////
// SUMMARY OF RESULTS
//
/////////////////////////////////////////////////////////////////////////////////////////////////////
    
    Test profile:
        Insert triples ([1..50], [101..150], [1..50])
        Inserted 125000 triples in 0.24 sec.
        
        part B (using Resources and Predicates)
        part C (using indexes only)
        Executing queries 1000 times    
        
        Find all triples ("s:2", ?v, ?w):
        Counted 2500 triples, ok
        
        Find all triples (s?, "p:102", "o:4"):
        Counted 50 triples, ok
        
        Find all triples ("s:3", ?p, "o:3"):
        Counted 50 triples, ok
        
        Find all triples (?u, ?v, ?w):
        Counted 125000 triples, ok
        
    
    Results on Laptop:
        Inserted 125000 triples in 0.24 sec.
        Part B: Queries executed in 22.95 sec, total test in 23.19 sec. Physical memory used 16,856 KB
        Part C: Queries executed in 4.51 sec, total test in 4.77 sec. Physical memory used 16,848 KB
        Same test profile using JRDF: 58 sec, Physical memory 226,700 KB
    
    Results on Desktop (dragon):
        Inserted 125000 triples in 0.18 sec.
        Part B: Queries executed in 14.7 sec, total test in 14.88 sec. Physical memory used 16,848 KB
        Part C: Queries executed in 3.75 sec, total test in 3.93 sec. Physical memory used 16,848 KB
        Same test profile using JRDF: 60 sec, Physical memory 226,100 KB


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Rule Engine v05
// 12/23/2006
//
/////////////////////////////////////////////////////////////////////////////////////////////////////
    
    Rule engine perform inferring correctly. However, rdf graph needs to keep tract of reference count on inferred triples, see results on unit test case test_rule_engine4.
    
    Re-executed results on Laptop:
        Inserted 125000 triples in 0.24 sec.
        Part B: Queries executed in 23.24 sec, total test in 23.48 sec. Physical memory used 16,908 KB
        Part C: Queries executed in 5.56 sec, total test in 5.8 sec. Physical memory used 16,908 KB
    
    Model with rdf_graph_uv, results:
        Inserted 125000 triples in 7.69 sec.
        Part B: Queries executed in 34.51 sec, total test in 42.15 sec. Physical memory used 58,956 KB
        Part C: Queries executed in 9.2 sec, total test in 16.89 sec. Physical memory used 58,956 KB


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Rule Engine v06
// 12/26/2006
//
/////////////////////////////////////////////////////////////////////////////////////////////////////
    
    Rule engine with index_graph (rdf_graph) using index_graph that keeps track of reference count for
    the inferred graph only using custom class rdf::internal::wc_type. Requires a custom hash function and equal predicate that consider the w index only.
    
    Re-executed results on Laptop (rdf_graph<index_type>, i.e., w/o ref counting):
        Inserted 125000 triples in 0.23 sec.
        Part B: Queries executed in 22.79 sec, total test in 23.03 sec. Physical memory used 16,908 KB
        Part C: Queries executed in 4.26 sec, total test in 4.49 sec. Physical memory used 16,908 KB
    
    Results on Laptop (rdf_graph<wc_type>, i.e., w ref counting):
        Inserted 125000 triples in 0.28 sec.
        Part B: Queries executed in 22.81 sec, total test in 23.09 sec. Physical memory used 16,908 KB
        Part C: Queries executed in 4.08 sec, total test in 4.36 sec. Physical memory used 16,908 KB


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Rule Engine v07
// 12/29/2006
//
/////////////////////////////////////////////////////////////////////////////////////////////////////
    
    rule_engine::explain_why completed, unit test updated.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Rule Engine v08
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    Infinite loop detection capability in place, exception is thrown when a loop is detected.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Rule Engine v09
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Rule event log implemented. Ability to print out trace log of the inferring process. 
      Usefull for debugging infinite loop caused by rules or data.

    o Clean up of beta_relation use of const.


=======================================================================================================
RENAMED to Top Engine
=======================================================================================================

/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v01
// 1/2/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Based on Rule Engine v09
    o Code refactored, changed the index_type to be a pointer to resource_base to provide quick access
      to resource attributes from index_type.

    Results on Laptop (rdf_graph with w ref counting and new index_type):
        Inserted 125000 triples in 0.23 sec.
        Part B: Queries executed in 4.08 sec, total test in 4.31 sec. Physical memory used 16,848 KB
        Part C: Queries executed in 4.5  sec, total test in 4.73 sec. Physical memory used 16,848 KB



/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v02
// 1/10/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Implemented rule expressions permitting literals with a set of operators.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v03
// 1/11/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Backward chaining integrated with forward (rete-based) chaining added.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v04
// 1/21/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Added knowledge_base class to manage the rule creation and configuration.
    o Optimize the rules by re-ordering the terms in the rule body.
    o Optimize the rules by factoring common rule terms in rule body across rules in
      the rule graph.
    o Need more test cases on the optimization features.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v05
// 1/23/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Added query rules.
    o Optimize the rules by factoring common rule terms in rule body across rules in
      the rule graph.
    o Need more test cases on the optimization features.

    o TODO: hadhoc queries - can be done by creating a rule_engine and knowledge_base
        on the fly. API would need to be on a separate class (hadhoc_query) which
        would create the current classes - rule_engine, knowledge_base, knowledge_rule,
        and rule_session, etc.
    o TODO: Augment the backward chaining capability to deal with variable. To do this need 
        to have multiple nodes at the head rule (or use virtual class) to manage the
        various combinations.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v06
// 1/26/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Rewrote backward chaining capability to enable the use of variables in
      the rule head term. Optimization of the backward chaining capability to avoid firing the same rule twice.

    o Added rule dependency graph capability to knowledge base. This allows to navigate
      between rule based on dependency on each other.

    o Added simple print capability to show rule dependency graph. 

    o TODO: Query rules and backward chaining rules are not using the optimization feature that factor out
        common rule terms since they each have their own root vertex in the graph. Need the capability to root them on
        the same node so to be able to factor out common terms while preserving the fact that they get fired individually.

    o TODO: hadhoc queries - can be done by creating a rule_engine and knowledge_base
        on the fly. API would need to be on a separate class (hadhoc_query) which
        would create the current classes - rule_engine, knowledge_base, knowledge_rule,
        and rule_session, etc.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v07
// 1/30/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Optimization of backward and query rules completed.
    o Backward chaining rules re-use rule terms of forward chaining rules for efficiency.
    o Query rules cannot re-use rule terms since they may have parameters (_1, ...)

    o TODO: Detection of vicious cycle in rule dependency graph.
    o TODO: Rule parser.
    o TODO: Had hoc query.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v08
// 2/01/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o In provision of the parser and support of metadata graph, remove the class predicate.

    o TODO: Detection of vicious cycle in rule dependency graph.
    o TODO: Rule parser.
    o TODO: Had hoc query.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v09
// 2/03/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Initial implementation of parser completed!! Works for all 3 rule types.

    o TODO: Detection of vicious cycle in rule dependency graph. (using rules on meta graph)
    o TODO: Had hoc query.
    o TODO: Built-in rule predicate to calculate multiplicity of relations.
    o TODO: Built-in rule predicate to create new instances from rules.
    
    o BUG: When compiling rules with optimization flag on, looks like it re-order negated
           terms without regards of the dependency of their variables.
    o BUG: When compiling rules with optimization flag on, need not to remove variable from
           indexes for filter attached to rule term.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v10
// 2/05/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Bug fixed - Rule compilation with optimization flag enabled
    o Bug fixed - Rule term shared between forward and backward rules

    o TODO: Clean up the depricated api
    o TODO: Use knowledge_term as the rule_vertex property object. -- major cleanup!
    o TODO: Detection of vicious circle in rule dependency graph. (using rules on meta graph)
    o TODO: Had hoc query.
    o TODO: Built-in rule predicate to calculate multiplicity of relations.
    o TODO: Built-in rule predicate to create new instances from rules.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v11
// 2/06/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Refactored the api and cleaned up the code.
    o Ported previous test cases.

    o TODO: Clean up the print out messages in kb_parse and in inferrence.
    o TODO: Detection of vicious cycle in rule dependency graph. (using rules on meta graph)
    o TODO: Had hoc query.
    o TODO: Built-in rule predicate to calculate multiplicity of relations.
    o TODO: Built-in rule predicate to create new instances from rules.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v12
// 2/11/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Added a SAX parser that import owl ontology into the rdf database. This will provide enhance testing
      of the rule engine.

    o TODO: Clean up the print out messages in kb_parse and in inferrence.
    o TODO: Detection of vicious cycle in rule dependency graph. (using rules on meta graph)
    o TODO: Had hoc query.
    o TODO: Built-in rule predicate to calculate multiplicity of relations.
    o TODO: Built-in rule predicate to create new instances from rules.

    
    Potential bug in protege (or jena) which produce the following construct:
    
          <owl:Class>
            <owl:unionOf rdf:parseType="Collection">
              <rdf:Description rdf:about="http://www.w3.org/2002/07/owl#Thing"/>
              <owl:Class rdf:about="#Automobile"/>
            </owl:unionOf>
          </owl:Class>
    
    
    This should simply collaps to:
    
          <owl:Class rdf:about="#Automobile"/>
    
    Currently the owl import utility will reduce it to a collection of a single item. Rules will need
    to exist to cleanup and remove the collection construct.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v13
// 2/17/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Added the ability to use resource in the expression terms.
    o Added operator on resources, including create_bnode, create_resource, and create_literal.
    o Major rework of beta_relation and rule_session classes. Many fixes pertaining to negation and
        propagation on the rete network.
    o Temporarily removed the rule salience, causing segmentation fault. Need testing.

    o BUG: When keeping the explain information, additional field are keept in the relation_row
        of the consequent terms causing duplicate triples to be inferred causing incorrect results
        when those triples are subsequetly retracted due to reference count. 
    o TODO: Replace the explain-why facility and re-use the execution trace information.
    o TODO: Clean up the print out messages in kb_parse and in inferrence.
    o TODO: Detection of vicious cycle in rule dependency graph. (using rules on meta graph)
    o TODO: Had hoc query.
    o TODO: Built-in rule predicate to calculate multiplicity of relations.

    o NOTE: using 'valgrind -v ./Debug/top-engine-utest-owl' for checking on memory allocation and segmentation faults.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v14
// 2/22/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Major cleanup and rework of beta_relation and explain_why, and rule_events.
    o Rule salience restored.

    o ERROR: top-utest-expression fails on literals.
    o ERROR: top-utest-parse fails with a segmentation fault.
    
    o TODO: Engine debugger facility.
    o TODO: Clean up the print out messages in kb_parse and in inferrence.
    o TODO: Detection of vicious cycle in rule dependency graph. (using rules on meta graph)
    o TODO: Had hoc query.
    o TODO: Built-in rule predicate to calculate multiplicity of relations.

    o NOTE: using 'valgrind -v ./Debug/top-engine-utest-owl' for checking on memory allocation and segmentation faults.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v15
// 2/25/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Clean up code and remove added node in import concerning parse type of collection.
    o Fix errors from previous release.

    o TODO: Engine debugger facility.
    o TODO: Clean up the print out messages in kb_parse and in inferrence.
    o TODO: Detection of vicious cycle in rule dependency graph. (using rules on meta graph)
    o TODO: Had hoc query.
    o TODO: Built-in rule predicate to calculate multiplicity of relations.

    o NOTE: using 'valgrind -v ./Debug/top-engine-utest-owl' for checking on memory allocation and segmentation faults.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v16
// 3/13/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Implementation of rules for OWL TBox Reasoning Service. Rules implemented for the
      following entailements:

        
        =================================================
        - Classes logical entailments:
        =================================================
            o Notation:
                - (A = B):      A owl:equivalentClass B
                - (A ~= B):     A owl:complementOf B
                - (A != B):     A owl:disjointWith B
                - (A < B):      A rdfs:subClassOf B
                - (A ^ B):      A conjunction B
                - (A | B):      A disjunction B
                - (a is A):     a is an individual of type A
                - (a = b):      a owl:sameAs b, (a, b) are individuals
                - (a != b):     a owl:differentFrom b, (a, b) are individuals
                - (a < A):      A owl:oneOf a, a is an individual, A is a class
                - (P1 < P2):    P1 rdfs:subPropertyOf P2
      
      
        - Class subsumption logical entailment:
        -------------------------------------------------

            o rdfs:subClassOf is transitive: (A < B) and (B < C) => (A < C)

            o Ensure all classes (owl:Class) are rdfs:subClassOf owl:Thing.

            o Ensure all restriction classes (owl:Restriction) are rdfs:subClassOf owl:Thing.

            o In OWL DL an individual can never be at the same time a class: 
              classes and individuals form disjoint domains.
      
            
        - Equivalent classes logical entailments (owl-test-case-08):
        -------------------------------------------------

            o owl:equivalentClass is symetric: (A = B) => (B = A)

            o owl:equivalentClass is transitive: (A = B) ^ (B = C) => (A = C)

            o owl:equivalentClass subsume each other: (A = B) => (A < B) and (B < A)

            o expression with conjuctions: (A = (B ^ C)) => (A < B) and (A < C)
            
            o The owl:intersectionOf property links a class to a list of class descriptions. An owl:intersectionOf 
              statement describes a class for which the class extension contains precisely those individuals that 
              are members of the class extension of all class descriptions in the list.
              In other words, determine that a class is a subset of a class defined by the conjuction of some of it's 
              base classes:
              (A = (A1 ^ A2...An)) and (B < A1) ... (B < An) => (B < A)

            o expression with disjunction: (A = (B | C)) => (B < A) and (C < A)
            
            o A disjuction of classes contained in a disjuction of a greater number of classes is a subset:
              (A = (A1 | A2...An)) and (B = (A1 | A2...Am)) and (m <= n) => (B < A)
      
        
        - Disjoint classes logical entailments (owl-test-case-09):
        -------------------------------------------------

            o owl:disjointWith is symetric: (A != B) => (B != A)

            o A class is disjoint with subclasses of it's disjoint class: (A != B) and (C < B) => (A != C) 

            o A class is disjoint with classes disjoint with it's equivalent class: (A = B) and (B != C) => (A != C) 
                > [this rule is implied from above]

            o Subclasses of disjoint classes are disjoint: (A != B) and (C < A) and (D < B) => (C != D)

            o A class subclass of 2 disjoint classes is owl:Nothing: (A < B) and (A < C) and (B != C) => (A < 0)
      
        
        - Complement classes logical entailments (owl-test-case-10):
        -------------------------------------------------

            o owl:complementOf is symetric: (A ~= B) => (B ~= A)

            o Complement classes are disjoint: (A ~= B) => (A != B)

            o A class can have only one complement class: (A ~= B) and (B ~= C) => (A = C)
      
            
        - Class equivalence constructed as enumeration set (owl-test-case-11):
        -------------------------------------------------

            o Individuals that are equivalent are in same enumerated sets: (a < A) and (a = b) => (b < A)

            o Identify equivalent set constructed with same individuals: all(a < A) and (a < B) => (A < B)

            o Identify equivalence of individuals (owl:sameAs) for sets known to be equivalent: 
                (A = B) and (a < A) and (b < B) and not(a != b) => (a = b)
            
            o An enumerated class not the subset of it's super-class must be empty:
                (A < B) and (a1 < A) and not(a1 < B) => (A < 0)
            
            o Empty enumerated set must have it's enumerated individuals of type Nothing:
                (A < 0) and (a1 < A)  => (a1 < 0)
      
                
        - Enumerated set with all individuals of rdf:type owl:Nothing is equivalent 
          (sub set of) to class owl:Nothing.

        
        =================================================
        - Individuals logical entailments (owl-test-case-12):
        =================================================

            o owl:sameAs is symetric: (a = b) => (b = a)

            o owl:sameAs is transitive: (a = b) and (b = c) => (a = c)
            
            o owl:sameAs individuals have same type: (a = b) and (a < A) => (b < A)
            
            o SameAs individuals participate in same relations: (x = y) and P(x, z) => P(y, z)
            
            o SameAs individuals participate in same relations: (z = z1) and P(x, z) => P(x, z1)

            o owl:differentFrom is symetric: (a != b) => (b != a)

            o Same individuals have common different individuals: (a = b) and (b != c) => (a != c)

            o owl:distinctMembers is syntactic sugar to owl:differentFrom
        

        - Apply class membership to individuals.
        -------------------------------------------------

            o Individuals must have rdf:type as specified by class hierarchy: (a < A) and (A < B) => (a < B)

            o Individuals member of two classes that are disjoint must be owl:Nothing: 
              (a < A) and (a < B) and (A != B) => (a < 0)

            o Individual can only be same as and different from another one if it is owl:Nothing.
              (a = b) and (a != b) => (a < 0)

        
        =================================================
        - Properties logical entailements (owl-test-case-13):
        =================================================

            o Ensure to have both owl:ObjectProperty and owl:DatatypeProperty subclasses of the RDF 
              class rdf:Property

            o Subject must be of type specified by the property domain: P(x, y) and (P domain C) => (x < C)

            o Object must be of type specified by the property range: P(x, y) and (P range C) => (y < C)

            o Property with empty range (range of disjoint classes) are inconsistent (top:propertyError)

            o Property with empty domain (disjoint classes in domain) are inconsistent (top:propertyError)

        
        - Subproperties logical entailments:
        -------------------------------------------------

            o In OWL DL the subject and object of a subproperty (rdfs:subPropertyOf) statement must be either both 
              datatype properties or both object properties.

            o Subproperty must have sub-domain parent property: 
              (P1 < P2) and (P1 domain C1) and (P2 domain C2) => (P1 domain (C1 ^ C2)) (conjunction of domain.)

            o Subproperty must have sub-range of parent property:
              (P1 < P2) and (P1 range C1) and (P2 range C2) => (P1 range (C1 ^ C2)) (conjunction of range.)

            o Transitivity of subproperty relation: (P1 < P2) and (P2 < P3) => (P1 < P3)
            
            o Inheritance of properties: P1(x, y) and (P1 < P2) => P2(x, y)

        
        - Equivalent properties logical entailments:
        -------------------------------------------------

            o owl:equivalentProperty is symetric and transitive.

            o owl:equivalentProperty have same domain and range.
            
            o owl:equivalentProperty construct can be used to state that two properties have the same property extension:
                (P1 = P2) => (P1 < P2) and (P2 < P1)
                (P1 < P2) and (P2 < P1) => (P1 = P2)
        
        
        - Inverse properties logical entailments:
        -------------------------------------------------

            o owl:inverseOf is applicable to owl:ObjectProperty.

            o owl:inverseOf is symetric.

            o owl:inverseOf have domain and range interchanged.

            o P1 owl:inverseOf P2: P1(x, y) => P2(y, x)
        
        
        - Functional properties logical entailments:
        -------------------------------------------------

            o owl:FunctionalProperty can have only one value.
        
        
        - Inverse Functional properties logical entailments:
        -------------------------------------------------

            o owl:InverseFunctionalProperty is an owl:ObjectProperty.

            o Inverse functional uniquely defines the subject in a triple:
              P(x1, y) and P(x2, y) => (x1 = x2)


        - Transitive properties logical entailments:
        -------------------------------------------------

            o owl:TransitiveProperty is an owl:ObjectProperty.

            o P rdf:type owl:TransitiveProperty: P(x, y) and P(y, z) => P(x, z)

            o OWL DL requires that for a transitive property no local or global cardinality constraints 
              should be declared on the property itself or its superproperties, nor on the inverse of the 
              property or its superproperties.

            o The superproperty of a transitive property is also a transitive property.
        
        - Symetric properties logical entailments:
        -------------------------------------------------

            o owl:SymmetricProperty is an owl:ObjectProperty.

            o P rdf:type owl:SymmetricProperty: P(x, y) => P(y, x)

            o The domain and range of a symmetric property are the same.

        
        =================================================
        - Property Restriction logical entailements:
        =================================================

        
        - All Values From logical entailments (owl-test-case-04):
        -------------------------------------------------

            o Describe a class of all individuals for which all values of the property under consideration 
              are either members of the class extension of the class description or are data values within 
              the specified data range:
                  P all-values-from Y, for X: all y: P(x, y) and (y < Y) => (x < X)
              
            o Analogous to the universal (for-all) quantifier of Predicate logic:
                  P all-values-from Y, for X: (x < X) and P(x, y) => (y < Y)

        
        - Some Values From logical entailments (owl-test-case-05):
        -------------------------------------------------

            o Describes a class of all individuals for which at least one value of the property 
              concerned is an instance of the class description or a data value in the data range:
                  P some-values-from Y, for X: exist y: P(x, y) and (y < Y) => (x < X)
              
            o Analogous to the existential quantifier of Predicate logic;
              for each instance of the class that is being defined, 
              there exists at least one value for P that fulfills the constraint:
                  P some-values-from Y, for X: (x < X) => P(x, y) and (y < Y) [exist at least one y]
                    - Note: Logical entailments of owl:someValuesFrom consist in determining the consistency
                            of the individuals member of class with the Some Value From restriction.
                    - Note: (x < X) and P(x, y) does not entails (y < Y)

        
        - Has Values logical entailments:
        -------------------------------------------------

            o Describes a class of all individuals for which the property concerned has at least one value 
              semantically equal to y (owl-test-case-06):
                  P has_value y, for X: P(x, y) => (x < X)
              
            o All member of the described class must have at least one value sematically equal to y
              (owl-test-case-06):
                  P has-value y, for X: (x < X) = > P(x, y) [exist at least one y]

            o When the property concerned is a Transitive Property, then this class may be subclass
              to another one describing the set of individual with value obtained from transitivity
              (owl-test-case-07):
                  P has-value y, for X: as P(X, y)
                  P is-transitive:
                  P has-value y2, for X2: as P(X2, y2)
                        P(X, y) and P(X2, y2) and P(y, y2) => (X < X2)

        
        - owl:maxCardinality logical entailments (owl-test-case-14):
        -------------------------------------------------

            o Describes a class of all individuals that have at most N semantically distinct values 
              (individuals or data values) for the property concerned, where N is the value of the 
              cardinality constraint.
                - Identify the individuals: for X: (#P(x, y) .le. n) => (x < X)
                - Validate restriction: for X: (x < X) and not(#P(x, y) .le. n) => (x < 0)


        - owl:minCardinality logical entailments (owl-test-case-15):
        -------------------------------------------------

            o Describes a class of all individuals that have at least N semantically distinct values 
              (individuals or data values) for the property concerned, where N is the value of the 
              cardinality constraint.
                - Identify the individuals: for X: (#P(x, y) .ge. n) => (x < X)
                - Validate restriction: for X: (x < X) and not(#P(x, y) .ge. n) => (x < 0)


        - owl:cardinality logical entailments (owl-test-case-16):
        -------------------------------------------------

            o Describes a class of all individuals that have exactly N semantically distinct values 
              (individuals or data values) for the property concerned, where N is the value of the 
              cardinality constraint.
                - Identify the individuals: for X: (#P(x, y) .eq. n) => (x < X)
                - Validate restriction: for X: (x < X) and not(#P(x, y) .eq. n) => (x < 0)


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v17
// 3/16/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////


        Benchmark results
        =================
            
            - Compile as 'release'
            - Case wine ontology, (wine.owl, wine.trd):
                
                o option: default explain enabled, no lookup indexes, base beta relation size    : 75.5 sec.
                o option: default explain disabled, no lookup indexes, base beta relation size   : 73.5 sec.
                o option: default explain disabled, with lookup indexes, base beta relation size : 9.6 sec.
                o option: as previous and optimized rule rule_intersect_axiom 2,3                : 8.1 sec.
                o option: as previous and removed rule_disjoint_class 1,2  (incorrect - is back) : 7.6 sec.
                o option: as previous and default size the beta relation to 1000                 : 7.4 sec.
                
                o final version of rules, w/o explain, w/ lookup indexes, 
                        beta relation of default size:                                           : 7.5 sec.

                        rule execution statistics:
                        
                        Number of times each rule fired (sorted by name):
                        Total is: 42,816 inferred triples
                        
                            err_rule_cardinality2                                       : 9
                            err_rule_min_cardinality2                                   : 8
                            err_rule_some_value_from3                                   : 15
                            rule_all_value_from1                                        : 546
                            rule_all_value_from2                                        : 2022
                            rule_all_value_from3                                        : 575
                            rule_cardinality1                                           : 257
                            rule_class_restriction                                      : 174
                            rule_disjoint_class1                                        : 5
                            rule_distinct_memb_axiom                                    : 1670
                            rule_domain_inverse_prop1                                   : 2
                            rule_gate_cardinality1                                      : 990
                            rule_gate_cardinality2                                      : 1034
                            rule_gate_cardinality3                                      : 55
                            rule_gate_cardinality4                                      : 94
                            rule_gate_cardinality5                                      : 266
                            rule_gate_cardinality6                                      : 257
                            rule_has_value1                                             : 1766
                            rule_has_value2                                             : 1766
                            rule_has_value3                                             : 32
                            rule_ind_membership1                                        : 8405
                            rule_inherited_base_class2                                  : 9646
                            rule_intersect_axiom1                                       : 127
                            rule_intersect_axiom2                                       : 5120
                            rule_intersect_axiom3                                       : 375
                            rule_max_cardinality1                                       : 990
                            rule_min_cardinality1                                       : 49
                            rule_not_empty_set                                          : 70
                            rule_oneof_axiom1                                           : 1746
                            rule_oneof_axiom2                                           : 121
                            rule_pair_inverse_prop1                                     : 198
                            rule_prop1                                                  : 16
                            rule_prop2                                                  : 1
                            rule_prop3                                                  : 682
                            rule_prop4                                                  : 886
                            rule_range_inverse_prop1                                    : 2
                            rule_some_value_from1                                       : 176
                            rule_some_value_from2                                       : 176
                            rule_sub_class_thing                                        : 175
                            rule_sub_prop11                                             : 5
                            rule_sub_prop2                                              : 4
                            rule_sub_prop3                                              : 4
                            rule_sub_prop6                                              : 251
                            rule_subsume_equ_class                                      : 114
                            rule_sym_inverse_prop1                                      : 4
                            rule_symetric_prop1                                         : 1
                            rule_symetric_prop2                                         : 2
                            rule_symetric_prop3                                         : 1
                            rule_symetric_prop4                                         : 1
                            rule_symetry_of_different_from                              : 1664
                            rule_symetry_of_disjoint_class                              : 8
                            rule_symetry_of_equ_class                                   : 114
                            rule_trans_prop1                                            : 1
                            rule_trans_prop2                                            : 136
                            rule_union_axiom1                                           : 2




            - Case copay ontology, (copay.owl, copay.trd):
                
                o option: default explain disabled, with lookup indexes, base beta relation size : 102.0 sec.
                o option: as previous and optimized rule rule_intersect_axiom 2,3                : 81.3 sec.
                o option: as previous and removed rule_disjoint_class 1,2  (incorrect - is back) : 36.4 sec.
                o option: as previous and default size the beta relation to 1000   (reset the default after test) : 36.8 sec.
                o option: default explain enabled, rule event logging, rule optimized            : 35.8 sec.
                
                o final version of rules, w/o explain, w/ lookup indexes, 
                        beta relation of default size:                                           : 84.5 sec.

                        rule execution statistics:
                        
                        Number of times each rule fired (sorted by name):
                        Total is: 251,369 (inferred triples)
                        
                            err_rule_oneof_axiom4                                       : 24
                            rule_class_restriction                                      : 682
                            rule_complement_class1                                      : 2
                            rule_complement_class2                                      : 2
                            rule_disjoint_class1                                        : 41367
                            rule_disjoint_class2                                        : 81230
                            rule_domain_inverse_prop1                                   : 2
                            rule_ind_membership1                                        : 1239
                            rule_inherited_base_class2                                  : 57721
                            rule_intersect_axiom1                                       : 282
                            rule_intersect_axiom2                                       : 600
                            rule_intersect_axiom3                                       : 406
                            rule_inv_funct_prop1                                        : 1
                            rule_prop1                                                  : 122
                            rule_prop2                                                  : 50
                            rule_range_inverse_prop1                                    : 2
                            rule_sub_class_thing                                        : 271
                            rule_sub_prop11                                             : 8
                            rule_sub_prop2                                              : 11
                            rule_sub_prop3                                              : 11
                            rule_subsume_equ_class                                      : 526
                            rule_sym_inverse_prop1                                      : 2
                            rule_symetry_of_disjoint_class                              : 21638
                            rule_symetry_of_equ_class                                   : 526
                            rule_trans_of_equ_class                                     : 24
                            rule_union_axiom1                                           : 350
                            rule_union_axiom2                                           : 44104
                            rule_union_axiom3                                           : 166


    o Added rule statistics collection to support the analysis of rule execution.

    o TODO: Engine debugger facility.
    o TODO: Detection of vicious cycle in rule dependency graph. (using rules on meta graph)
    o TODO: Had hoc query.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v18
// 3/20/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////


    o Converted the projects using top-engine as a shared library.

    o TODO: Engine debugger facility.
    o TODO: Detection of vicious cycle in rule dependency graph. (using rules on meta graph)
    o TODO: Had hoc query.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v19
// 3/26/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////


    o Completed bindings to python.

    o TODO: Engine debugger facility.
    o TODO: Detection of vicious cycle in rule dependency graph. (using rules on meta graph)
    o TODO: Had hoc query.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v20
// 4/12/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

# Apply logical consequences of
# owl:complementOf
#
    > Need to add rule about individuals!!

    o TODO: Add a class description to top_class that returns either the class name or a string 
      representing the class expression.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v21
// 4/17/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Moved to kdevelop IDE! This is to unify all development under the same IDE and use a
      portable build system; automake (configure; make; make install)

/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v22
// 4/19/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Added psearch! Still have to integrate psearch to rule_session.

/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v23
// 4/23/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o PSearch integrated minimally - nodes and patterns are rdf::index_type!
      Need to further integrate with knowledge_base and the knowledge_base configuration file.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v24
// 4/27/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o The sematics of psearch is extended to perform searching of patterns that 
      incorporate some constructs from description logic:
      
        - Patterns have the following attributes:
            o index_type to uniquely identify the pattern.
            o set of node_index_type as neccessairy and sufficient criteria - aka c1 (new.)
            o set of node_index_type as neccessairy criteria - aka c2; c2 includes c1 nodes.
            o set of negated node_index_type to exclude the pattern from a query.
        
        - Nodes have the following attribures:
            o index_type to uniquely identify the node.
            o bool flag is_skip_pattern_activation for pattern selection.
            o set of patterns for which the node is included in the pattern's 
              neccessairy and sufficient criteria (pattern's c1 criteria).
        
        - During the execution of a query, a pattern is activated when:
            o the index_type of a 'has' node is also the index_type of a pattern (new.)
            o all the pattern's c1 nodes are also in the session's 'has' nodes (new.)
            o patterns are filtered out by negated nodes.
        
        - The psearch session's filter flag (usefull for authoring or testing):
            o all_relevant: includes all pattern even if the session's 'has' nodes is a subset of pattern's c1 nodes.
            o strictly_relevant: includes only patterns for which all c1 nodes are in the session's 'has' nodes.
    
    o Incorporate PSearchDB into knowledge_base.
    o Unit test cases for psearch added.
    o Need to export psearch api to python.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v25
// 5/01/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Add inferrence capability to psearch. The inference algorithm is:
    
        1 Compute the union of all patterns that may be activated using the psearch session's has nodes.
          Do not filter out any patterns.
          
        2 Take the pattern of highest weight, do:
            o check that c1 criteria is meet.
            o check if pattern is negated from psearch session's has not nodes.
            o check if pattern is negated from psearch sesson's has nodes.
            
        3 Infer nodes from pattern's c2 node set:
            o Add node(s) to working session node set (asserted + inferred node)
            o Add all related patterns to the list computed in 1.
            o Create/update nsc
            o Check if node(s) negate any pattern that was previously negated. If so put them onto
              the negated pattern list.
            o Create psc and register pattern's negated nodes.
            
        4 Process the negated pattern list, for each pattern:
            o For each c2 node of pattern, update nsc by reducing the frequency by 1.
            o If node's frequency is 0 and node's activation is inferred, remove node from
              working session set. Also put all related patterns onto the negated pattern list.
            o Process list untill negated pattern list is empty.
            
        5 Process next pattern of highest weight, untill list is empty (go to step 2).
    
    o Python bindings added for psearch with unit test cases.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v26
// 5/02/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Updated the psearch API:
    
        - PSearchSession is created by rule_engine and managed using a session id.
        - PSearchQuery and PSearchInfer are helper classes used internally by PSearchSession
          and not exposed externally.

    o py_top_web_client in progress to add psearch capability.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v27
// 5/02/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Updated the rdf_graph API:

        - added capability to find triples based on resource names.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v28
// 5/11/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Added Category class to psearch.
    o Modified the semantics of psearch query versus infer; query is a 'look ahead' with filtering on Category.
    o Completed the basic web interface to psearch.
    o Persistence of psearch db in the knowledge base meta graph.
    o psearch db import and export from web client.
    


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v29
// 5/17/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Added Rule class to psearch.
    o Patterns are generated from Rule class.
    o Removed the ability of having a pattern to be a node as well.
    o Added the ability to have an existential relationship between Rule and Category. This
      result in a 'or' relationship between the Rule and the Nodes of the Category;
      A Pattern is created for each node of the Category.
    o Ability to copy Rule.
    o Rule, Category, and Node have a name attribute with is unique per type.
    o Updated the Rule Editor.
    o Added meta graph visible to rdf session find methods.
    o Improved usability by of rule editor and psearch session pages. 


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v30
// 5/29/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Completed psearch Interview editor.
    o Improvements on API of rdf_graph and rdf_session, updated literal interface for literal of type string.
      Need to do the same improvement for other types as well.
    o Remain to do the Interview Runtime component.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v31
// 6/5/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Completed Interview Runtime application.
    o Fixed the literal issue relating to uri vs content.
    o Added capability to import/export rdf session as well as meta graph in a single file.
    o Improved api on Top Engine for usage from python.
    o CSS need to be completed for Interview Engine.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v32
// 6/9/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Top Engine / Interview Engine Version 0.9
    o Added regressing testing using Selenium IDE (partially complete)


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v33
// 6/11/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Regression testing added for following use case:
        o Creating New Knowledge Base
        o Executing Interview after completion of Knowledge Base creation (same session)
        o Importing Knowledge Base and executing Interview

    o Tooltips added using YAHOO library.
    
    o Regression testing use case TODO:
        o Importing Interview Session.
        o Case with multiple Interviews defined in single Knowledge Base.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v34
// 6/14/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Migrated to Mandriva 2007.1
        o Boost and xerces library are now system libraries.

    o Simplified interface for Rule Editor and Page / Interview ordering.
    o Regression testing to create new KB is working. Need to upgrade other scripts.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v35
// 7/11/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Added domain predicate to Question
    o Added domain class to Category
    o During the solicitation, a triple is asserted using the domain predicate with the answers.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v36
// 7/26/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Added file upload for OWL models, Interview KB, and Interview Sessions.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v37
// 8/17/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Added encode / decode of rdf graph and knowledge base.
    o Session persistence using files implemented for web client.
    o OWL import is broken with session persistence.
    o Optimization of page load by having a single css file and a single js file
      implemented for ISPageView.tmpl. This use a cat scipt in the cheetah_top_compile script.


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v38
// 8/19/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o OWL import is fixed for small model - session persistence implemented where the inferred
      model is computed each time the session is restored. Can be a problem for larger ontology.
    o Need to perform test on OWL Import. May need to move the inferred triples into the aserted 
      graph to avoid recomputing the logical entailements of the OWL model.

/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v39
// 8/20/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Session persistence implemented for both OWL import and interview session.
        - OWL Import: Both the asserted and inferred graphs are serialized using encode / decode
        - Interview session; only the asserted graph is serialized and the inferred graph
          is recalculated on session reload.

      
/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v40
// 8/22/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Moved to Anjuta IDE (gnome)
        - When running Configure script, use following parameters:
            o for Degug: CXXFLAGS='-O0 -g3'
            o for release: CXXFLAGS='-O2 -g0'

    o Small bug fix in deserialization of interview model to comply to new api.

    o Note on deployment w/ CherryPy under Apache:
      Must use the svn 3.0.X branch AND file modpython_gateway.py. The last one must be
      put in the site-packages of the python install.

    o Project must now be in directory '/home/michel/projects/top-engine'


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v41
// 8/23/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Deployed on AMS with url http://top.dufresneconsulting.com/topengine
        - IP address is 72.44.50.15

    o Bug fixes in model serialization and de-serialization.

    o Web page added for home of top.dufresneconsulting.com 
      (will be Top Engine project of sourceforge.net)


/////////////////////////////////////////////////////////////////////////////////////////////////////
// Top Engine v42
// 9/XX/2007
//
/////////////////////////////////////////////////////////////////////////////////////////////////////

    o Updated YUI to current version 2.3.0

    o Removed table scrolling, put json support w/ server-side pagination

    o Support for IE7 and Firefox 2