The advent of the World Wide Web has created an explosion in the available on-line information. As the range of potential choices expand, the time and effort required to sort through them also expands. We propose a formal framework for expressing and combining user preferences to address this problem. Preferences can be used to focus search queries and to order the search results. A preference is expressed by the user for an entity which is described by a set of named fields; each field can take on values from a certain type. The * symbol may be used to match any element of that type. A set of preferences can be combined using a generic combine operator which is instantiated with a value function, thus providing a great deal of flexibility. Same preferences can be combined in more than one way and a combination of preferences yields another preference thus providing the closure property. We demonstrate the power of our framework by illustrating how a currently popular personalization system and a real-life application can be realized as special cases of our framework. We also discuss implementation of the framework in a relational setting.

A distributed multimedia information system allows users to access data of different modalities, from different data sources, ranked by various combinations of criteria. Fagin (1996) gives an algorithm for efficiently merging multiple ordered streams of ranked results, to form a new stream ordered by a combination of those ranks. In this paper we describe the implementation of Fagin's algorithm in an actual multimedia middleware system, including a novel, incremental version of the algorithm that supports dynamic exploration of data. We show that the algorithm would perform well as part of a single multimedia server and can even be effective in the distributed environment (for a limited set of queries), but that the assumptions it makes about random access limit its applicability dramatically. Our experience provides a better understanding of an important algorithm, and exposes an open problem for distributed multimedia information systems.

The goal of the Garlic [1] project is to build a multimedia information system capable of integrating data that resides in different database systems as well as in a variety of non-database data servers. This integration must be enabled while maintaining the independence of the data servers, and without creating copies of their data. "Multimedia" should be interpreted broadly to mean not only images, video, and audio, but also text and application specific data types (e.g., CAD drawings, medical objects, …). Since much of this data is naturally modeled by objects, Garlic provides an object-oriented schema to applications, interprets object queries, creates execution plans for sending pieces of queries to the appropriate data servers, and assembles query results for delivery back to the applications. A significant focus of the project is support for "intelligent" data servers, i.e., servers that provide media-specific indexing and query capabilities [2]. Database optimization technology is being extended to deal with heterogeneous collections of data servers so that efficient data access plans can be employed for multi-repository queries.A prototype of the Garlic system has been operational since January 1995. Queries are expressed in an SQL-like query language that has been extended to include object-oriented features such as reference-valued attributes and nested sets. In addition to a C++ API, Garlic supports a novel query/browser interface called PESTO [3]. This component of Garlic provides end users of the system with a friendly, graphical interface that supports interactive browsing, navigation, and querying of the contents of Garlic databases. Unlike existing interfaces to databases, PESTO allows users to move back and forth seamlessly between querying and browsing activities, using queries to identify interesting subsets of the database, browsing the subset, querying the content of a set-valued attribute of a particularly interesting object in the subset, and so on.

No abstract available.

Set constraints are relations between sets of terms. They have been used extensively in various applications in program analysis and type inference. Recently, several algorithms for solving general systems of positive set constraints have appeared. In this paper we consider systems of mixed positive and negative constraints, which are considerably more expressive than positive constraints alone. We show that it is decidable whether a given such system has a solution. The proof involves a reduction to a number-theoretic decision problem that may be of independent interest.

Language designers and implementors have avoided specifying and preserving the meaning of programs that produce errors. This is apparently because being forced to preserve error behavior limits severely the scope of program optimization, even for correct programs. However, error behavior preservation is desirable for debugging, and error behavior must be preserved in any language that permits user-generated errors (i.e., exceptions). This article presents a technique for expressing general program transformations for languages that possess a rich collection of distinguishable error values. This is accomplished by defining a higher-order function called Safe , which can be used to annotate those portions of a program that are guaranteed not to produce errors. It is shown that this facilitates the expression of very general program transformations, effectively giving program transformations in a language with many error values the same power and generality as program transformations in a language with only a single error value. Using the semantic properties of Safe , it is possible to provide some useful sufficient conditions for establishing the correctness of transformations in the presence of errors. In particular, a Substitutability theorem is proven, which can be used to justify “in-context” optimizations: transformations that alter the meanings of subexpressions without changing the meaning of the whole program. Finally, the effectiveness of the technique is demonstrated by some examples of its use in an optimizing compiler.

We present a simple and powerful type inference method for dynamically typed languages where no type information is supplied by the user. Type inference is reduced to the problem of solvability of a system of type inclusion constraints over a type language that includes function types, constructor types, union, intersection, and recursive types, and conditional types. Conditional types enable us to analyze control flow using type inference, thus facilitating computation of accurate types. We demonstrate the power and practicality of the method with examples and performance results from an implementation.

It is shown that systems of set constraints that use all the standard set operations, especially unrestricted union and complement, can be solved. The centerpiece of the development is an algorithm that incrementally transforms a system of constraints while preserving the set of solutions. Eventually, either the system is shown to be inconsistent or all solutions can be exhibited. Most of the work is in proving that if this algorithm does not discover an inconsistency, then the system has a solution. This is done by showing that the system of constraints generated by the algorithm can be transformed into an equivalent set of equations that are guaranteed to have a solution. These equations are essentially tree automata.>

Language designers and implementors have avoided specifying and preserving the meaning of programs that produce errors. This is apparently because being forced to preserve error behavior severely limits the scope of program optimization, even for correct programs. However, preserving error behavior is desirable for debugging, and error behavior must be preserved in any language that permits user-generated exceptions.

This paper treats languages whose operational semantics is given by a set of rewrite rules. For such languages, it is important to be able to determine that there are enough rules to be able to compute the correct meaning of all expressions, but not so many that the system of rules is inconsistent. A formal framework is developed in which to give a precise treatment of these completeness and soundness issues, which are then investigated in the context of an extended version of the functional programming language FP. The rewrite rules of FP are shown to be sound and complete with respect to three different notions of completeness. The latter half of the paper considers rewrite strategies. In order to implement a language based on rewrite rules, it does not suffice to know that there are “enough” rules in the language; a good strategy for determining the order in which to apply them is also needed. But what is “good”? Corresponding to each notion of completeness, there is a notion of a good rewrite strategy. These notions of goodness are examined and characterized, and examples of a number of natural good strategies are given. Although these results are presented in the context of FP, the techniques (some of which are nontrivial extensions of techniques first used in the context of λ-calculus) should apply well beyond the realm of FP rewriting systems.

The designers of (functional) programming languages are faced with two occasionally conflicting goals: programmer convenience and semantic simplicity. For example, it is convenient to treat I/O operations as primitive “functions” with side effects, but doing so destroys referential transparency.FL is a functional language that is designed to trade some of the semantic simplicity of a pure language for some of the convenience of a procedural language, by treating I/O operations as primitives with “side effects”, but by using a structuring technique that localizes the scope of those effects. In this way, surprisingly little of the semantic simplicity is lost, as can be seen by comparing the underlying algebraic laws of FL with those of its pure counterpart. FP.This paper describes that comparison and shows that, in fact, for programs involving I/O, the structures of the algebraic laws of the two languages are identical! It concludes by showing that this technique cannot be extended to allow assignment statements without incurring a massive loss in the expressiveness and simplicity of the underlying algebra.

We consider languages whose operational semantics is given by a set of rewrite rules. For such languages, it is important to be able to determine that there are enough rules to completely reduce all meaningful expressions, but not so many that the system of rules is inconsistent. We develop a formal framework in which to give a precise treatment of these soundness and completeness issues. We believe our approach to be novel in that we make heavy use of denotational semantics in our proof of completeness. The particular language for which we answer these questions is an extended version of the functional programming language FP; however the applicability of these techniques extends beyond the realm of FP rewriting systems.