PhD Thesis

PhD Candidate: Jordi Conesa Caralt

Advisor: Dr. Antoni Olivé Ramon.

Summary: One of the main stumbling blocks in the development of Information Systems (IS) lies in the creation of their conceptual schemas. A conceptual schema represents the knowledge about a domain that a given IS needs in order to be able to perform its functions. To create such a schema, designers need to know very well the domain of the IS and thy also need to have a very great abstraction ability. Yet, even when all these pre-requisites are met, there is no guarantee of success.

Ontologies can play one or more of the following roles: building, block, support and base. In the field of Information Systems, it is the base role the one that has been studied the least. We say that an ontology plays a base role when from its schema a conceptual schema is derived. The designer's task for this role is to extend the ontology until it includes as a subset the desired final conceptual schema.

The main goal of this thesis is to define a collection of automatic techniques to make possible the use of ontologies in their role base in conceptual modelling.

Three activities have been identified, namely refinement, pruning and refactoring. These activities can be executed in a sequential o iterative manner. In only a few cases some of this activities may be unnecessary. This thesis deals mainly with the pruning activity and the automatic step of refactoring. Their main contributions are:

   1. It defines a method that allows for the creation of IS conceptual schemas from general ontologies. This method allows for automatic pruning and refactoring. Its output is an optimized conceptual schema that is directly usable as the conceptual schema of the Information System.

   2. It defines a generic pruning method that can be applied in other contexts and other types of ontologies. This is the first pruning method that can be generalized to other types of ontologies or selection strategies with just minimal changes. This methods has been applied in the pruning of ontologies written in UML or OWL

   3. It defines ontology refactoring and it shows a catalogue of ontology refactoring operations. This catalogue has been created and refined by extending refactoring operations previously defined in other contexts.

   4. It formalizes some refactoring operations and defines conditions to pinpoint their opportunities.

   5. It formalizes a refactoring method that allows an automatic reduction in the size of an ontology.

Date: January 22nd, 2008

Time: 12:00h

Place: Sala del Llac. Campus Nord, edifici R.

PhD Candidate: Federico Heras.

Advisor: Dr. Javier Larrosa.

Summary: The problem of propositional satisfiability (SAT) consists in finding if there exist a assignment for variables so that they satifsfy a CNF formula. SAT is a very well known NP Complete problem that occurs in many contexts.

One version of a SAT optimization is the Weighted Maximum Satisfiability. We will called it Max-SAT. Given a set of clauses with a given associated weight the goal of Max-SAT is to find an assignment of variables so that the sum of weights of the clauses is maximum.

Algorithms based in local search for SAT can be directly applied to Max-SAT. In contrast algorithms based in exhaustive search and formula manipulation cannot and have to be adapted to solve Max-Sat.

The work presented in this thesis explores the relationship between SAT and Max-SAT. As a result we have found interesting connections between both problems which have allowed us to put forth a new environment to solve Max-SAT. Firstly, we have extended an classic SAT algorithm based on systematic search to solve Max-SAT. Secondly, we have extended the resolution rule from SAT to Max-Sat. Then we have shown empirically that a Max-SAT search algorithm can be accelerated notably by the application of the new resolution rule during search. Finally, we propose and algorithm that integrates all these techniques and others coming some other ones coming form work in SAT and Max-SAT.

Date: January 25th 2008.

Time: 12:00h

Place: Sala del Llac. Campus Nord. Edifici R.

ilapuente@lsi.upc.edu

(Back to the Newsletter)