When selecting alternatives from large amounts of data, trade-offs play a vital role in everyday decision making. In databases this is primarily reflected by the top-k retrieval paradigm. But recently it has been convincingly argued that it is almost impossible for users to provide meaningful scoring functions for top-k retrieval, subsequently leading to the adoption of the skyline paradigm. Here users just specify the relevant attributes in a query and all suboptimal alternatives are filtered following the Pareto semantics. Up to now the intuitive concept of compensation, however, cannot be used in skyline queries, which also contributes to the often unmanageably large result set sizes. In this paper we discuss an innovative and efficient method for computing skylines allowing the use of qualitative trade-offs. Such trade-offs compare examples from the database on a focused subset of attributes. Thus, users can provide information on how much they are willing to sacrifice to gain an improvement in some other attribute(s). Our contribution is the design of the first skyline algorithm allowing for qualitative compensation across attributes. Moreover, we also provide an novel trade-off representation structure to speed up retrieval. Indeed our experiments show efficient performance allowing for focused skyline sets in practical applications. Moreover, we show that the necessary amount of object comparisons can be sped up by an order of magnitude using our indexing techniques.

Skyline queries have received a lot of attention due to their intuitive query formulation. Following the concept of Pareto optimality all dasiabestpsila database items satisfying different aspects of the query are returned to the user. However, this often results in huge result set sizes. In everyday's life users face the same problem. But here, when confronted with a too large variety of choices users tend to focus only on some aspects of the attribute space at a time and try to figure out acceptable compromises between these attributes. Such trade-offs are not reflected by the Pareto paradigm. Incorporating them into user preferences and adjusting skyline results accordingly thus needs special algorithms beyond traditional skylining. In this paper we propose a novel algorithm for efficiently incorporating such typical trade-off information into preference orders. Our experiments on both real world and synthetic data sets show the impact of our techniques: impractical skyline sizes efficiently become manageable with a minimum amount of user interaction. Additionally, we also design a method to elicit especially interesting trade-offs promising a high reduction of skyline sizes. At any point, the user can choose whether to provide individual trade-offs, or accept those suggested by the system. The benefit of incorporating trade-offs into the strict Pareto semantics is clear: result sets become manageable, while additionally getting more focused on the users' information needs.

Skyline queries have recently received a lot of attention due to their intuitive query capabilities. Following the concept of Pareto optimality all dasiabestpsila database objects are returned to the user. However, this often results in unmanageable large result set sizes hampering the success of this innovative paradigm. As an effective remedy for this problem, trade-offs provide a natural concept for dealing with incomparable choices. Such trade-offs, however, are not reflected by the Pareto paradigm. Thus, incorporating them into the userspsila preference orders and adjusting skyline results accordingly needs special algorithms beyond traditional skylining. For the actual integration of trade-offs into skylines, the problem of ensuring the consistency of arbitrary trade-off sets poses a demanding challenge. Consistency is a crucial aspect when dealing with multi-dimensional trade-offs spanning over several attributes. If the consistency should be violated, cyclic preferences may occur in the result set. But such cyclic preferences cannot be resolved by information systems in a sensible way. Often, this problem is circumvented by restricting the trade-offspsila expressiveness, e.g. by altogether ignoring some classes of possibly inconsistent trade-offs. In this paper, we will present a new algorithm capable of efficiently verifying the consistency of any arbitrary set of trade-offs. After motivating its basic concepts and introducing the algorithm itself, we will also show that it exhibits superior average-case performance. The benefits of our approach promise to pave the way towards personalized and cooperative information systems.

Unlike numerical preferences, preferences on attribute values do not show an inherent total order, but skyline computation has to rely on partial orderings explicitly stated by the user. In such orders many object values are incomparable, hence skylines sizes become unpractical. However, the Pareto semantics can be modified to benefit from indifferences: skyline result sizes can be essentially reduced by allowing the user to declare some incomparable values as equally desirable. A major problem of adding such equivalences is that they may result in intransitivity of the aggregated Pareto order and thus efficient query processing is hampered. In this paper we analyze how far the strict Pareto semantics can be relaxed while always retaining transitivity of the induced Pareto aggregation. Extensive practical tests show that skyline sizes can indeed be reduced about two orders of magnitude when using the maximum possible relaxation still guaranteeing the consistency with all user preferences

The vector-space model offers an easy and robust model for Information Retrieval. Thereby, the similarities between queries and documents as well as the similarities between documents themselves are of importance. Document similarities may be used in order to generate links between documents that lead users from one document to related ones. Studies have shown that the vector-space model is robust in the context of OCR-processing if manually constructed queries are used. However it is not clear whether this model, if used for hypertext construction, is robust with regard to data corruption as caused by OCR engines. In this paper, we describe the performance of automatic hypertext construction, based on the vector-space model, with regard to three different measures: the number of overtakings within the used rankings, the accumulated distance of a document's position within the rankings and a comparison based on recall-precision graphs.

Many online databases are available on the Internet, each one with its own access procedures and a special user interface and query language. The Z39.50 protocol standard offers a solution to this situation of diversity and lacking interoperability. However the majority of online databases do not yet support Z39.50. We describe a system that interfaces online bibliographic databases with Z39.50 clients, if the databases are accessible via TELNET and have a line-oriented interface. Our system thus acts as a gateway or middleware. One part of it is a Z39.50 server which can be accessed by every Z39.50 client. The client's requests are translated into commands of the database's query language, which are then sent to the database via TELNET. The results received from the database are analyzed, transformed into the appropriate Z39.50 protocol data units and sent back to the Z39.50 client. The system is highly configurable and can be adapted to the different features and parameters of online bibliographic databases.

We present a coherent modeling and reasoning methodology to extend object-oriented databases towards taxonomic and uncertain integrity constraints. Our so-called TOP database model enriches current ISA-hierarchies by more general tclasses to improve conceptual modeling. The t-classes themselves are then integrated with probabilistic constraints to express uncertainty. We give an efficient algorithm for checking the modeling-consistency of a probabilistic knowledgebase. As a typical application domain for TOP, we exemplify how various aspects of a portfolio management system can be modeled. We also demonstrate that recent probabilistic inference methods, relying on a careful interaction between taxonomic and uncertain knowledge, can be applied in this context. 1 Introduction The evolution of database technology from the relational model into object-oriented databases (OODBs) and deductive databases has been pushed forward to a state where stable and usable systems are becoming widely ...

When looking for detailed pieces of information within the facsimiles of documents, a user has only a highly limited set of supportive tools at his disposal. As a solution to this problem, the use of automatically generated hypertext structures is proposed. These structures also include conventional mechanisms like table of contents, index, or full text search, but extend to the possibility of associative searches. The automatic generation of hypertext structures is based on two sources of information: the output of a commercial OCR system and a document type dependent specification file including the specifications for both structure elements and link types. Thus, additional information hidden in layout and typography is taken into account in addition to the plain ASCII representation of the document. The browsing problems that may arise from a hypertext's nonlinearity do not appear, because the user also has access to the document in its original linear fashion.>

A coherent approach is presented that extends relational and deductive database technology toward an integration of expert-system applications, which require sound and efficient capabilities to deal with uncertainty. Extending logic programming, the authors define the semantics of quantitative deductive databases, where fixpoint theory plays a central role. Calculus gives the rule programmer a great deal of flexibility to tailor the aggregation of certainties according to the application expertise at hand. Extending relational algebra, the authors also introduce a quantitative relational algebra as a suitable target language for rule compilation. This approach makes rule-based expert systems requiring uncertainty reasoning on large and complex data, feasible for a variety of practical application areas.>

Based on matured database technology the paper provides new insights into efficient ways to evaluate recursive deduction rules. We show how the forward-chaining approach to deduction can flexibly be married with goal-directed aspects of best/easiest-first strategies. From the natural fixpoint semantics of recursion we develop generally applicable differential iteration schemes that efficiently compute the fixpoint. Surprisingly the well-known Warshall-algorithm gets disclosed as a descendant of this class of algorithms. Performance measurements suggest the former as well as systolic Δ-algorithms with linear fixpoint equation as candidates for incorporating a transitive closure operator in databases. As a next important step towards integration of database technology and logic programming we suggest to profit from the standard features of concurrency control and transaction management by effectively using them for the synchronization of parallel deductions.