A Knowledge Discovery (KD) process is a complex inter-disciplinary task, where different types of techniques coexist and cooperate for the purpose of extracting useful knowledge from large amounts of data. So, it is desirable having a unifying environment, built on a formal basis, where to design and perform the overall process. In this paper we propose a general framework which formalizes a KD process as an algebraic expression, that is, as a composition of operators representing elementary operations on two worlds: the data and the model worlds. Then, we describe a KD platform, named Rialto, based on such a framework. In particular, we provide the design principles of the underlying architecture, highlight the basic features, and provide a number of experimental results aimed at assessing the effectiveness of the design choices.

This paper describes Olex, a novel method for the automatic induction of rule-based text classifiers. Olex supports a hypothesis language of the form "if T1or hellip or Tnoccurs in document d, and none of T1+n,... Tn+moccurs in d, then classify d under category c," where each Tiis a conjunction of terms. The proposed method is simple and elegant. Despite this, the results of a systematic experimentation performed on the REUTERS-21578, the OHSUMED, and the ODP data collections show that Olex provides classifiers that are accurate, compact, and comprehensible. A comparative analysis conducted against some of the most well-known learning algorithms (namely, Naive Bayes, Ripper, C4.5, SVM, and Linear Logistic Regression) demonstrates that it is more than competitive in terms of both predictive accuracy and efficiency.

This paper describes an advanced authorization mechanism based on a logic formalism. The model supports both positive and negative authorizations. It also supports derivation rules by which an authorization can be granted on the basis of the presence

This paper presents an extension of Disjunctive Datalog (DATALOG/sup V,/spl sim//) by integrity constraints. These are of two types: strong, that is, classical integrity constraints and weak, that is, constraints that are satisfied if possible. While strong constraints must be satisfied, weak constraints express desiderata, that is, they may be violated-actually, their semantics tends to minimize the number of violated instances of weak constraints. Weak constraints may be ordered according to their importance to express different priority levels. As a result, the proposed language (call it, DATALOG/sup V,/spl sim/,c/) is well-suited to represent common sense reasoning and knowledge-based problems arising in different areas of computer science such as planning, graph theory optimizations, and abductive reasoning. The formal definition of the language is first given. The declarative semantics of DATALOG/sup V,/spl sim/,c/ is defined in a general way that allows us to put constraints on top of any existing (model-theoretic) semantics for DATALOG/sup V,/spl sim// programs. Knowledge representation issues are then addressed and the complexity of reasoning on DATALOG/sup V,/spl sim/,c/ programs is carefully determined. An in-depth discussion on complexity and expressiveness of DATALOG/sup V,/spl sim/,c/ is finally reported. The discussion contrasts DATALOG/sup V,/spl sim/,c/ to DATALOG/sup V,/spl sim// and highlights the significant increase in knowledge modeling ability carried out by constraints.

We propose a logic formalism that naturally supports the encoding of complex security specifications. This formalism relies on a hierarchically structured domain made of subjects, objects and privileges. Authorizations are expressed by logic rules. The formalism supports both negation by failure (possibly unstratified) and true negation. The latter is used to express negative authorizations. It turns out that conflicts may result from a set of authorization rules. Dealing with such conflicts requires the knowledge of the domain structure, such as grantor priorities and object/subject hierarchies, which is used in the deductive process to determine which authorization prevails, if any, on the others. Often, however, conflicts are unsolvable, as they express intrinsic ambiguities. We have devised two semantics as an extension of the well-founded and the stable model semantics of logic programming. We have also defined a number of access policies, each based on two orthogonal choices: one is related to the way of how we cope with multiplicity of authorization sets in case of stable model semantics; the other is concerned with the open/closed assumption. A comparative analysis of the proposed authorization policies, based on their degree of permissivity shows that they form a complete lattice.

The Bottom-up Query machine (BQM)-the role played by our system in the framework of the KIWIS system (K. Apt et al., 1987)-extends deductive database technology with knowledge structuring capabilities to provide an advanced environment for the development of data and knowledge based applications. The system relies on a knowledge representation language that combines the declarativeness of logic programming with the notions of object, inheritance with exceptions, and message passing. Exceptions are supported by allowing rules with negated heads. The use of exceptions inside the inheritance mechanism makes the language inherently nonmonotonic. The paper contains a comprehensive description of both the language and the implementation principles of the BQM system. It begins by providing a model theoretic semantics of the language based on the notion of least model. A fixpoint semantics, providing a constructive definition of the least model, is given as well. Then, a number of implementation techniques for efficient query evaluation are described. Such techniques significantly extend "traditional" deductive database query evaluation strategies to deal with monotonic reasoning. A description of the architecture of the current prototype of the BQM system is also given.

The BQM system extends deductive database technology with knowledge structuring capabilities to provide an advanced environment for the development of data and knowledge-based applications. The system relies on a knowledge representation language that combines the declarativeness of logic programming with the notions of object, inheritance with exceptions and message passing. Exceptions are supported by allowing rules with negated heads. The use of exceptions inside the inheritance mechanism makes the language inherently nonmonotonic. The paper describes BQM focusing on both the language and the implementation techniques. An informal overview of the language is first given. Then, a number of techniques for efficient query evaluation are presented. These techniques significantly extend "traditional" deductive database query evaluation strategies to deal with nonmonotonic reasoning. A description of the architecture of the current prototype of the BQM system is also given.

Ordered logic programming (OLP) is an elegant, yet powerful extension of logic programming with the object-oriented notions of inheritance and exceptions. The latter are expressed by allowing rules with negated heads. The capability of expressing nonmonotonic reasoning is one of the major features of OLP. In this paper we extend OLP to include sets. The new language is called OLPS (ordered logic programming with sets). An interesting aspect of OLPS is the way sets are integrated in the framework of a non-monotonic logic, resulting in a declarative language able to model complex knowledge domains. We show that any OLPS program has a least model and that this model can be computed in a bottom-up fashion by iteratively applying a suitable operator. We compare OLPS with other logic languages with sets and show that the semantics of OLPS programs is a declarative generalization of the well-founded semantics of classical logic programs.

The design and a prototypical implementation of COMPLEX, which is a logic-based system extended with concepts from the object-oriented paradigm and is intended as a tool for the development of knowledge-based applications, are described. The system supports a logic language, called Complex-Datalog (C-Datalog), enhanced by semantic constructs to provide facility for data abstraction. Its implementation is based on a bottom-up computational model that guarantees a fully declarative style of programming. However, the user is also given the possibility of running a query using a top-down model of computation. Efficiency of execution is the result of the integration of different novel technologies for the compilation and the execution of queries.>

Systems EROS is a physical design tool for CODASYL database systems which covers a large spectrum of decision variables, notably location mode, set implementation, set order, and search keys. System EROS is based on a model where the CODASYL physical database design problem is formulated as an extension of the index selection problem in the relational database environment. Optimization algorithms for index selection are extended to solve the more complex problem of selecting a good physical access path configuration for CODASYL databases. The proposed approach represents a unified solution to the physical database design problem for both CODASYL and relational systems.>

A heuristic algorithm for the selection of an optimal access path configuration for CODASYL databases is presented. This algorithm is based on the idea of extending index selection techniques proposed for relational systems to COD ASYL systems. The proposed approach has the worth effacing the physical design problem in a unified way; moreover, it allows for covering a large spectrum of physical decision variables, namely, location modes, set implementations, set orders and search keys.

General architecture of a transaction workload analyzer for the Codasyl DBMS environment is presented. The proposed solution is discussed in the framework of general performance problems typical for a Codasyl database environment. Major functions of the Workload Analyzer such as the data manipulation algorithm analysis, the DML statement expansion and the cost model underlying the workload evaluation are described.