Intelligent Sharing of Classes

Daniel J. Buehrer, Wang Chun-Yao

Institute of Computer Science and Information Engineering
National Chung Chung University, Chiayi 621 Taiwan ROC
dan@cs.ccu.edu.tw

Abstract

Class algebra [2-6] provides the logical basis for a distributed object-oriented data for the semantic web.  Class algebra provides a logical system in which all logical subclass containments are computable, even if no explicit database facts are specified.  After briefly describing the theory for normalizing class algebra queries so that the normal forms satisfy the laws of Boolean algebra, we present some examples of the Cadabia database user interface.  It should be clear from these examples that a Boolean algebra of binary relations provides a much friendlier environment for retrieving data than using relational database joins. 

1.	Introduction - The need for another logical reasoning system
Each mathematical model of reality has certain advantages and disadvantages.  So far, set theory has proven to be very valuable as a description mechanism for almost all scientific models.  However, set theory is based on first-order logic, which unfortunately has some queries which are only semi-decidable.  Other simpler logics such as propositional logic are decidable, but they are not powerful enough to describe complex systems.  The queries of class algebra provide a nice compromise, with powerful concepts of object-oriented programming, probability, and fuzzy theory combined with an efficient logical inference mechanism which is based on intuitionistic logic [7,8].  We determine a unique SDNF (Sorted Disjunctive Normal Form) for each class algebra expression.  These SDNF descriptions can be compared to check for "containment" or "equality", which in turn can imply a subset relationship between the sets of objects in the database that currently satisfy the expressions.  The decidability of the "containment problem" using only logical class/query definitions is the chief advantage of using class algebra.  The queries are also of “treewidth” 1 [9], which makes them computable in parallel time LOGCFL, (i.e. log time convertible to a context-free language problem)  which is better than the worst-case NP-complete time for SQL queries.
Other logics like first-order logic are usually not typed, and these logics generally cannot calculate the superclasses or subclasses of an arbitrary set of objects.  In class algebra, one can easily find superclasses, subclasses, superrelations, subrelations, complement classes, and complement relations, for either implicit or explicit classes and relations.  This makes it possible to quickly locate examples, counterexamples, analogies, isomorphisms, etc.  Needless to say, such a logical reasoning system will be of great value to all fields of research, including artificial intelligence.  It will also be very important for more practical applications like e-commerce, where it is necessary to agree upon common models of reality.
Class algebra uses logical containment expressions to define classes in terms of upper and lower bounds based on the attributes and binary relations of the class.  A class expression is thus an implicit definition of a rough set.  This rough set is based on the initial (minimal) model and the circumscription (maximal) model of a set of Horn clauses.  These initial model (i.e. the lower bound) is simply the set of those objects which can be proven to satisfy the class expression by direct (linear) proofs.  The circumscription (i.e. the upper bound) is the set of objects which cannot be proven to satisfy the pseudo-complement of the expression, using only direct proofs.  A state of the class algebra is obtained by a sequence of additions and deletions to such upper/lower bound definitions of classes, attributes, or relations.  

Table 1
Advantages of Class Algebra Theory

Classical Theory		   Advantages of Class Algebra
Finite Sets 	O(nm) worst-case time for query with n binary relations and at most m objects in each relation's value.
Each set has superclass "descriptions" [2].	
Infinite Sets	Query and complement are both enumerable in decreasing order of fuzzy values; anytime algorithm is epsilon decidable [5].	
Relational Algebra	Has IS-A hierarchy, inheritance of constraints on attributes, relations, and methods	
Description Logics	Since complements are computable, can, for instance, express a query to compute the leaves of a tree.  This is more than NP-expressive description logics can express.	
Probability 	Satisfies Boolean axioms; consistent logical inference for probability bounds for direct proofs.
Can get best IS-A hierarchy based on information theory.	
Fuzzy sets and Fuzzy Logic	Integrates fuzzy set theory and fuzzy logic.
Integrates fuzzy and probabilistic reasoning.	

The logical expressions that are used in class algebra do not contain "variables" or "arguments" in the sense of first-order logic.  Each binary relation, however, has implicit "this" and "value" arguments, and a single "true", "false", "unknown", or fuzzy interval as an output value.  The binary relations of class algebra can only be used as functions, with the "value" arguments being assigned to the "this" input variable of the next relation in a dotted expression.  Each implicit variable is used at most once as an input variable and at most once as an output variable.  This makes class algebra recursive, unlike the more general first-order logic, and it is thus possible to compute the normal form of a query, or to check if one query logically contains (i.e. is implied by) another query.   This theory can be fuzzified [5].
Class algebra has almost all of the advantages of object-oriented programming, including inheritance, encapsulation, and self-reflection.  It is thus much more "powerful" than propositional logic, which also does not have explicit variables or arguments.  However, class algebra retains prepositional logic’s ability to produce a normal form for any logical expression.  As in prepositional logic, it is possible to produce a sorted Karnough map.  This is equivalent to using resolution to find all non-subsumed consequents, and then sorting these.  Equivalently, in terms of the IS-A hierarchy, the normalization process finds those nodes above all and only the normalized query nodes.  The SDNF form is a kind of "minimal cover" of the terms of the original query.   By comparing the SDNF forms, it is easy to see whether or not one query (or class definition) implies another, and thus whether the set of objects satisfying that query is necessarily a subset of the other.

2. Getting Down to Basics
Like any universal algebra, class algebra is based on an implicit data structure.  Since class algebra has union, intersection, and difference operators that satisfy the laws of Boolean algebra, this structure is a lattice structure [1].  Each node is labeled by a disjunctive normal form, with a union node above each of its conjuncts, and each conjunct below each of its literals (i.e. nodes labeled by a single predicate or negated predicate).  The existence of this structure depends on the ability to "normalize" any class expression to determine the label of a unique node in this lattice.  For any given state of the class algebra, there are only a finite number of nodes in this lattice.  The upper/lower bounds of a class thus determine a computable region of the lattice.  Similarly, the upper/lower bounds of a binary relation determine a computable region within a pair of lattices.  From these lattices, it can be determined whether or not one class or relation is completely below or above another.  If node b is below node c, then for any object 0bj, when Obj.SDNF(b) produces a true value, Obj.SDNF(c) will also produce a true value, since b "inherits" all of the constraints of node c.  That is, the lower node b has more constraints than the upper node c.  Node b thus represents a subclass or sub-domain/range of node c, and the lattices represent the "IS-A" lattices of classes and relations.  The rather unique feature about class algebra is that this IS-A lattice also represents the logical implication relationships between the class algebra expressions which label each of the nodes.  A relationship "class1 IS-A class2" is equivalent to an implication relationship "(this) this.SDNF(class1)  this.SDNF(class2)".
The key feature of class algebra is the very close relationship between an implicit logical definition of a class or relation and its explicit set of members.  Class algebra has the ability to go either from the implicit logical definitions to a computable rough set of members, or from any set of members to a unique class and its superclasses.  Both of these tasks are computable.  
An object is simply a singleton class, where the object identifier has been specified in the class's invariant.  The class's SDNF expression is "oid = [oidvalue] && <this object's declared type's invariant>".   It is assumed that object identifiers cannot be reused when objects are deleted, except for retrieving backup versions of the objects.

3.	Defining lower and upper bounds
In class algebra, both sets and logical expressions are 3-valued.  That is, predicates have "true", "unknown", and "false" values, and sets have lower and upper bounds which represent the elements which are provably in the set or provably not in the complement set.  The expression  ">k(r,)" represents a 3-valued predicate which is "true" if the number of r which return "true" for  is greater than k (for a given "this").  It is "false" if the number of r which return "false" for  is greater than or equal to |r|-k.  It is "unknown" otherwise.  There is an isomorphism between the + (union), * (intersection), and complement operators for the rough sets, and the || (or), && (and) and complement operators of the 3-valued predicate expressions.  That is, the operators involving rough sets can be converted to logical operators, and vice versa, just as relational algebra expressions can be converted to/from relational calculus expressions.  
There is a lower and upper bound for the set of objects which satisfy ">k(r,)".  We say that reln.>k(r,) = [b, ~ -b], where b is the set of objects "this" for which this.r has more than k elements for which  evaluates to "true", and "~ -b" is the set of objects for which there are more than k elements which do not evaluate to false.
We describe the ternary Boolean operators in terms of the following binary Boolean functionals:
	t() = true if  returns "true"  (i.e. not "unknown" or  "false"), false otherwise
	u() = true if  returns "unknown" (i.e. not "true" or "false"), false otherwise
	f() = true if  returns "false" (i.e. not "true" or "unknown"), false otherwise
For an arbitrary 3-valued predicate expression , t() =  ~ ~ =  (even number of ~ and  - not ending in -).  Similarly, t()||u() = ~ -  = (even number of ~ and -)-.   
A class algebra expression  can contain two kinds of negation operators, "~" and "-".   The "-" pseudo-complement acts just like the true complement "~" unless it comes right before a predicate P, in which case the "-P" is treated like a predicate "not_P" whose value is independent of P’s value.

 Simplified 	  		t()		f()
  =   ~ where  is odd # of complement operators, either ~ or -	 t()	 f()	
~ =  ~  where  is an even # of complement operators, either ~ or -	 f()||u() =1 -t()	1-f()	
- =  -  	 f()	 t()	
~ -  =  -	 t()||u() =1-f()	 1-t()	
That is, after getting rid of the preceding complement operators, there are only four possible simplified expressions, depending on whether the operator in front of the predicate is ~ or -, and on whether there are an even or odd number of complements.
	The following rules can be seen to be true from the above table:
t(-) = f(), 
t(~) = f() || u() 
u(-) = u(~) = false
By using the fuzzy interval [t(),t()||u()]=[t(),1-f()], we can keep all of the information provided by the original 3-valued expression .  Since the value of – is independent of the value of , the computations of the lower and upper bounds of the rough set are also independent, and must both be computed.  However, it can be seen that the interval for r{~} simply flips around the lower and upper bounds for r{}.   Moreover, the normal forms of the class expressions are related even though their values are independent.  It is sufficient to simply write the class expression for the lower bound, since the class expression for the upper bound can be obtained by prefixing each predicate by "~ -", the operators which return "true" if the argument is either "true" or "unknown".  
We now consider the "&&" (and) and "||" (or) operators.  The expression  p||-p is true if p is either true or false, and is false if p is unknown.   The true complement of this expression, ~p&&~ -p, is true if and only if p is unknown.  Altogether, there are 8 possible subsets of t, u, and f which are true, and we use these two expressions as a normal form for expressions involving a predicate p, the complement operators, and the and/or operators.  Any such expression will simplify to one of these 8 cases:
Normal Form  t/u/f subset	Other Equivalent Expressions
False	 	p*~p,  -p*~ -p	
P	 {t} 	~ ~ p, - ~ p,  (odd # complements ~ or -) ~p	
-p 	 {f}	-p&&~p, (even # of complements ~ or -) –p	
~p	 {u,f}	-p||~p, (even # of complements ~ or -) ~p	
~ -p	 {t,u}	p||~ -p, (odd # of complements ~ or -) -p	
p|| -p 	 {t,f}		
~p&& ~ -p	 {u}		
True	 {t,u,f}	p||~p, -p||~ -p 	
The lower bound for r{} can contain more objects than the upper bound, so some of these intervals are technically not rough sets.  For example, r{~p} represents the rough set [{r| r. ~p}, {r | r.p}].  However, we’ll continue to treat these reverse-intervals as a kind of "negative" rough set.  
The union, intersection, and difference of rough sets are constructed in the standard way by taking the union, intersection, and difference of the bounds.  That is, if r=[rL,rU] and s=[sL,sU],
r+s = [rL+ sL, rU+sU]  where + represents set union
r-s = [rL- sL, rU-sU]  where – represents set difference
r~s = [rL-sU, rU-sL].
The rough set that corresponds to a class expression involving && or || is also defined as follows:
	r{||} = r{}+ r{}
	r{&&} = r{}* r{} where * represents intersection.
Since exactly one of the functionals t(), u(), and f() will return "true" for a given "this" and a given , we have
r{ || ~} = [r.t( || ~)], r.(t( || ~) || u( || ~))] = r{true} = [r,r]
r{ && ~} = r{t() && (u() || f())} = r{false} = [Ø, Ø]
r{ && } = r{}* r{}
r{ || } = r{}+ r{}

	The functionals t(), u(), and f() are 2-valued, and it can be easily checked that the algebra with the operators &&, ||, and ~ satisfies the laws of Boolean algebra.  For instance,

r{~ ~} = r{}
r{~( && )} = r{~ || ~}
r{~( || )} = r{~ && ~}
r{ && } = r{~ (~)}
= r{}~ (r{}* r{~}) 
= r{}r{~} r{~})
		= r{}r{~} r{}r{~}  
= r{}  r{}

It can easily be checked that the operators {+,*,~} satisfy the laws of Boolean algebra. Notice, however, that the complement operator "-" does not satisfy the laws x || -x=true when x=unknown, so {+,*,-} does not form a Boolean algebra.  However, we have  ~x||- ~x=true, -x || - -x=true, - - ~x = ~x and - - -x = -x.  
The count selection predicates >k(reln, where), <k(reln, where), >=k(reln, where), and <=k(reln, where) and their complements return only "true" or "false" values, but they are still considered to be  3-valued predicates since the complement "-" is unrelated to the original predicate, so that it is possible to be neither "false" nor "true", or to be both "false" and "true".  Such conditions are considered to be the same as having an "unknown" value.   For instance, - >3(r, pred) represents the predicate which states that it is provably false that more than 3 r's satisfy pred.  This is that same as saying that >=|r|-3(r,-pred), which means that at least |r|-3 r's will return a "false" value for "pred", making it impossible for there to be more than 3 r's returning "true"  or "unknown".   The "true complement" operator "~", on the other hand, means "possibly not".  For instance, the expression ~>3( r, pred) is true if there are possibly not greater than 3 r's returning "true" values for "pred".  This is logically equivalent to saying <=3(r, pred), meaning that there are at most 3 r's for which pred returns "true".
By looking at these examples, we see that the complement signs can be moved inside of the selection condition of the cnt predicates when simplifying these expressions.

4. Summary
The “intelligence” of this system comes from the ability to simplify logical definitions of classes and queries, and to compute their IS-A containments, if any.  As well as looking at the logical containments, the user can also compute the extents of class differences, thus easily finding examples and counterexamples.  The major problem for agent-based technologies at the present time is that various groups of users develop their own models and terminologies.  Class algebra can be used to clearly map between the groups’ models.  Class definitions, queries, and binary relations can be compared both logically and by looking at actual instances that might cause inconsistencies.

References
[1] Helena Rasiowa and Nguyen Cat Ho, "LT-Fuzzy Logic", in Fuzzy Logic for the Management of Uncertainty, (edited by Lotfi Zadeh), New York: Wiley, 1992.

[2] D. Buehrer and Chee-Hwa Lee, "Class Algebra for Ontology Reasoning", Proc. of TOOLS Asia 99 (Technology of Object-Oriented Languages and Systems, 31st  International Conference), IEEE Press, Nanjing, China, Sept. 22-25, pp.2-13, 1999.

[3] D.J. Buehrer, "An Object-Oriented Class Algebra", in Proceedings of ICCI '95: 7th International Conference on Computing and Information, Peterborough, Ontario, Canada, July 5-8, 1995, pp.669-685.

[4] D.J. Buehrer, Y.H. Liu, T.Y. Hong, J.J. Jou, "Class Algebra as a Description Logic", AAAI Lecture Notes, Proceedings of the 1996 Description Logic Workshop, Nov. 2-4, Boston, pp.92-96, 1996.

[5] D.J. Buehrer, "From Interval Probability Theory to Computable Fuzzy First-Order
Logic and Beyond," Proceedings of IEEE World Congress on Computational Intelligence, June 26-July 2, 1994, Orlando, Florida, pp.1428-1433.

[6] Wen-Long Gau, D.J. Buehrer, "Vague Sets", IEEE Transactions on Systems, Man, and Cybernetics, Vol. 23, No. 2, pp.610-614, 1993.

[7] Anthony J. Bonner, "Intuitionistic Deductive Databases and the Polynomial Time Hierarchy," The Journal of Logic Programming (1997) pp.1-47.

[8] Krassimir Atanassov and George Gargov, "Elements of intuitionistic fuzzy logic, Part I", Fuzzy Sets and Systems, Vol. 95 (1998) pp. 39-52.

[9] Georg Gottlob, Nicola Leone and Francesco Scarcello, “The Complexity of Acyclic Conjunctive Queries,” Journal of the ACM, Vol. 48, Issue 3 (May 2001), pp.431-498.

Figure 1
Abia Cadabia Interface for Queries

Figure 2
Abia Cadabia Interface for Editing Binary Relations