This file is raw output from pdftotext and may not be ideal for distribution. If you are a maintainer for Hackipedia, please sit down when you have time and clean this text version up. Source PDF: /mnt/fw-js/docs/languages, computer/F-Logic/F-Logic - A Higher-Order Language For Reasoning About Objects, Inheritance, And Scheme.pdf Like all conversions the text below should be fully readable as UTF-8 unicode text. --------------------------------------------------------------- F-Logic: A Higher-Order Language for Reasoning about Objects, Inheritance, and Scheme Michael Kifer* Georg Lausen Department of Computer Science Fakult &t fiir Mat hematik und Informatik SUNY at Stony Brook, Stony Brook, Universitgt Mannheim, D-6800 Mannheim, NY 11794, U.S.A. West Germany Abstract languages. Since logic programming can be used as a full-fledged computational formalism as well as a We propose a database logic which accounts in a clean database specification language, proponents of the de- declarative fashion for most of the “object-oriented” ductive approach have also argued that it is capable of features such as object identity, complex objects, in- overcoming the aforesaid mismatch problem. However, heritance, methods, etc. Furthermore, database schema in their present form both approaches have shortcom- is part of the object language, which allows the user to ings. The main problem with the object-oriented ap- browse schema and data using the same declarative for- proach is the lack of formal semantics which is tradition- malism. The proposed logic has a formal semantics and ally considered to be very important in databases. On a sound and complete resolution-based proof procedure, the other hand, deductive databases normally use flat which makes it also computationally attractive. data model and do not support object identity and data abstraction. It therefore can be expected that combin- ing the two paradigms will yield significant benefits. 1 Introduction A number of attempts to combine the two approaches [1,2,5,6,7,13,20,23,22,27,37] have been reported in the Object-oriented approach to databases has generated literature, but, in our opinion, none of them succeeds considerable interest in the community in the past few in meeting all of the above goals. These approaches years. Although the very term “object-oriented” is either do not support object identity, or restrict the loosely defined, a number of concepts have been identi- kinds of complex objects and queries one can use, or do fied as the most salient features of that approach. Ac- not support inheritance, limit deduction, etc. cording to [4,39,9,43] and a number of other surveys, In this paper we propose a formalism, called Frame these concepts are: complex objects, object identity, F-logic), which is a full-fledged logic Logic (abbr. methods, and inheritance. achieving a21 of the goals listed above and, in addi- One of the reasons for the interest in object-oriented tion, is suitable for defining and manipulating database database languages is that they show promise in over- schema. Our work has also implications for the frame- coming the, so called, impedance mismatch [28,9] be- based languages in AI [16,33], which are essentially tween programming and database languages. Mean- scaled down versions of complex objects with identity, while, a different, de&dive, approach has gained enor- inheritance, and deduction. It is this connection that mous popularity both in databases and programming the name “F-logic” was derived from. *Supported in part by the NSF grant DC%8603676; Work To reason about inheritance and schema we need ca- partially performed while visiting the University of Mannheim, pabilities of higher-order logics. However, these are usu- W. Germany ally much too powerful to be useful for our purposes. A number of researchers have suggested that the “useful” parts of higher-order logics can be given a first-order se- mantics by encoding them in predicate calculus [18,32]. However, this provides only an indirect semantics and Permiuion to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM is not true to the spirit of object-oriented programming copyright notice and the title of the publication and its date appear, and notice is and frame-based languages in AI. In contrast, we pro- given that copying is by pemksion of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. pose a logic which has an appearance of a higher-order 0 1989 ACM 0-89791-317-5/89/ooO5/0134 $1.50 logic, but, unlike it, is tractable and has a natural di- 134 rect first-order semantics. More precisely, according to Additionally, this clause states that bob works in the the classification of [12], F-logic has a higher-order syn- department csl, the department name is “CS” and tax and a first-order semantics. A sound and complete the manager is an employee denoted by the constant proof procedure for F-logic will be described in the full Phil. Clauses (2) through (4) present similar infor- paper. mation about mazy, john, and sally. Note that the This work is an extension of [20], which in turn was f Tiends attribute in mary’s record is set-valued, which based on Maier’s O-logic [27]. In [20] a distinction be- is syntactically expressed by means of the set construc- tween objects, classes, and relationships is maintained, tor { }. Our syntax is that from [27,20] with some em- which is the main reason why inheritance, methods, and bellishments from [l3]. schema cannot be reasoned about in these formalisms. Clauses (5), (6), and (7) provide general information This paper is organized as follows. In Section 2 we about classes faculty, students, and empl, such as that present the syntax and semantics of F-logic, and Sec- faculty are normally supervised by faculty and are mid- tion 3 presents Skolem and Herbrand theorems; in Sec- dle aged, students are normally young, etc. Clause (8) tion 4 we illustrate the higher-order capabilities of F- is a rule stating that employee’s supervisor is the man- logic. ager of the department the employee works in. Clause (9) is a rule defining a method: for each per- son, X, the method children is a function which for a 2 Syntax and Semantics of F- given argument, Y, returns a set of persons containing logic all the children common to X and Y. Notice that the term children(Y) appears in the same clause (9) in two In this section we describe the proposed logic by means different roles: in the head of (9) it is in the “attribute” of an example, followed by a formal account of the syn- position, where it denotes the aforesaid method, and it tax and semantics. is in the “object” position in the body of (9), where it denotes the id of the object whose content is the set 2.1 F-logic by Example of children of Y. Thus, any ground instance of this term, say chiIdren(mury), has two different roles: it In developing F-logic we were motivated by the desire denotes the object representing all mary’s children and to capture in a logically clean way a number of scenar- also a function which, for each person, returns a (possi- ios whose most salient common features are depicted bly empty) set of all children mary has with that per- by way of an example in Figures 1 and 2. Figure 1 son. Thus, in F-logic, the same syntactic term may shows part of the IS-A hierarchy. All classes and indi- denote different things, depending on the context it ap- vidual objects are taken from the same domain and are pears in. This feature allows one to pose meta-queries organized in a lattice. It asserts that a faculty and an about the objects, such as “retrieve a set of all objects assistant are employees, student and empl are persons, which represent the labels defined for a certain object”. “Mary” and “CS” are strings, mary is a f acuity, while Two applications of method children are demon- sally is a student. Notice that the lattice is ordered strated by queries (10) and (11). Query (10) asks for with respect to the “definedness” ordering of denota- the father of mary’s child sally, and (11) requests all tional semantics, or, equivalently, with respect to the children mary has with Phil. Query (12) is requesting relative “knowledge content” [17]. For instance, a state- information about all middle aged employees working ment assistant : john (john is an assistant) is more in- for the “CS” departments. Particularly, for each such formative than empl : john because every assistant is employee, it is requesting the supervisor, age, and the an employee, but not vice versa. Therefore, assistant department. The expected answer to this query is has more knowledge content and is located above empl. (13) bob[euperuisor + T, age ---) 40, works -+ CLQ] In general, a class is always located below each of its instances. Furthermore, note that classes are reified by (14) mary[superuisor 3 f acuity, age -t 30, being placed in the same domain with their instances. works + ~821 Thus the same object (e.g. empl) can be viewed as To see that bob is an answer, first observe that, by (l), an instance of its superclass (person) and, at the same bob is working for the “C‘S” department and that bob time, as a class of all objects located above it in the has age 40, which is a value belonging to class midaged lattice. (see Figure 1). The value for SUpeTUiSOT is partly in- Figure 2 presents facts about employees, students, ferred from the rule (8) and partly inherited from the etc. The first clause says that object bob is a faculty general description (5) of class f acuity. Indeed, the rule whose name is “Bob” (notice: bob is an id of the ob- suggests that bob’s supervisor should be Phil, while on ject, while “Bob” is a string representing bob’s name). the other hand, being a faculty, bob’s supervisor has 135 ehi&n(john) I Figure 1: Part of the IS-A hierarchy Facts: (1) facUZQ/ : bob[name --) “Bob”, age + 40, works + dept : csl [dname + “C’S”, mngr + empl : Phil] ] (2) f acuZty : mary[name + “Mary”, age + 30, f Tiends + {bob, sally), woTk8 + dept : caz[dname + ‘C’S”] ] (3) assistant : john[name + “John”, works t csl[dname ---)“CS”]] (4) student : saZZy[age midaged] + General Class Information: (5) faalty[ aupeTvisor -+ f acuZty, age -P midaged] (6) student[uge + young] (7) empZ[eupervis~ + empl] Rules: (8) E[SU~~ZTV~SOT -+ M] ti empZ : E[wmks + dept : D[mngr + empl : M]] (9) X[chiZdren(Y) -+ {Z}] *person : Y [chiZdTen_obj-+ chiZdren(Y)[membere -+ {pereon : Z}] 1, person : X[chiZdTen-obj ---)chiZdren(X)[members --) (person : Z}] ] Queries: (10) mary[chiZd?en(Y) --) {sally}]? (11) mary[chiZdTen(phiZ) -+ {Z}]? (12) empl: X[ supervieor + Y, age -+ midaged : 2, works + D[dname + “CS”] ]? Figure 2: A Sample Database 136 to be in the class faculty. However, looking at Fig- thentic, yet inexpensive, way. ure 1, we observe that phi1 is not an instance of faculty. The semantics of F-logic then suggests that the value of 2.2 Syntax SU~TV~SOT for bobshould be Zub(phi1,faculty) which is T (see Figure 1). That is, the information about Phil’s The alphabet of F-logic consists of (1) a set 0 of basic supervisor is inconsistent. objects, (2) a set of object constructors 7, (3) an infinite Clause (14) is retrieved because mar y is in the yuppie set of variabZes, V, and (4) usual logic connectives and age, and thus is also a middle aged person. On the quantifiers V, A, V, 3, 7, e, etc. other hand, the object denoted by constant john is The “objects” in F-logic are either complex objects not retrieved because john, being a student, inherits in the usual sense, or classes of objects. Unlike other young from (6), and according to Figure 1, young is approaches which treat classes and instances as inher- not an instance of midaged. However, if the restric- ently different entities, we do not emphasize the distinc- tion midaged : Z in query (10) were dropped, then the tion. For instance the object student can be viewed following clause will be retrieved as well: as representing the class of students (each individual student being its instance) and at the same time as (15) john[eupervisor -+ phil, age + young, an instance of its superclass represented by the object works + CLQ] person. Thus, in F-logic classes have the same meaning The supervisor of john is inferred by rule (8), since as in frame-based formalisms (e.g. [16,33]) in the sense john is working in csi, and, due to clause (l), depart- that a class is viewed as an instance (rather than a sub- ment csi is managed by Phil. An interesting point here set) of a superclass. This feature is largely responsible is that, unlike bob, john is not a f acuity and therefore for the fact that inheritance is naturally built into the is not subject to the restriction imposed by clause (5) semantics of F-logic, contrasting it to algorithmically that his supervisor must be a faculty. Therefore, no defined inheritance in other approaches. contradiction with john’s supervisor being phi1 arises! Basic objects (elements of 0) are the constants of F- One additional important observation is that dis- logic. Object constructors (elements of 7) are logically agreements in attribute values need not always result function symbols over 0 of arity >_ 1; they are used to in inconsistency as in the bob’scase. For instance, sally construct new objects. Although members of 0 can be is midaged according to (4), but, being a student, she viewed as 0-ary object constructors, it is convenient to inherits young from (6). In F-logic this logically en- consider them separately, and we assume that 0 and 3 tails saZZy[uge Zub( + young, midaged)], which is yuppie are disjoint. An id-term is a term composed of function according to Figure 1. symbols (i.e. object constructors), constants (i.e. basic The example of Figures 1 and 2 alludes to the point objects), and variables in the usual way. The set of all that in F-logic we are dealing with higher-order con- ground (i.e. variable-free) id-terms is denoted by O*. In cepts. For instance, in Figure 2, attribute friends is the following we will show that 0’ essentially plays the essentially a set-valued function which for each person role of Herbrand universe of F-logic. Conceptually id- returns a set of persons. Similarly, the user can think terms should be viewed as objects themselves or as ob- of objects of the lattice displayed in Figure 1 as sets ject abstractions which are commonly referred to as ob- ordered by subset relation, and use higher-order intu- ject identity [19]. Objects represented by id-terms other itions to develop programs and models. However, the than constants (non-basic objects) are best perceived as underlying semantics formally remains first-order (see being constructed from simpler objects. For instance, [12] for details), w h ic h a11 ows us to overcome the diffi- the object university(state) can be taken as a class rep- culties normally associated with truly higher-order the- resenting universities, while the object university(nys) ories. is the class of universities in New York State (assuming The first-order behaviour with respect to sets is nys is an instance of class state). achieved by introducing typing so that single-valued In O-logic [27,20], which is a predecessor of F-logic, and set-valued functions do not mix. Furthermore, for- there was a distinction between objects and Za5eZsand mally, F-logic has only flat sets, but we can model arbi- the latter were viewed exclusively as binary relations trarily deeply nested sets in a very natural way. F-logic among objects. This distinction made it difficult to rea- shares this behaviour with respect to sets with other son about entities and relationships in a uniform frame- two related formalisms [13,20] and more discussion on work; it can be traced to the Entity-Relationship model that can be found in [20]. The first-order behaviour where entities (objects) and relationships (labels) con- with respect to the class/subclass hierarchy is achieved stitute two disjoint categories. by defining a lattice structure on the set of objects and In F-logic, every object can be viewed as an entity classes which allows us to model sets in quite an au- or a relationship depending on the situation (namely, 137 on its syntactic position in a formula). In its role as Flab,, are functional. The order of labels in an a label, each object has a type: a label can be either F-term is immaterial. Finally, in the above, Ti and single-valued (sometimes also called functional) or set- Sri,,, denote F-terms. valued. Accordingly, we partition 0’ into a pair of It is worth noting here that, since we chose a sort- disjoint sets t# (for objects typed as functional labels) less setting for F-logic, typing of nonground labels is and C, (for objects typed as set-valued labels). virtually impossible. Consequently, say, t = a[X -+ b] We require the aforesaid partition to be congruent: is considered to be a syntactically correct term, even ifti,si, . . . . t,, 8, E U*, where for each i, ti and 4 are though X may be bound to ground id-terms typed as in the same partition, and f E 3 is an n-ary object functional as well as set-valued labels. However, the constructor, then f(ti,. . . , t,) and f(zi, . . . , an) belong semantics is set up in such a way that, since the syn- to the same element of the partition (C, or C,). tax of t calls for a functional label, t will be always This restriction is needed to be able to specify types false whenever X is universally quantified. Further- on CY* effectively and check them efficiently. Indeed, more, even the constructs such as a[Zab+ c, lab -+ {d}] under the congruence assumption, assigning types to are syntactically correct F-terms, despite the fact that elements of UC involves the following: (1) assigning a lab must be a functional label due to one part of the type to each element of 0; (2) specifying the type of term, and a set-valued label due to the other. How- f(Cl, ***, Ln) for every n-ary function symbol f E 3 ever, according to the F-logic semantics, this term is and each n-tuple < Cl, . . . , L, >, where each Lj is either L# or L,. Since the cardinality of 0 and 3 is unaatiafiable. finite in practical cases, this procedure is effective. To Intuitively, the F-term (2) above is a statement about check the type of a term t E U*, one needs to “evaluate” an object, Q, asserting that it is an instance of the class this term by substituting types for subterms, starting P and haz properties specified by the labels. Thus, with constants. This procedure is linear in the size of when no labels are specified we can omit the brackets, the term. Furthermore, we suspect that, in practice, thereby reducing a complex F-term, P : Q[ 1, to the one needs to assign only a single type to the range simple F-term P : Q. of each function symbol (regardless of the argument To account for the higher-order features of frame- types), which then makes type definition linear in the based and object-oriented formalisms without incurring sizes of 0 and 3, and type checking can be done in con- the overhead of the higher-order predicate calculus, we stant time by checking the range type of the outermost reify classes and model class membership by means of a function symbol. lattice ordering instead of the true set-theoretic mem- The language of F-logic consists of a set of formulae bership. Formally, we assume that the elements of 0’ constructed out of the alphabet symbols. Formulae are are organized in a lattice1 by means of the ordering built from atomic formulae by means of the usual con- 40 . As usual, -& stands for 40 or =. We distin- nectives 7, V, and A, and quantifiers 3 and V. Atomic guish in 0’ the maximal element, T, and the minimal formulae are, so called, F-terms (F-logic terms). Later element, 1. The maximal element, T, can be viewed as we will see that the id-terms introduced earlier can be a “meaningless” object which represents a class with no viewed as a special case of F-terms. instances; I can be perceived as the object representing For convenience, we will use names starting with the biggest class (or as the “unknown” object). lower-case letters to denote ground terms, and names The lattice on U* is a static part of the language2, starting with capital letters to denote possibly non- and can be viewed as part of schema specifica- ground terms. An F-term (cf. [27,20]) is tion: the lattice represents the transitive closure of the “subclass-of” and the “instance-of” relationships (1) a simple F-term, P : Q, where P and Q are id- among classes, so that p 40 q (e.g. person 40 student terms, or or student 40 john) means that q is a (possibly indi- complez F-term, P : Q [Flabl + Tl, . . . , rect) subclass or instance of p. As mentioned earlier, (2) a we do not distinguish between individual objects and Flab,,, * Tin, Slab1 --) {&,I, . . . , %,I), . . . , Slab1-+ {&,I, . . . , Sk,,r}]. Here P, Q are id-terms; classes: any object, d, is treated as a class whose exten- Flabi and Slabj are also id-terms, but we chose to sion contains all objects/classes found above d in the name them differently to indicate that their syn- lattice. Therefore, any element p E U* may appear in tactic position within the F-term emphasizes their an F-term in the “instance position”, q : p[...], and in role as labels. Furthermore, the appearance of the 1 When objects are considered in their role as labels, the lattice set construct, { }, indicates that the respective id- structure on labels is ignored. terms SlabI, .... Slab, are supposed to be typed as ll’his assumption is needed for F-logic unification to be set-valued labels; the rest of the labels, FlabI, .... decidable. 138 the “class position”, p : T [...I. This gives F-logic a “feel” 2.3 Semantics of a higher-order language, although its semantics is es- sentially first-order [12]. Accordingly, we will use the Before presenting the semantics, we will need to intro- terms “instance” and “class” to refer to the same ob- duce an ordering on the powerdomain of a lattice. This ject, p, depending on whether we want to emphasize ordering was also used in [5] and is sometimes called p in its role as a class or as an instance in its respec- Hoare’s ordering [8]. Given a lattice U with the order- tive superclass. Part of a sample lattice structure on ing 5~ and maximal and minimal elements TV and Iv, 0’ is depicted in Figure 1. We impose the following the preorder & on the powerset 2’ is defined as fol- monotonicity restriction on the lattice U*: lows: for any pair of sets X, Y E U, we write X & Y iff for every element z E X there is y E Y such that X3UY. if tl 30 al, .. .. t, 50 8, then The preorder & on 2IJ is not an order, since it fbl ,-&a) Ib f(81r .a-,4; is cyclic. For instance {u} & {a, Iv} !& {u} and This simply means that object constructors are {Tu} Eu U Cu {Tu}. II owever, 2” can be considered a lattice modulo the equivalence relation MU, where monotonic functions on the lattice: for instance, X R:LI Y if and only if X &I Y and Y & X. The if pereon+ john, i.e., John is a person, then maximal and minimal elements in this lattice are the car(person) 40 car(john) meaning that John’s cars be- equivalence classes of { } (the empty set) and {Tu}, long to the class of cars owned by persons. respectively. To simplify the language, we will often Monotonicity is necessary for the resolution proce- talk about the lattice structure on the powerset of U dure to be complete, which will be discussed in the disregarding the aforesaid subtlety. full paper. Apart from that, this ensures that the lat- Similarly, given a pair of lattices, U and V, we tice structure on U* can be given effectively as part can define a lattice structure on the set of mappings of schema specifications and that the “instance-of” re- U + V, denoted Mup(U, V), as follows: f +ap(U,V) g lationship can be verified efficiently. Indeed, in prac- if for every u E U, f(u) 5~ g(u). Two kinds of lat- tical cases, 0 and 3 are finite and 40 can be first tice mappings, monotonic (denoted Mon(U, V)) and specified on 0. To complete the specification of the homomorphic3 (denoted Hom( U, V)) are of particular lattice order, one only needs to provide typing informa- importance. Clearly, Hom(U, V) C ikfon(U, V). tion for each of the finite number of object construc- Semantics of F-logic can now be defined as follows. tors by specifying the classes for the range and the Given a language of F-logic, its interpretation, I, is a arguments. For instance, con8 : edge x path-path tuple < U, go, gz, I#, J* >. Here U is a universe of all (meaning path 40 cons(edge,path)) is an example of objects which is required to have a lattice structure with such typing information. Additional typing for func- Iv and TV being the smallest and the largest elements, tion symbols can be automatically inferred using the respectively, and with the lattice ordering 5~; U is par- well known type inference techniques (e.g. see [lo]). titioned into a pair of subsets U# and U, to account for Verification of whether t 30 8 holds for a pair of ground the types of elements of 0’. It is useful to think of the id-terms t, 8 E U* can be done in a way resembling the elements of U* as the names of objects, while the ele- usual unification algorithm and will be discussed in the ments of U are best thought of as the object8 themselves full paper. in the possible world I. Every F-term is also an (atomic) F-formula. F- The homomorphism go : 0’ + U is interpreting ob- formulae are constructed from other (simpler) F- jects of U* by elements of U, so that g,,(t#) c U# formulae by means of logical connectives and quanti- and gO(L,) c U,. The mapping gP : 3+Mon(Uk, U) fiers. interprets each k-ary object constructor, f E 3, by a To simplify the notation we assume the follow- monotonic mapping Uk + U. Additionally, go and gr ing convention: if a single-valued label, Lab, in an are related as follows: if t = f(.q, .. ..a.) E U* then F-term is omitted then the intention is Lab-t I : So(t) = 97(f)(90(81),...rSo(8n)). I; similarly, if a set-valued label, Lab’ is omit- The reader may notice that constants and function ted then we assume Lab’-+ { }. Furthermore, if symbols are interpreted essentially the same way as in a class specification is omitted then I is assumed. predicate calculus. The only difference is that the set of Thus, for instance, john[name --tat&g : “john”] ground terms, U’, and the domain, U, now have lattice and I : john[name + string : “john”, pay+ -L : structures which must be accounted for. I, children + { }] are considered to be the same term. In their role as labels, objects are interpreted This convention allows us to view id-terms as a special case of F-terms by identifying P and I : P[ 1. 3i.e. the ones preserving lub and glb. 139 by associating appropriate mappings to each ele- says that for an F-term, T, to be satisfied by a possi- ment of U using functions J# and 3,. More specif- ble world, I, w.r.t. Y, that world must have at least ically, J# : U# + Mon( U, U) associates a mono- as much information about the object denoted by u(T) tonic mapping U -+ U with each element of U# and as the amount of information asserted by T. Finally, 3* : U, -+ Mon(U, 2”) associates monotonic mappings the third condition in (2) and (3) simply says that the U + 2’ with elements of U,. Notice that J# and J+ properties of Q asserted by T (i.e., Ti, Sj, etc.) must ignore the ordering +J induced on Us and U, by U. also be true in I w.r.t. V. Thus, set-valued labels are interpreted by monotonic Notice that according to these defi- set-valued functions, while functional labels become nitions, MrlY(T) = MI,“(~) = MIIY(d) = true and monotonic single-valued functions. Notice that these MI,~(~ : d) = MI,,(d : T) = true for every d E 0’. functions are associated with the elements of U, not Similarly, if I -+J d 40 T then MI,,(d : I) = Ml,,(T : U’, because, as noted earlier, 0’ is, strictly speaking, d) = false. only a set of object names; these are interpreted by the Meaning of the formulae 4 V 4, 4 A 4, and -$ is de- “real” objects in a possible world, I, and it should be fined in the standard way: MI,,(# V ~6) = true (resp., the objects, not their names, who can assume roles (of Mr,Jd A $1, r-p. MI,~(%)) iff MzJd) = tTw V labels) 4. MI,,,($) = true (resp. MI,,(+) = true A MI,,($) = A variuble assignment, V, is a mapping from vari- twe, resp. MllY(+) # true). The meaning of quan- ables, V, to the domain U. We extend it to id-terms tifiers is also quite standard: MI,“($) = true, where in the usual way: y(d) = go(d) if d E 0 and, recur- $ = (VX)q5 (resp. II, = (3X)$) if for every (resp. some) sively, v( f (..., T, . ..)) = gF( f )( .. .. v(T), ...). To simplify p which agrees with u everywhere, except possibly on the notation, we will also extend variable assignments X, MI,,($) = true. to F-terms as follows: V( P : Q[. . .]) = V(Q). Clearly, for a closed formula, $, its meaning is inde- Let I be an interpretation and Y a variable assign- pendent of a variable assignment, and we can simply ment. The meaning in I under Y of an F-term T, write MI($). A n interpretation I is a model of II, if denoted MI,“(T), is a statement about the existence M&b) = t+ue. (true) or nonexistence (false) in I of an object v(T) As an aside, other orderings on powersets over lattices with the properties specified in v(T). Consider an F- are possible. For instance, according to the Smyth ‘a or- term, T = P : Q[. . . , Flabi --tTi, .... Slabi -+ {Sl, .... dering [8], X CZu Smyth Y iff for every element y E Y S,}, . . .], where P, Q are id-terms in their role as ob- there exists z E X such that 2 5~ y. Presumably, we jects, Flab{, Slabj are id-terms in their role as func- could use this ordering instead of Hoare’s in our seman- tional and set-valued labels, respectively, and T{, Sk tics. This would allow us to enforce typing constraints are F-terms. Then J%v m = true iff the following on elements of sets the same way as we do it for func- conditions hold: tional labels (see Section 4.2). However, switching to Smyth’s ordering would permit certain unnatural infer- (1) v(P) dcr y(Q); ences, such as: from a[lab + {b)] infer a[Zab-+ {b, c}] for Flabi (intended as a functional la- any c. Ideally, we would like to use the so called Egli- (2) for each id-term Milner’s order, which is Hoare’s and Smyth’s orderings 3, combined. We could then benefit both from the right Y(FZabi) E U#, semantics of sets achieved through Hoare’s ordering, : v(Z) -+I 3#( u(FM))(y(Q)), and and from type enforcement which Smyth’s order has - MI,,&) = tT’UE; to offer. Unfortunately, in order to be able to group el- (3) for each id-term Slabj (intended as a set-valued la- ements into sets under Egli-Milner’s ordering, we would bel), have to change F-logic syntax by introducing variables u(Slabj) E U*, over sets. Particularly, instead of being first-order, as in 4 v (S)I J~~~J~(sm)~ Eu J*( v(Slabj) )(dQ)h and O-logic [20], set grouping will become second-order, as - MI,,,(Sk) = true for k = 1, . .. . m. in LDL [6], which makes handling of sets an expensive proposition. Here (1) simply says that the object V(Q) must be in the class V(P) in the possible world I. In (2) and (3), the first condition says that id-terms representing the la- 2.4 Databases and Queries bels must be appropriately typed; the second condition A database is a set of formulae. We distinguish be- tween the extensional part of a database (the set of ‘There is also a tecbnicd reason for that, which becomes ap- parent when one tries to define formula satisfaction w.r.t. a vari- F-terms) and its intentional part (the set of formulae able assignment. “more complex” than F-terms). If S is a set of formulae 140 and 4 a formula, we write S + 4 (4 is logically implied Because &U is, strictly speaking, only a preorder (see or entailed by S) iff 4 is true in every model of S. Section 2.3), 3 is too a preorder, but not an order. Given a language L with a set of variables V and a However, as &, it is an order modulo the equivalence set of basic objects 0, a substitution is a mapping u : relation %, whereI~~iffI~~andi~1. V -+ {id-terms of L} which is identity everywhere out- Having defined 5, we can now talk about minimal side some finite set &m(u) E V, called the domain of u. models: I is minimal if there is no J s.t. J 3 I but It is extended to id-terms by letting u to commute with not I 5 J. The reader can notice that our definitions object constructors and, recursively, to F-terms so that of minimality and order are in the spirit of the corre- Q(P : Q[ . . . . FZab+T, . . . . Slab-+{ . . . . S, . ..}I = sponding classic notions for Herbrand interpretations, Q(P) : 4QK.. , a(FZab)+u(T), . . ..u(SZab)-. where “smaller” means “less defined”. 1. ..) u(S), . . .)]. Finally, substitutions are extended In classic logic programming [26], Herbrand interpre- to F-formulae by letting them commute with logical tations are defined as subsets of the Herbrand base, connectives. A substitution is ground if u(X) E U* for where the latter is just the set of all ground atomic each X E dam(u). Given a substitution u and a for- formulae. In F-logic, the analogue of Herbrand base is mula 4, u(b) is called an inrtance of 4. It is a ground the set of all ground F-terms with the class information instance if it contains no variables. stripped off 5. The class information is superfluous here A query is a statement of the form Q?, where Q is an since the validity of the “‘instance-of’ statement of the F-term. The set of un8wer8 to Q? w.r.t. a database D is form p : q, where p, q E U*, is a consequence of the the smallest set of ground F-terms which is (1) closed lattice structure (which is part of the language), and is under + and (2) contains all instances of Q logically therefore independent of the program. Let us call such entailed (b) by D. F-terms base. As in classic logic, in F-logic every subset of the Her- brand base can be associated with a unique Herbrand 3 Skolemization and the Her- interpretation. brand Theorem Proposition 1 For any subeet S of Herbrund base there is a Herbrand interpretation H such that: Skolemization procedure in F-logic is not any different a H sutiafies every F-term in S; from that of predicate calculus. As in predicate calcu- lus, we have the following result. l H is u minimal interpretation w.r.t. the preorder 4. -t Theorem 1 (cf. the Skolem Theorem) Let D be a Furthermore, such interpret&ion H ia unique module set of F-formulue and 4 an F-formulu. Let D’, 4’ denote dome akolemi%otion of D and 4, respectively. the equivalence relation M defined earlier. Then D U {T$) is unsati8fiable (ho8 no model) ifl 80 However, this relationship between sets of bare F-terms is D’ u {+‘}. and the corresponding Herbrand interpretations is less obvious than in the classic case. For instance, the Given a language L of F-logic, its Herbrand universe is set S = {d[l ab + a, lab’ + Cc}], d[Zab-, b, lab’ + {e}] } 0’. A Herbrund interpretction, H, is an interpretation corresponds to the interpretation in which lab maps d whose domain is U’ together with the lattice ordering into Zub(a,b) and lab’ maps it into the set {c, e}. The 40 originally supplied with 0’ (in L). Herbrand in- rest of the labels map everything to I or { }, depending terpretations interpret objects and object constructors on the type. in the usual way: for d E 0 and f E 3, go(d) = d and . . . . tk) = f(tl, . . . . tk). Theorem 2 (cf. the Herbrand Theorem) A finite 9F(fPl> We can compare interpretations (Herbrand, in par- aet of form&e, S, is incondistent i# 80 i8 dome finite ticular) as follows: For&a pair of interpretations I = subset of its ground instances. (u,go,gF,3#,3+) and I = (u,go,gF,&,j+) differ- Herbrand Theorem is a basis for the resolution based ing only in the way they interpret objects as la- semi-decision procedure in predicate calculus [ll]. In bels, we write I 5 f iff for every object d E 0’ the full paper we will show that, extending the result typed as a functional label and every set-valued la- of [20], a sound and complete resolution-based proof bel, e E a’, s#(go)(d) ~M=~~(u,u) &(g,)(d) and procedure can be defined for F-logic. This, in turn, 3*(g0)(e) ~M~~(u,P) Ah)(e). The ordering on lat- provides a firm basis for the theory of logic program- tice mappings was introduced at the beginning of Sec- ming. Particularly, model-theoretic semantics of logic tion 2.3. To spell it out for this particular case, it means 6Recall that according to Section 2.2, a term without the class that for ~JI u E u, 3#(go)(d)(u) 5~ &(g,)(d)(u) ad information, e.g. d[lab-+c], is an abbreviation of the term I : fr(90)(e)(u) Eu Lt(90)(e)(u). d[lob4 I : c]. 141 programs (e.g. perfect model semantics [36]) can be ex- i.e. v is an instance of class p. Then tended to F-logic. This will be discussed in a companion paper. D b v[Lab+Q, Lab’-+(R)]. Thus, whenever p 30 v, properties of p also hold for 4 Inheritance, Methods, and v. In other words, v inherits properties ofp. Theorem 3 justifies our intuitions about the example of Section 2.1. Higher-Order Queries For instance, since faculty30 mary (Figure l), mary inherits supervisor --+ fact&y from clause (5) of Figure n In this section we discuss some salient features of the proposed semantics and illustrate them by a number of Sally (clause (4)) p rovides a more sophisticated examples. example. Since student -& saZZy, saZZy inherits age --) young from clause (6) of Figure 2. However, since clause (4) states that sally is midaged, in ev- 4.1 Inherit ante ery interpretation in which both saZZy[age --) young] The notion of inheritance is fundamental in AI and and saZZy(age-+midaged] are true, necessarily it is object-oriented programming, and a number of re- the case that saZZy[age--+Zub(young, midaged)] (G searchers have worked on incorporating it into program- saZZy[age- yuppie]) is also true, i.e. clauses (4) ming languages. Cardelli [lo] considered inheritance and (6) logically entail saZZy[age + yuppie]. Indeed, in the framework of functional programming. He de- in every interpretation I =< U,g,, g7, J#,J, > scribed a type inference procedure which is sound with the label age, being interpreted as a monotonic respect to the denotational semantics of his system. In single-valued function J#(age), has to map g,(saZZy) contrast, we have devised a logic in which inheritance into something which is above both go(young) and is built into the semantics and the proof procedure (in go (midaged). Since go : 0 --) U is a lattice homo- the full paper) is sound and complete. morphism, we have Zub( g,, (young), g,(midaged) ) = Ait-Kaci and Nasr [3] incorporate inheritance into gO( Zub(young, midaged) ) = gO(yuppie). Since I logic programs by means of a unification algorithm. is an arbitrarily chosen interpretation, we derive Although intuitively appealing, this algorithm was not saZZy[age yuppie]. + Thus, although the inherited given any semantically sound justification. In addition, property age +young is still true, in fact, we have Maier [27] has pointed out that their algorithm may more: age + yuppie. This effect can be called mono- be correct for type inferencing, but not for querying tonic overwriting of inheritance. databases. Later, Smolka and Ait-Kaci [38] presented It is arguable whether monotonic overwriting suffices a semantics to the unification algorithm of [3] using for all the needs of real world modeling. It is not diffi- equational logic. However, it is not clear how to extend cult to think of a situations when, in the above example, this semantics to a full-fledged logic in such a way that one would want sally to be midaged, completely disre- the resolution procedure based on the proposed unifica- garding the inherited age young. Furthermore, in some tion algorithm will be sound and complete. Even if it is cases (recall the paragraph discussing bob’s supervisor possible, this still does not make this system applicable in Section 2.1) inheritance contradicts the other infor- to database querying. mation to such an extent that we have to declare local There is also ample literature on, so called, nonmono- inconsistency (cf. bob[supervisor ---)T]). Although in tonic inheritance (e.g. [40,41,15]), which is different some cases this indeed may be the intention, in other from the monotonic inheritance of F-logic (see later). situations it may be not, and one needs a formal ac- Furthermore, in these works inheritance is defined al- count for the latter case. Such complete overwriting of gorithmically and is not built into the semantics, which inheritance is a (rather simple) instance of nonmono- we consider to be inappropriate for a logic for object- tonic inheritance mentioned earlier, and it is desirable oriented programming. In contrast, F-logic inheritance to have it built into the logic the same way as its mono- is built into the semantics, as follows from the next the- tonic counterpart. However, this raises a host of diffi- cult problems and is an issue for future research. orem: Theorem 3 Let D be a database, T = p[Lab+ Q, 4.2 Browsing Database Schema Lab’4 {R}] be an F-term and D b T. (Since Q, R and Lab, Lab’ can be nonground F-terms and id-terms, As explained earlier, although F-logic formally has a respectiveZy, should be viewed as a universally quanti- T first-order semantics, it is capable of modeling certain fied F-term.) Supposev E 0’ is an id-term s.t. ~30 v, higher-order features such as sets, class/subclass hierar- 142 thy, and scheme quite naturally. The first two are mod- will cause every instance of person to inherit the do- eled by means of set-valued functions and the lattice main string for the label name. Now, if an F-term structure on CY, while schema can be reasoned about specifies a value for name, e.g. john[name + “John”], because labels (which correspond to attributes of the re- and this value is an instance of string, then everything lational model) are represented by id-terms which are goes well and, as explained in Section 4.1, “John” over- virtually indistinguishable from objects. writes string. However, if the specified value is incom- In this section we discuss the browsing capabilities of parable with string, e.g. john[name + 201, then, since F-logic. Some of the higher-order capabilities described Zub(20,string) = T, john[name ---)T] is derived. in this section were also discussed in [21] in the context In relational model, relation schema is usually fixed of deductive databases. However, the treatment in [21] (e.g., suppZieT(sno, sname)) so that the tuples in a re- is not as general and integrated as in the present paper. lation are defined over the schema attributes only. In Typically, queries in database systems are specified contrast, in object-oriented languages (F-logic in par- with respect to an existing scheme, which is assumed ticular), attribute set may vary from object to object. to be known to the user. The practice shows, however, In fact, the general class information (cf. clauses (5) that this assumption is unrealistic and some kind of to (7) in Figure 2) limits the schema “from below” by browsing of the database is necessary. This means that specifying what is generally true about the class, while the user has to apply intuitive or exploratory search relational model limits schemes “from above” by spec- through the structure of the scheme and the database ifying the only set of meaningful attributes for a rela- at the same time and even in the same query (cf. [34]). tion. We do not take a stand on whether the notion of Many user interfaces to commercial databases support schema in relational databases is a modeling necessity browsing to different extents. The purpose of the fol- or merely an implementational convenience. The fol- lowing examples is to demonstrate that F-logic pro- lowing example shows that, if desired, schema restric- vides a unifying framework both for data and schema tion in the relational sense can be imposed in F-logic: exploration. We again refer to the example of Sec- suppZier[X + T] +== suppZier[X + 11, tion 2.1. X # 87x0,X # sname The following pair of rules collects for each instance suppZier[X --) (T}] (= suppZier[X --) { }] of class faculty all labels which are “more defined” than person or (person} (including the inherited labels): The first clause states that every label other than sno and sname maps supplier to T; the second clause says definedlabels [labels + {L}] G= faculty : X[L + person : Z] that every set-valued label maps supplier to the top set. Now, every individual supplier s will inherit these defineddabeZs(X) [labels -+ {L}] e restrictions and therefore every label outside the sup faculty : X[L + Cperson : Z)] plier’s scheme will yield meaningless information re- For the example of Figures 1 and 2, we have: garding 8. def inedJabeZs(mary) = {f&ends, supervisor}. Re- placing person by I and adding Z # I in the bodies of the above rules yields the set of all labels which are 4.3 Met hods strictly more defined than 1. Methods are the means of incorporating data abstrac- Another example of browsing is retrieval of all ob- tion into object-oriented programming. Since they jects which mention, say, “CS” directly or indirectly embody the procedural aspect of the object-oriented (through other objects). This can be specified as fol- paradigm, many researchers believed that methods can- lows: not be cast into a declarative setting. For instance, fina!er( “CP) [content + {X}] e X[Y + “CS”] [24,25] propose a formal data model intended to sup- finu?er( “CS’) [content + {X}] e X[Y * { “CS”}] port a procedural object-oriented language. Similarly, finder(“CSn)[content --, {X}] * X[Y 3 21, in [7] methods written in a procedural language are in- fincZer( “CS”)[content ---)(Z}] tegrated into a declarative setting. finder(“CSn)[content --) {X}] * X[Y + {Z}], We believe that the infamous impedance mismatch finder( “CS”)[content --f {Z}] between programs and data should be overcome in a For our running example, the query fincZer(“CS”) declarative fashion, which requires methods to be de- [content + (X}] ? will return the set {csr, ~82, bob, fined declaratively. This is not to say that procedural mary, john}. languages are of no use. However, our contention is The inheritance mechanism discussed in the previous that the procedural component should be integrated in section can be also used to enforce the domains of la- a declarative framework in a clean way, e.g. the one bels. For instance, specifying person[name + string] alluded to at the end of this section. 143 In F-logic, declarative definitions of methods are pos- gramming. This means that the same method name can sible because nonground id-terms are allowed to appear be used to denote quite different procedures, depending in label positions in F-terms. One example to this ef- on the class where this name is used. Another instance fect was given in Figure 2. For another one, consider of overloading can be obtained by modifying the pre- the rule vious example to include the class company which is person : X[graduation-date(I) -‘Y] * incomparable to person. Since companies have a com- univ : I[aZumni ---){aZumn-ret : G[stud --) pletely different set of rules regulating their legal names, person : X, date -+ year : Y]}] the definition of legal-name for class company may For each person, the graduation-date method is a func- have little resemblance of the definition of this method tion from universities to years, and one can ask queries for classes person, female, and writer, yet syntacti- such as cally the name is the same. X[graduation-date(I) + 1987]? Note that, in F-logic, methods are essentially “la- john[graduation-date(I) --$Y]? bels with parameters” and therefore plain labels can be viewed as parameterless methods. This uniformity to find all persons who graduated from anywhere in is rather pleasing and corresponds to the situation in 1987, or to find dates and universities john graduated abstract data types. The technique described above al- from. lows one to define arbitrarily complex methods, since By modifying the browsing example of the previous the full power of logic programming is at our disposal. section, we can define a method which returns the set Alternatively, we could incorporate procedures written of all objects directly or indirectly referring to the ob- in a nonlogic language, such as C or SmallTalk, by con- ject passed to the method as an argument (the Stuff sidering nonground labels as “computed functions” and variable): adapting the ideas from [30,31]. finder[find(Stuf f) -b {X}] G= X[Y + Stuff] finder[find(Stuff)+{X}] += X[Y -{Stuff}] finder[find(Stuf f) -t {X}] += X[Y + 21, 5 Conclusions finder[find(Stuff)+(Z}] finder[find(Stuf f) --${X}] k= X[Y ---*{Z}], Unlike the relational approach to databases which was finder[find(Stuff)--,{Z}] initiated by Codd [14] and was based on firm theo- In object-oriented languages, the ability to inherit retical grounds, object-oriented databases were dom- methods and build them incrementally is responsible for inated by “grass-roots” activity where several imple- much of the success of this approach in human interfaces mentations have been done [44,42,29] without the ac- and graphics. The following example illustrates how companying theoretical progress. As a result, many re- these phenomena can be accounted for in F-logic. searchers had a feeling that the whole area of object- Suppose that person -& male, female, w+iter. We oriented databases is misguided, lacking direction and can define the method legal-name as follows. Normally, needing a spokesman, like Codd, who could “coerce the the legal name is the last name of a person. However, researchers in this area into using common set of terms maiden name of a married female as well as a pen-name and defining a common goal that they are hoping to of a writer is also considered to be a legal name. We achieve [35]“. can first define this method for each person: Our contention is that the problem lies much deeper. X[ZegaZ-names(Y) + {IV}] -+= year : Y, When Codd made his influential proposal, he relied on person : X[Zast-name(Y) + string : N] a large body of knowledge in Mathematical Logic con- and then refine it for females and writers: cerning predicate calculus. Essentially, he merely ap- X[ZegaZ-names(Y) + {IV}] += year : Y, plied (in different terms) what logicians had already female : X[maiden-name(Y) + string : N] known for several decades. Logical foundations for object-oriented databases that are parallel to those that X[ZegaZ-names(Y) -+ {IV}] += year : Y, underly the relational theory were lacking and, in our writer : X[pen-name(Y) + string : N] opinion, this was a major factor for the uneasy feeling. Thus, if in 1988 mary was a married female, a writer, In his pioneering work [27], Maier proposed a frame- and uses her husband’s last name, she will have three work for defining model-theoretic semantics for object- different legal names in that year. On the other hand, oriented logics. However, he encountered certain se- for a ioe who is a male and not a writer, this method mantic difficulties with his approach and subsequently will return only one legal name. abandoned this direction. As it turned out, the diffi- This example is also an instance of operator overload- culties were not fatal, and the theory was repaired and ing - another feature attributed to object-oriented pro- significantly extended in [13,20]. 144 In the present paper, we presented a novel logic which PI P. Buneman and A. Ohori. Using Powerdomains takes the C- and 0-logics of [13,20] into a new dimen- to Generalize Relational Databases. Theoretical sion: F-logic is capable of representing most of what is Computer Science, 1989. to appear. known as the object-oriented paradigm. We provided a formal semantics for that logic and showed that it em- PI H. Ait-Kaci C. Zaniolo, D. Beech, S. Cammarata, L. Kerschberg, and D. Maier. Object-Oriented bodies in a natural way the notions of complex object, Database and Knowledge Systems. Technical Re- object identity, inheritance, methods, and schema. Al- port DB-038-85, MCC, 1985. though not presented in this paper, we note that F-logic has a sound and complete resolution-based proof pro- PO1 L. Cardelli. A Semantics of Multiple Inheritance. cedure which makes it also computationally attractive In Int. Symp. on Semantics of data l$pes, LNCS and renders it a suitable basis for developing a theory 173, pages 51-67, June 1984. of object-oriented logic programming. This issue will be discussed in a companion paper. Pll C.L. Chang and R.C.T. Lee. Symbolic Logic and Acknowledgements: We have obviously benefited Mechanical Theorem Proving. Academic Press, 1973. from Dave Maier’s original paper on O-logic [27], as well as from his valuable suggestions. Discussions with PI W. Chen, M. Kifer, and D.S. Warren. HiLog: Dave Warren have been extremely helpful; in particu- A First-Order Semantics for Higher-Order Logic lar, Dave helped us understand the “orderness” of the Programming Constructs. In 2-nd Intl. Workshop semantics we have developed. We also thank James on Database Programming Languages, Morgan- Wu for finding several inaccuracies in the earlier draft Kaufmann, June 1989. of this paper. P31 W. Chen and D.S. Warren. C-logic for Complex Objects. In Proceedings of the ACM SIGACT- References SIGMOD-SIGART Symposium on Principles of databaseSystems, March 1989. to appear. PI S. Abiteboul and C. Beeri. On the Power of Languages for Manipulation of Complex Objects. 1141 E.F. Codd. A Relational Model For Large Shared 1987. manuscript. Data Banks. Communications of ACM, 13(6):377- 387, 1970. PI S. Abiteboul and S. Grumbach. COL: A Logic-Based Language for Complex Objects. In PI D.W. Etherington and R. Reiter. On Inheri- Workshop on Database Programming Languages, tance Hierarchies with Exceptions. In AAAI-89, pages 253-276, Roscoff, France, September 1987. pages 104-108, Washington, D.C., 1983. PI H. Ait-Kaci and R. Nasr. LOGIN: A Logic Pro- P61R. Fikes and T. Kehler. The Role of Frame-Based gramming Language With Built-in Inheritance. J. Representation in Reasoning. Commun. ACM, Logic Programming, 3:185-215, 1986. 28(9):904-920, 1985. PI F. Bancilhon. Object-Oriented Database Systems. P71 M.L. Ginsberg. Multivalued Logics. In M.L. Gins- In Proceedings of the ACM SIGACT-SIGMOD- berg, editor, Readings in Non-Monotonic Reason- SIGART Symposium on Principles of database ing, pages 251-255, Morgan-KauGnann, 1987. Systems, pages 152-162, 1988. PI P.J. Hayes. The Logic for Frames. In D. Metzing, PI F. Bancilhon and S.N. Khoshafian. A Calculus editor, Frame Conception and Text Understanding, of Complex Objects. In Proceeding8 of the ACM pages 46-61, Walter de Gruyter and Co., 1979. SIGACT-SIGMOD-SIGART Symposium on Prin- ciples of database Systems, pages 53-59, March PI S.N. Khoshafian and G.P. Copeland. Object Iden- 1986. tity. In OOPSLA-86, pages 406-416, 1986. PI C. Beeri, S. Naqvi, 0. Shmueli, and S. Tsur. WI M. Kifer and J. Wu. A Logic for Object-Oriented Sets and Negation in a Logic Database Language Logic Programming (Maier’s O-logic Revisited). (LDL). Technical Repcrt, MCC, 1987. In Proceeding8 of the ACM SIGACT-SIGMOD- SIGART Symposium on Principles of database PI C. Beeri, R. Nasr, and S. Tsur. Embedding $- Systems, March 1989. to appear. terms in a Horn-clause Logic Language. In Third International Conference on Data and Knowledge WI R. Krishnamurthy and S. Naqvi. Towards a Real Bases: Improving Usability and ReSpOnSiVeneSS, Horn Clause Language. In Proceeding8 of the Intl. pages 347-359, Morgan Kaufmann, 1988. Conference on Very Large Data Bases, 1988. 145 G. Kuper and M.Y. Vardi. A New Approach 1351 Neuhold E. and M. Stonebraker. Future Directions to Database Logic. In Proceedings of the ACM in DBMS Research. 1988. The Laguna Beech Re- SIGACT-SIGMOD-SIGART Symposium on Prin- port. ciples of database Systems, 1984. WI T.C. Przymusinski. On The Declarative Seman- 1231 G.M. Kuper. An Extension of LPS to Arbitrary tics of Deductive Databases and Logic Programs. Sets. Technical Report, IBM, Yorktown Heights, In J. Minker, editor, Foundations of Deductive 1987. Databases and Logic Programming, pages 193-216, Morgan Kaufmann, Los Altos, CA, 1988. 1241 C. Lecluse and P. Richard. Modeling Inheritance and Genericity in Object-Oriented Databases. In VI M.A. Roth, H.F. Korth, and A. Silberschatz. Ex- 2-d Int. Conf. on Database Theory (ICDT), tended Algebra and Calculus for 7lNF Relational LNCS 396, pages 223-238, Springer Verlag, Databases. Technical Report 84-36, Univ. of Texas Bruges, Belgium, 1988. at Austin, 1985. PI C. Lecluse, P. Richard, and F. Veles. 02, an P81 G. Smolka and H. Ait-Kaci. Inheritance Hiemr- Object-Oriented Data Model. In Proceedings of chies: Semantics and Unification. Technical Re- the ACM SIGMOD Conference on Management of port AI-057-87, MCC, May 1987. Data, pages 424433, 1988. PI M. Stefik and D.G. Bobrow. Object-Oriented Pro- WI J.W. Lloyd. Foundations of Logic Progmmming gramming: Themes and Variations. The AI Mag- (Second Edition). Springer Verlag, 1987. azine, 40-62, January 1986. P71 D. Maier. A Logic for Objects. In Workshop PO1 D.S. Touretzky. The Mathematics of Inheritance. on Foundations of Deductive Database8 and Logic Morgan-Kaufmann, Los Altos, CA, 1986. Programming, pages 6-26, Washington D.C., Au- WI D.S. Touretzky, J.F. Horty, and R.H. Thoma- gust 1986. son. A Clash of Intuitions: The Current State of Nonmonotonic Multiple Inheritance Systems. In PI D. Maier. Why Database Languages are a Bad IJCAI-87, pages 476-482, 1987. Idea (position paper). In Proc. of the Workshop on Database Programming Languages, Roscoff, WI VbaeeObject Manager. Ontologic, Inc., 1986. User France, September 1987. Manual. P91 D. Maier, J. Stein, A. Otis, and A. Purdy. Devel- PI P. Wegner. The Object-Oriented Classification opment of an Object-Oriented DBMS. In Proceed- Paradigm. 1987. manuscript. ings of OOPSLA-86, pages 472-482, 1986. PI D. Woelk, W. Kim, and W. Luther. Multimedia [301 D. Maier and D.S. Warren. A Theory of Computed Information Management in an Object-Oriented Relations. Technical Report 80/12, Department of Database System. In Proceedings of the Intl. Con- Computer Science, SUNY at Stony Brook, Novem- ference on Very Large Data Bases, 1987. ber 1980. [311 D. Maier and D.S. Warren. Incorporation Com- puted Relations in Relational Databases. Technical Report 80/17, Department of Computer Science, SUNY at Stony Brook, December 1980. [321 J. McCarthy. First Order Theories of Individual Concepts and Propositions. In J.E. Hayes and D. Michie, editors, Machine Inteligence, pages 129- 147, Edinburgh University Press, 1979. PI M. Minsky. A Framework for Representing Knowl- edge. In J. Haugeland, editor, Mind design, pages 95-128, MIT Press, Cambridge, MA, 1981. [34] A. Motro. BAROQUE: A Browser for Relational Databases. ACM Bans. on Ofice Information Systems, 4(2):164-181, 1986. 146