96/1
ON COMPROMISING
UPDATES IN LABELLED DATABASES
F.C.C. Dargam, 66pp
This paper presents a logical system, CIULDS, as a labelled realization to our approach of Compromising Interfering Updates. Basically, this approach proposes a method for handling logically conflicting inputs into knowledge bases, via restricting their consequences. The main idea is to update the database with as many consistent consequences of the inputs as possible, in the case that the inputs themselves are not allowed to be kept in it. And in the case that a revision applies, the idea is to keep as many as possible of the consistent consequences of the retracted sentences as a compromise.
Our approach caters for the specific case where compromised solutions for revising knowledge bases apply, when conflicts involving updates occur. In comparison with approaches that require preference between conflicting inputs, or that avoid them by cancelling them out completely, our approach fits as an alternative which provides more informative results, and is directed to some specific applications. Hence, instead of preventing updates to be performed, when they introduce inconsistency to the system, our approach proposes to generate the consequences of the conflicting inputs, and to get rid of the inconsistency, via a minimal number of retractions of those consequences. We expect the resulting database to be consistent w.r.t. the integrity constraints, and to retain a safe-maximal subset of the consistent non-supported consequences. This reconciliation of conflicting inputs follows some specified postulates for compromised revision.
CIULDS is based on the Labelled Deductive Systems framework (LDS). This framework deals with labelled formulae as its basic units of information. By labelling the formulae, we are provided with a way of including in the labels extra information to the system. The main motivation for adopting LDS as the underlying framework of this formalization was to take advantage of its labelling facility, to control the derivation process of the compromised consequences. We embed in the labelling propagation conditions, which act on the inference rules, part of the control mechanism for the compromised approach. This control mechanism helps the update operations to perform the reconciliation of conflicting inputs. The update operations invoke a compromised revision on the labelled database, whenever conflicts arise.
In this paper, we present briefly our main motivations and we discuss the general issue of conflict resolution and theory revision. We introduce the basic specification of our approach CIU, for the case of database updates, describing the adopted policies for reconciling conflicting updates under a compromised reasoning perspective. We introduce the CIULDS system, by describing informally its main features and definitions. In CIULDS, we propose a specific revision method which applies some compromising criteria for achieving the revised database. Finally, we summarize the system’s main properties.
96/2
A COMPROMISED
CHARACTERIZATION TO BELIEF REVISION
F.C.C. Dargam, 80pp
This paper proposes a method for handling logically conflicting inputs into knowledge bases. Basically, it concerns reconciling conflicting inputs with the underlying theory, via restricting their consequences. The main idea is to update the database with as many consistent consequences of the inputs as possible, in the case that the inputs themselves are not allowed to be kept in it. And in the case that a revision applies, the idea is to keep as many as possible of the consistent consequences of the retracted sentences as a compromise.
Resolving conflicting updates in dynamic databases, for instance, are frequent and critically important problems of real applications. Such problems require the revision of theories and knowledge bases. It is not realistic to aim for a generic approach in those cases, since theory revision is fundamentally dependent on application-specific mechanisms, principles and heuristics. The approach we propose here, caters for the specific case where compromised solutions for revising knowledge bases apply, when conflicts involving updates occur. In comparison with approaches that require preference between conflitting inputs, or that avoid them by cancelling them out completely, our approach fits as an alternative which provides more informative results. Examples of inputs include database updates, actions, and beliefs.
In more practical terms, consider the situation where K is a database and A an input. Assume that A is inconsistent with K. Current belief revision/update approaches will keep A and maintain consistency by selecting some element from K to form a revised database, usually denoted by K*A. There is a lot of research in this area, both theorectical, e.g.: the AGM theory of belief revision, and algorithmic research, e.g.: Reason Mantenance Systems.
Our aim is to offer an alternative approach, restricted to some specific applications, which is flexible enough to keep more data in K in the case of conflicts. We view the above situation as a conflict between two inputs (K and A) into an empty database, and we tackle the problem of reconciling these inputs. Under our approach, the conflicting input A is kept in K only in the case that A does not directly contradict K's integrity constraints, in which case a revision also applies in order to restore consistency. However, in the case that A is not allowed to be kept in K, its eventual consistent consequences, w.r.t. the existing data of K, are added to the database under the compromised policy of our approach.
This way, instead of preventing updates to be performed, when they introduce inconsistency to the system, our approach proposes to generate the consequences of the conflicting inputs, and to get rid of the inconsistency, via a minimal number of retractions of those consequences. We expect the resulting database to be consistent w.r.t. the integrity constraints, and to retain a maximal subset of the consistent non-supported consequences. This reconciliation of conflicting inputs follows some specified postulates for compromised revision.
Justifications for the proposed approach are mainly based on its practical applications. In particular, design processes, where one builds up the goal state of a particular task, via performances of intermediary updates. Within this procedure, compromised results of updates can help to build up the goal state, when conflicts arise. This is so because, in general, our approach provides more information about the setting, in order to carry on the application development. We also find applications in AI, in particular in theory revision, where our approach can provide a compromised way for revising a theory base with conflicting information.
96/3
THE INTEGRATION
OF FUNCTIONAL LANGUAGES AND RELATIONAL DATABASES
A.J. Field and J.A.R. Hutton, 18pp
The rapid increase in the use and size of relational databases is demanding increasingly fast and efficient database management systems. There is currently considerable research effort being directed towards the use of parallel processing to provide such performance improvements.
Here we extend the Haskell language and its compiler to support SQL database queries as the first step towards performing query processing in a parallel function environment. SQL queries are generated from the translation of Haskell list comprehensions at compile-time and are used to query a relational database at run-time thereby allowing a Haskell program to access and process data stored in a relational database. We shown that query processing can be partitioned between the SQL and Haskell domains and conclude that if query processing is migrated into the Haskell domain with both domains supported on the same hardware platform then access performance is reduced. However, it is proposed that if separate platforms, and in particular a parallel Haskell platform are used to support the two processing domains, then increased performance should be possible. Finally we explore some other areas of interest such as lazy database access and dynamic query construction that might be the subject further work.
96/4
TOPOSES POUR
LES NULS
S. Vickers, 9pp
A brief introduction to Grothendieck's idea of toposes as generalized topological spaces, written from a topological viewpoint.
96/5
BOUNDING THE
ATTRACTOR OF AN IFS
A. Edalat, D.W.N. Sharp and R. Lyndon While, 9pp
Fractal images defined by an iterated function system (IFS) are specified by a finite number of contractive affine transformations. In order to plot the attractor of an IFS on the screen of a digital computer, it is necessary to determine a bounding area for the attractor. Given a point on the plane, we obtain a formula for the radius of a circle centred on that point that contains the attractor of the IFS. We then describe an algorithm to find the point on the plane such that the bounding circle centred on that point has minimum radius.
96/6
A TIGHTER BOUND
ON THE AREA OCCUPIED BY A FRACTAL IMAGE
D.W.N. Sharp and R. Lyndon While, 4pp
We derive a bounding circle for a fractal image specified by an iterated function system. The radius of the bounding circle is smaller than those from previously published material. The bounding circle is important in fractal design and plotting software as it enables a fractal image to be scaled correctly to fit the screen of a digital computer.
96/7
THE KNIFE CHANGE
MINIMIZATION PROBLEM. DEFINITION, PROPERTIES, HEURISTICS
S. Drossopoulou, 7pp
We define formally the Knife Change Minimization Problem, we prove some properties which reduce the search space, and then describe some heuristsics.
At one of the last stages of the paper construction process customer widths have to be cut out of jumbo reels. For example, the widths 50,40,60,40, 30,50,50,50 and 60,40,40,40 may have to be cut out of three jumbo reels of width 200. The collections of indivdidual widths (e.g. 50-40-60-40) are called patterns.
The order in which to consider the patterns (i.e. the route) can be arbitrary, and the order in which to cut each pattern is arbitrary as well. Each different solution involves a different number of knife changes, e.g. the solution from above involves 12 knife changes, whereas the solution 50-40-40-60, 5-4-4-4 and 50-50-50-30 involves only 7 knife changes. The objective is to find the solution with the minimal number of knife changes, or, because the search space is immense, to approximate such a solution.
We first give some auxiliary definitions describing operations on sequences, bags and sets. We then define formally the problem, the solution space and the cost function in terms of the above. We prove some properties which reduce the search space, and then we describe heuristics.
96/8
JAVA IS TYPE
SAFE -- PROBABLY
S. Drossopoulou, S. Eisenbach, 30pp
Amidst rocketing numbers of enthusiastic Java programmers and internet applet users, there is growing concern about the security of executing Java code produced by external, unknown sources. Rather than waiting to find out empirically what damage Java programs do, we aim to examine first the language and then the environment, looking for points of weakness. A proof of the soundness of the Java type system is a first, necessary step towards demonstrating which Java programs won't compromise computer security.
We consider a type safe subset of Java describing primitive types, classes, inheritance, instance variables and methods, interfaces, shadowing, dynamic method binding, object creation, null and arrays. We argue that for this subset the type system is sound, by proving that program execution preserves the types, up to subclasses/subinterfaces.
96/9
ENHANCEMENTS
TO A PITCH DETECTION SYSTEM
D.W.N. Sharp, 6pp
This paper describes some enhancements to a pitch detection algorithm presented in an earlier paper by the author. The enhancements reduce flickering between adjacent semitones when the algorithm is used as part of a pitch to MIDI converter. The enhancements also permit less memory space to be used and minimise accidental octave jumping. The enhancements illustrate the use of voting techniques for pattern recognition applications.
96/10
BALLOON TYPES:
CONTROLLING SHARING OF STATE IN DATA TYPES
P.S. Almeida, 25pp
Current data abstraction mechanisms are not adequate to control sharing of state in the general case involving objects in linked structures. The pervading possibility of sharing is a source of errors and an obstacle to language implementation techniques.
We present a general extension to programming languages which makes the ability to share state a first class property of a data type, resolving a long-standing flaw in existing data abstraction mechanisms.
Balloon types enforce a strong form of encapsulation: no state reachable (directly or transitively) by a balloon object is referenced by any external object. Syntactic simplicity is achieved by relying on a non-trivial static analysis as the checking mechanism.
Balloon types are applicable in a wide range of areas such as program transformation, memory management and distributed systems. They are the key to obtaining self-contained composite objects, truly opaque data abstractions and value types - important concepts for the development of large scale, provably correct programs.