M. and F. M. and Buchheit1 Donini2 W. and Nutt1
the way systems are used, we expect to come up with as a specialization of Person, having exactly one algorithms, and the investigation of the computalayered architecture consisting of TBox and ABox. characterize a terminological system: (i) the lanalthough in applications the need to model cyclic The results of these studies were unsatisfactory in Given this setting, there are three parameters that ily motivated by mathematical considerations but by concepts and statements. Research tried to improve dependencies between classes of objects arises contional properties of inferences. language and semantics have been kept uniform.1 E.g., suppose we want to model a company environIn the applications studied we found that the in modeling tasks, e.g., the boss of an Employee is Our goal is twofold: on the one hand we want to tions in object-oriented systems. For this purpose, a minological systems, we suggest to rene the twodeclare frame-like structures by introducing primia more practical system design. statements allowed, and (iii) the semantics given to type Department. This is similar to class declaraall existing systems and almost all theoretical studies inferences are only possible for languages with litguage for concept descriptions, (ii) the form of the systems by modifying these three parameters. But in terminological cycles; on the other hand, we want to at least two respects. First, it seems that tractable stantly. primitive and dened concepts and the seman tics of case complexity. Since our changes are not primarrange restrictions and number restrictions of roles. ment. Then we may introduce the concept Employee TBox has to meet two functions at a time. One is to improve the tradeo bet ween expressivity and worst relationship. This abstract architecture has been the name of type Name and at least one aliation of basis for the design of systems, the development of Based on an ongoing study of applications of tertle expressivity. Second, no consensus has been reached about the semantics of terminological cycles, tive concepts and roles together with typing information like isa-relationships between concepts, or achieve more conceptual clarity about the role of simple language is sucien t. Cycles occur naturally in the view part, we propose to choose a semantics In the following section we outline our rened arinto schema and views. Among the benets to be In the third section we show by three case studies ences with dened concepts. We proved that reamulated in the view language. In general, the schema purpose we need more expressive languages. If cyAs a consequence of our analysis we propose to schema and views. So we found a combination of introductions, formulated in the schema language, part. We envision the two parts to dier with retional import, they just restrict the set of possible soning with cycles is easier when only primitive congained from this renemen t are the following three. ned concepts and assertions in traditional systems.
The second function of a TBox is to dene new base and as left-hand sides of trigger rules. For this split the TBox into two components: one for declarscription, which comprise primitive concepts, decepts are considered. Third, the rened arc hitecture views on the objects in the knowledge base. Dened the semantics of terminological cycles has been preguage. Since the role of statements in the schema cles occur in this part they must have denitional is to restrict the interpretations we want to admit, cisely the fact that no distinction has been made The purpose of this work is not to present the that denes concepts uniquely , e.g., least or greatest schema and view language with polynomial inference allows for more dieren tiated complexity measures, procedures whereas merging the two languages into semantics in this context (see Nebel 1991), is adelanguage will be less expressive than the view lanbetween primitive and dened concepts. Moreover, The schema consists of a set of primitive concept concepts are important for querying the knowledge the options that arise from the separation of TBoxes bership. This can be seen as dening abstractions or the schema, the view taxonomy, and the world deand the view part by a set of concept denitions, foring frame structures and one for dening views. By rst order seman tics, which is also called descriptive chitecture for a TKRS, which comprises three parts: ments, and semantics can be specied dieren tly for spect to the language, the form of statements, and full-edged design of a new system but to explore the semantics of cycles. interpretations. improving systems, since language, form of statenecessary and sucien t conditions for concept memalso an Employee. Such declarations have no denilieve that one of the obstacles to a consensus about import. intractability results for cycles mostly refer to inferxpoin t semantics. concepts in terms of primitive ones by specifying that adding a simple schema with cycles to existing one would have led to intractability. Second, we berst componen t the schema and the second the view First, the new architecture has more parameters for quate for cycles occurring in the schema. For cycles as shown later in the paper. systems does not increase the complexity of reasonanalogy to the structure of databases we call the to \V = C" as the denition of V . The distincare above Bill in the hierarchy of bosses we can use the denition \BillsSuperBosses BillsBosses t =: we want to describe the group of individuals that tions such that (i) for each view name there is at curring on the right hand side of a denition has a view language. Views provide abstractions by dention between schema and view names is crucial for the schema, the role of cycles in the view part where V is a view name and C is a concept in the tions is a delicate design decision. Dieren tly from : ample of a view, one can describe the bosses of A view taxonomy V is a nite set of view deniDieren tly from schema axioms, view denitions schema and views. and names introduced in the schema. We refer role: is to state recursive denitions. For example, if give necessary and sucien t conditions. As an exdenition in V. most one denition, and (ii) each view name ocWhether or not to allow cycles in view denithe employee Bill as the instances of \BillsBosses = 9boss-of.fBILLg." ing new classes of objects in terms of the concept our architecture. It ensures the separation between tain the intended meaning if we assume least xpoin t semantics. This observation holds more generally: if V. or greatest xpoin t semantics or, more generally, a not yield a denition if we assume descriptive senitions (see Schild 1994). Unfortunately, algorithms above equality holds. In this example, we only obsemantics based on the -calculus yield unique deonomies. In this case, the semantics of view denidened in T ables 1 and 2. tions is An interpretation I satises straightfor:ward. to interpret BillsSuperBosses in such a way that the for a view taxonomy V if I satises all denitions in In this paper, we only deal with acyclic view taxand of the role boss-of there may be several ways the denition V = C if V I = , and it is a model CI 9boss-of.BillsSuperBosses." But note that this does for subsumption of views under such semantics are mantics because for a xed interpretation of BILL descriptive semantics is not suitable. However, least cycles are intended to uniquely dene concepts then known only for fragments of the concept language in a terminological system by two components: a like structures are introduced, and a view part that costly reasoning process, or treat such constraints in either enrich the language and have to pay by a more discussion about the semantics of cycles. Given the We have proposed to replace the traditional TBox view part a denitional seman tics should be adopted. on primitive concepts than those which can be exa passive way by only verifying them for the objects tems are used in most applications. pressed in it. We see two solutions to this problem: ture reects adequately the way terminological syswe propose that cycles in the schema are interpreted be sucien t in many cases. Sometimes, however, In three case studies we have shown that the recontains dened concepts. We feel that this architecvised architecture yields a better tradeo between dieren t functionalities of the schema and view part, The schema language we have introduced might expressivity and the complexity of reasoning. with descriptive semantics while for cycles in the one might want to impose more integrity constraints schema, where primitive concepts describing frameWe also think that this distinction can clarify the ways tractable, (ii) combined complexity is not inrespect to SL-schemas. We aimed at showing two al., or the language oered b y kris or clas- 1994], et al., We investigated the com- [Borgida 1989]. sic, respectively. results: (i) reasoning w.r.t. schema complexity is alconcept language the abstraction of the query lanevaluating the complexity, we replace the size of the concepts are completely expanded. Therefore, when putational properties of the reasoning services with We have found the following results for the three reason, from this point on, we suppose that view systems in which SL is the schema language and the are allowed in membership assertions and that the view part by the size of the concept representing the the schema. creased by the presence of terminological cycles in view taxonomy is acyclic. In this setting, every view guage of ConceptBase introduced in et [Buchheit In all three cases, we assume that view names name can be substituted with its denition. For this view.