Traditionally, the core of a Terminological Knowledge Representation System (TKRS) consists of a so-called TBox, where concepts are introduced, and an ABox, where facts about individuals are stated in terms of these concepts. This design has a drawback because in most applications the TBox has to meet two functions at a time: on the one hand, similar to a database schema, framelike structures with typing information are introduced through primitive concepts and primitive roles; on the other hand, views on the objects in the knowledge base are provided through dened concepts.
We propose to account for this conceptual separation by partitioning the TBox into two components for primitive and de ned concepts, which we call the schema and the view part. We envision the two parts to di er with respect to the language for concepts, the statements allowed, and the semantics.
We argue that by this separation we achieve more conceptual clarity about the role of primitive and de ned concepts and the semantics of terminological cycles. Moreover, three case studies show the computational bene ts to be gained from the re ned architecture.
Research on terminological reasoning usually presupposes the following abstract architecture, which re ects quite well the structure of existing systems. There is a logical representation language that allows for two kinds of statements: in the TBox or terminology, concept descriptions are introduced, and in the ABox or world description, individuals are characterized in terms of concept membership and role relationship. This abstract architecture has been the basis for the design of systems, the development of algorithms, and the investigation of the computational properties of inferences.
Given this setting, there are three parameters that characterize a terminological system: (i) the language for concept descriptions, (ii) the form of the statements allowed, and (iii) the semantics given to concepts and statements. Research tried to improve systems by modifying these three parameters. But in all existing systems and almost all theoretical studies language and semantics have been kept uniform. 1The results of these studies were unsatisfactory in at least two respects. First, it seems that tractable inferences are only possible for languages with little expressivity. Second, no consensus has been reached about the semantics of terminological cycles, although in applications the need to model cyclic dependencies between classes of objects arises constantly.
Based on an ongoing study of applications of terminological systems, we suggest to re ne the twolayered architecture consisting of TBox and ABox. Our goal is twofold: on the one hand we want to achieve more conceptual clarity about the role of primitive and de ned concepts and the semantics of terminological cycles; on the other hand, we want to improve the tradeo between expressivity and worst case complexity. Since our changes are not primarily motivated by mathematical considerations but by the way systems are used, we expect to come up with a more practical system design.
In the applications studied we found that the TBox has to meet two functions at a time. One is to declare frame-like structures by introducing primitive concepts and roles together with typing information like isa-relationships between concepts, or range restrictions and number restrictions of roles. E.g., suppose we want to model a company environment. Then we may introduce the concept Employee as a specialization of Person, having exactly one name of type Name and at least one a liation of type Department. This is similar to class declarations in object-oriented systems. For this purpose, a simple language is su cient. Cycles occur naturally in modeling tasks, e.g., the boss of an Employee is also an Employee. Such declarations have no de nitional import, they just restrict the set of possible interpretations.
The second function of a TBox is to de ne new concepts in terms of primitive ones by specifying necessary and su cient conditions for concept membership. This can be seen as de ning abstractions or views on the objects in the knowledge base. De ned concepts are important for querying the knowledge base and as left-hand sides of trigger rules. For this purpose we need more expressive languages. If cycles occur in this part they must have de nitional import.
As a consequence of our analysis we propose to split the TBox into two components: one for declaring frame structures and one for de ning views. By analogy to the structure of databases we call the rst component the schema and the second the view part. We envision the two parts to di er with respect to the language, the form of statements, and the semantics of cycles.
The schema consists of a set of primitive concept introductions, formulated in the schema language, and the view part by a set of concept de nitions, formulated in the view language. In general, the schema language will be less expressive than the view language. Since the role of statements in the schema is to restrict the interpretations we want to admit, rst order semantics, which is also called descriptive semantics in this context (see Nebel 1991), is adequate for cycles occurring in the schema. For cycles in the view part, we propose to choose a semantics that de nes concepts uniquely, e.g., least or greatest xpoint semantics. The purpose of this work is not to present the full-edged design of a new system but to explore the options that arise from the separation of TBoxes into schema and views. Among the bene ts to be gained from this re nement are the following three. First, the new architecture has more parameters for improving systems, since language, form of statements, and semantics can be speci ed di erently for schema and views. So we found a combination of schema and view language with polynomialinference procedures whereas merging the two languages into one would have led to intractability. Second, we believe that one of the obstacles to a consensus about the semantics of terminological cycles has been precisely the fact that no distinction has been made between primitive and de ned concepts. Moreover, intractability results for cycles mostly refer to inferences with de ned concepts. We proved that reasoning with cycles is easier when only primitive concepts are considered. Third, the re ned architecture allows for more di erentiated complexity measures, as shown later in the paper.
In the following section we outline our re ned architecture for a TKRS, which comprises three parts: the schema, the view taxonomy, and the world description, which comprise primitive concepts, dened concepts and assertions in traditional systems. In the third section we show by three case studies that adding a simple schema with cycles to existing systems does not increase the complexity of reason-ing.
We start this section by a short reminder on concept languages. Then we discuss the form of statements and their semantics in the di erent components of a TKRS. Finally, we specify the reasoning services provided by each component and introduce di erent complexity measures for analyzing them.
In concept languages, complex concepts (ranged over by C, D) and complex roles (ranged over by Q, R) can be built up from simpler ones using concept and role forming constructs (see Tables 1 and 2 a set of common constructs). The basic syntactic symbols are (i) concept names, which are divided into schema names (ranged over by A) and view names (ranged over by V ), (ii) role names (ranged over by P), and (iii) individual names (ranged over by a, b). An interpretation I = ( I ; I ) consists of the domain I and the interpretation function I , which maps every concept to a subset of I , every role to a subset of I I , and every individual to an element of I such that a I 6 = b I for di erent individuals a, b (Unique Name Assumption). Complex concepts and roles are interpreted according to the semantics given in Tables 1 and 2, respectively.
In our architecture, there are two di erent concept languages in a TKRS, a schema language for expressing schema statements and a view language for formulating views and queries to the system.
We rst focus our attention to the schema. The schema introduces concept and role names and states elementary type constraints. This can be achieved by inclusion axioms having one of the forms: A v D; P v A 1 A 2 ; where A, A 1 , A 2 are schema names, P is a role name, and D is a concept of the schema language. Intuitively, the rst axiom states that all instances of A are also instances of D. The second axiom states that the role P has domain A 1 and range A 2 . A schema S consists of a nite set of schema axioms.
Inclusion axioms impose only necessary conditions for being an instance of the schema name on the left-hand side. For example, the axiom \Employee v
Person" declares that every employee is a person, but does not give a su cient condition for being an employee.
A schema may contain cycles through inclusion axioms (see Nebel 1991 for a formal de nition). So one may state that the bosses of an employee are themselves employees, writing \Employee v 8boss.Employee." In general, existing systems do not allow for terminological cycles, which is a serious restriction, since cycles are ubiquitous in domain models.
There are two questions related to cycles: the rst is to x the semantics and the second, based on this, to come up with a proper inference procedure. As to the semantics, we argue that axioms in the The view part contains view de nitions of the form V : = C; where V is a view name and C is a concept in the view language. Views provide abstractions by de ning new classes of objects in terms of the concept and role names introduced in the schema. We refer to \V : = C" as the de nition of V . The distinction between schema and view names is crucial for our architecture. It ensures the separation between schema and views.
A view taxonomy V is a nite set of view de nitions such that (i) for each view name there is at most one de nition, and (ii) each view name occurring on the right hand side of a de nition has a de nition in V.
Di erently from schema axioms, view de nitions give necessary and su cient conditions. As an example of a view, one can describe the bosses of the employee Bill as the instances of \BillsBosses : = 9boss-of.fBILLg."
Whether or not to allow cycles in view de nitions is a delicate design decision. Di erently from the schema, the role of cycles in the view part is to state recursive de nitions. For example, if we want to describe the group of individuals that are above Bill in the hierarchy of bosses we can use the de nition \BillsSuperBosses : = BillsBosses t 9boss-of.BillsSuperBosses." But note that this does not yield a de nition if we assume descriptive semantics because for a xed interpretation of BILL and of the role boss-of there may be several ways to interpret BillsSuperBosses in such a way that the above equality holds. In this example, we only obtain the intended meaning if we assume least xpoint semantics. This observation holds more generally: if cycles are intended to uniquely de ne concepts then descriptive semantics is not suitable. However, least or greatest xpoint semantics or, more generally, a semantics based on the -calculus yield unique denitions (see Schild 1994). Unfortunately, algorithms for subsumption of views under such semantics are known only for fragments of the concept language de ned in Tables 1 and 2.
In this paper, we only deal with acyclic view taxonomies. In this case, the semantics of view de nitions is straightforward. An interpretation I satis es the de nition V :
= C if V I = C I , and it is a model for a view taxonomy V if I satis es all de nitions in V.
A state of a airs in the world is described by assertions of the form C(a); R(a; b); where C and R are concept and role descriptions in the view language. Assertions of the form A(a) or P(a; b), where A and P are names in the schema, resemble basic facts in a database. Assertions involving complex concepts are comparable to view updates.
A world description W is a nite set of assertions. The semantics is as usual: an interpretation I satis es C(a) if a I 2 A I and it satis es R(a; b) if (a I ; b I ) 2 R I ; it is a model of W if it satis es every assertion in W.
Summarizing, a knowledge base is a triple = hS; V; Wi, where S is a schema, V a view taxonomy, and W a world description. An interpretation I is a model of a knowledge base if it is a model of all three components.
For each component, there is a prototypical reasoning service to which the other services can be reduced.
Schema Validation: Given a schema S, check whether there exists a model of S that interprets every schema name as a nonempty set.
View Subsumption: Given a schema S, a view taxonomy V, and view names V 1 and V 2 , check whether V I 1 V I 2 for every model I of S and V;
Instance Checking: Given a knowledge base , an individual a, and a view name V , check whether a I 2 V I holds in every model I of .
Schema validation supports the knowledge engineer by checking whether the skeleton of his domain model is consistent. Instance checking is the basic operation in querying a knowledge base. View subsumption helps in organizing and optimizing queries (see e.g. Buchheit et al. 1994). Note that the schema S has to be taken into account in all three services and that the view taxonomy V is relevant not only for view subsumption, but also for instance checking.
In systems that forbid cycles, one can get rid of S and V by expanding de nitions. This is not possible when S and V are cyclic.
The separation of the core of a TKRS into three components allows us to introduce re ned complexity measures for analyzing the di culty of inferences. The complexity of a problem is generally measured with respect to the size of the whole input. However, with regard to our setting, three di erent pieces of input are given, namely the schema, the view taxonomy, and the world description. For this reason, di erent kinds of complexity measures may be dened, similarly to what has been suggested in Vardi, 1982] for queries over relational databases. We consider the following measures (where jXj denotes the size of X): Schema Complexity: the complexity as a function of jSj;
View Complexity: the complexity as a function of jVj;
World Description Complexity: the complexity as a function of jWj;
Combined Complexity: the complexity as a function of jSj + jVj + jWj.
Combined complexity takes into account the whole input. The other three instead consider only a part of the input, so they are meaningful only when it is reasonable to suppose that the size of the other parts is negligible. For instance, it is sensible to analyze the schema complexity of view subsumption because usually the schema is much bigger than the two views which are compared. Similarly, one might be interested in the world description complexity of instance checking whenever one can expect W to be much larger than the schema and the view part.
It is worth noticing that for every problem combined complexity, taking into account the whole input, is at least as high as the other three. For example, if the complexity of a problem is O(jSj jVj jWj), its combined complexity is cubic, whereas the other ones are linear. Similarly, if the complexity of a given problem is O(jSj jVj ), both its combined complexity and its view complexity are exponential, its schema complexity is polynomial, and its world description complexity is constant.
In this paper, we use combined complexity to compare the complexity of reasoning in our architecture with the traditional one. Moreover, we use schema complexity to show how the presence of a large schema a ects the complexity of the reasoning services previously de ned. View and world description complexity have been investigated (under di erent names) in Nebel, 1990, Baader, 1990] and Schaerf, 1993, Donini et al., 1994], respectively.
We studied some illustrative examples that show the advantages of the architecture we propose. We extended three systems by a simple cyclic schema language and analyzed their computational properties.
As argued before, a schema language should at least be expressive enough for declaring subconcept relationships, restricting the range of roles, and specifying roles to be necessary (at least one value) or single valued (at most one value). These requirements are met by the language SL, which was introduced in Buchheit et al., 1994] and that is de ned by the following syntax rule: C; D ! A j 8P.A j ( 1 P) j ( 1 P): Obviously, it is impossible to express in SL that a concept is empty. Therefore, schema validation in SL is trivial. Also, subsumption of concept names is polynomially decidable.
We proved that inferences become harder for extensions of SL. If we add inverse roles, schema validation remains trivial, but subsumption of schema names becomes NP-hard. If we add any construct by which one can express the empty concept|like disjointness axioms|schema validation becomes NPhard. However, in our opinion this does not mean that extensions of SL are not feasible. For some extensions, there are natural restrictions on the form of schemas that decrease the complexity. Also, it is not clear whether realistic schemas will contain structures that require complex computations. In all the three cases studied, the schema language is SL. For the view language, we propose three di erent languages derived from three actual systems described in the literature, namely the deductive object-oriented database system Concept-Base Jarke, 1992], and the terminological systems kris Baader and Hollunder, 1991] and classic Borgida et al., 1989]. We investigated the computational properties of the reasoning services with respect to SL-schemas. We aimed at showing two results: (i) reasoning w.r.t. schema complexity is always tractable, (ii) combined complexity is not increased by the presence of terminological cycles in the schema. In all three cases, we assume that view names are allowed in membership assertions and that the view taxonomy is acyclic. In this setting, every view name can be substituted with its de nition. For this reason, from this point on, we suppose that view concepts are completely expanded. Therefore, when evaluating the complexity, we replace the size of the view part by the size of the concept representing the view.
We have found the following results for the three systems in which SL is the schema language and the concept language the abstraction of the query language of ConceptBase introduced in We conclude that adding (possibly cyclic) schema information does not change the complexity of reasoning within the systems taken into account.
We have proposed to replace the traditional TBox in a terminological system by two components: a schema, where primitive concepts describing framelike structures are introduced, and a view part that contains de ned concepts. We feel that this architecture re ects adequately the way terminological systems are used in most applications.
We also think that this distinction can clarify the discussion about the semantics of cycles. Given the di erent functionalities of the schema and view part, we propose that cycles in the schema are interpreted with descriptive semantics while for cycles in the view part a de nitional semantics should be adopted.
In three case studies we have shown that the revised architecture yields a better tradeo between expressivity and the complexity of reasoning.
The schema language we have introduced might be su cient in many cases. Sometimes, however, one might want to impose more integrity constraints on primitive concepts than those which can be expressed in it. We see two solutions to this problem: either enrich the language and have to pay by a more costly reasoning process, or treat such constraints in a passive way by only verifying them for the objects in the knowledge base. The second alternative can be given a logical semantics in terms of epistemic operators (see Donini et al. 1992).