In this paper, we propose a procurement mechanism for selecting optimal supplier combination when the suppliers have interoperability and cost dependency issue. The proposed mechanism, named Multi-Component Contingent Auction(MCCA), guarantees that the outcome is the combination of the suppliers with the minimum total cost who can work together. The core of the MCCA is a special form of bid: contingent bid. Contingent bids provide the suppliers with a way to express incompatibility and cost dependency. Suppliers can also implement a package bid by submitting multiple contingent bids. Therefore, the MCCA can be considered as a super set of the combinatorial auction.A major problem in the MCCA is the number of computations required for winner determination. We propose a winner determination algorithm that alleviates this computational burden and compare its performance with the depth-first tree search algorithm.

Online brokers are inventing strategies as fast as they move online.Some strategies are being implemented already, such as the Yahoo!model of advertiser-supported brokerage, or the eBay model supported by commissions charged to sellers, but there is no theoretical backing for either of these two models compared to the wide variety of auction theory.The services offered by brokers are also evolving very rapidly.In this paper we first provide an overview of the evolving brokering practices and limitations of existing work.We then investigate in detail the effect of search costs on the performance of the broker's optimal strategy for the case of M buyers and N sellers where negotiation is on the price attribute of the product or service.The relation to the fees is also analyzed.A time dependent model is constructed and simulation results are reported.

Distributed object standards provide a key to building interoperable applications that can run on a range of platforms. The paper describes a CORBA-based research prototype for an electronic broker in business-to-business electronic commerce. High-level IDL specifications are used to achieve interoperability between components of the electronic marketplace. The two key functionalities of the electronic broker are the ability to dynamically gather information from remote electronic catalogs and the support for negotiations through auction mechanisms. The paper discusses the functionality and the design of the electronic broker and gives an overview of current extensions of the prototype. As application-level interoperability is a crucial precondition for many brokerage services, we put special emphasis on electronic commerce protocol standards.

We propose a novel directory scheme for a large federation of databases where object migration is in response to manufacturing events. In our directory scheme, objects report their location to a directory server instead of the traditional method of the directory servers polling sites in the network. The directory is distributed among multiple servers to avoid bottlenecks during query processing. A distributed linear hashing algorithm is proposed for efficiently determining an appropriate server for an object. Finally, a stochastic dynamic programming model is proposed for minimizing the number of database transactions.

Manufacturing industries have recently started exploring the potential for sharing information across inter-organization database systems to increase productivity and gain strategic advantages. As manufacturing information is not well structured such systems bring together a diverse variety of databases that transcend organizational boundaries to include customers and suppliers. In this paper, we present a framework for object matching that uses rules and approximation schemes to support transparent user access to such heterogeneous databases. In the second part of the paper, we discuss how object matching can be implemented in an extensible DBMS. Several implementation options are described using the features supported by POSTGRES.

Article Free Access Share on Electronic catalogs: a technology overview and survey results Authors: Arie Segev Fisher Center for Information Technology & Management, Haas School of Business, University of California, Berkeley Fisher Center for Information Technology & Management, Haas School of Business, University of California, BerkeleyView Profile , Dadong Wan Fisher Center for Information Technology & Management, Haas School of Business, University of California, Berkeley Fisher Center for Information Technology & Management, Haas School of Business, University of California, BerkeleyView Profile , Caroline Beam Fisher Center for Information Technology & Management, Haas School of Business, University of California, Berkeley Fisher Center for Information Technology & Management, Haas School of Business, University of California, BerkeleyView Profile Authors Info & Claims CIKM '95: Proceedings of the fourth international conference on Information and knowledge managementDecember 1995 Pages 11–18https://doi.org/10.1145/221270.221284Published:02 December 1995Publication History 17citation718DownloadsMetricsTotal Citations17Total Downloads718Last 12 Months26Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We describe a manufacturing environment where, driven by market forces, organizations cooperate as well as compete with one another. We argue that a federated database system (FDBS) is appropriate for such an environment. Contrary to conventional wisdom, complete transparency, assumed desirable and mandatory in distributed database systems, is neither desirable nor feasible in this environment. We propose a new approach that is based on schema coordination rather than integration under which each component database is free to change its data structure, attribute naming, and data semantics. A federated metadata model based on the notion of universal relation is introduced for the FDBS. We also develop the query processing paradigm, and present procedures for query transformation and heterogeneity resolution.>

In intelligent database systems, knowledge directed inference often derives large amounts of data, and the efficiency of query processing in these systems depends upon how the derived data is maintained. This paper focuses on situations where the rule is conditional on a join of multiple data objects (relations) and the rule-derived data are materialized to reduce the overall query processing costs. We develop an indexing technique based on a unique construct called join pattern relation. Several pattern redundancy reduction methods are also introduced to minimize the overhead cost of join indexing.

In applications like financial trading, scheduling, manufacturing and process control, time based predicates in queries and rules are very important. There is also a need to define lists of time points or intervals. The authors refer to these lists as calendars. The authors present a system of calendars that allow specification of natural-language time-based expressions, maintenance of valid time in databases, specification of temporal conditions in database queries and rules, and user-defined semantics for date manipulation. A simple list based language is proposed to define, manipulate and query calendars. The design of the parser and an algorithm for efficient evaluation of calendar expressions is also described. The paper also describes the implementation of time-based rules in POSTGRES using the proposed system of calendars.>

This paper presents a framework for supporting regression in extensible databases. This work is motivated by an actual case study that required probabilistic record matching using regression be supported in a database. We discuss how the regression function can be implemented in a database using rules and functions. We present some indexing and caching ideas for efficient data processing for retrieval-intensive applications. We also describe how the regression coefficients can be incrementally updated by materializing some of the intermediate statistical results. Finally, we illustrate how sampling techniques can be used to generate the data sets for regression and highlight some of the performance issues in this regard.>

Optimal arrangements of cartridges and file partitioning schemes are examined in carousel type mass storage systems using Markov decision theory. It is shown that the Organ-Pipe Arrangement is optimal under different storage configurations for both the anticipatory as well as the non-anticipatory versions of the problem. When requests arrive as per an arbitrary renewal process this arrangement is also shown to minimize the mean queueing delay and the time spent in the system by the requests.

In intelligent database systems, knowledge-directed inference often derives large amounts of & @ and the efficiency of query processing in these systems depends upon how the derived data are maintained, This paper focuses on situations where data-deriving rules are conditional on joins of multiple data objects (or relations) and the derived data are materialized to reduce the overall query processing costs. Join indexing is needed for the efficient maintenance of such rule-derived daa but existing join indexing methods are not suitable for this purpose. We develop a family of join indexing techniques-join pattern indexing-- based on a unique construct called join pattern relation. The performance of the proposed join pattern indexing techniques is evaluated to demonstrate their cost effectiveness. 1.

The primary issues that affect the design of indexing methods are examined, and several structures and algorithms for specific cases are proposed. The append-only tree (AP-tree) structure indexes data for append-only databases to help event-join optimization and queries that can exploit the inherent time ordering of such databases. Two variable indexing for the surrogate and time is discussed. It is shown that a nested index could be a very efficient structure in this context and is preferable to a composite B-tree or an index that involves linear lists of historical tuples. The problems of indexing time intervals, as related to nonsurrogate joint-indexing, are discussed. Several algorithms to partition the time line are introduced. A two-variable AT index based on nested indexing is outlined.>

This paper deals with I/O throughput maximization in a single processor/multidisk database system, by means of optimal allocation of entire relations (or other nonfragmented data objects) to disks. We examine the cases in which such allocation is beneficial, and present a mathematical formulation of the problem. This formulation is shown to be flexible enough to accommodate various objectives and constraints of a typical system design.>

High availabilityof data is clearly a very important goal in a distributed system.Most previous studies have concentrated on the unconstrained maximization of availability, disregarding communications costs.Here we model this problem as one of minimizing commumcations costs subject to availability constraints.Two models for such constrained optimization are presented: The first characterizes availability deterministically, while the second one does so probabilistitally.Other simpler models that are special cases of these two basic models and that arise from making simplifying assumptions such as equal vote values or constant intersite communications costs are also discussed.We describe a semi-exhaustive algorithm and efficient heuristics for solving each model.The algorithms utilize a novel signature-based method for identifying equivalent vote combinations, and an efficient procedure for computing availability.Computational results for the various algorithms are also given.

Intersection join processing in temporal relational databases is investigated. An analysis is presented of the characteristics and processing requirements of three types of intersection join operators: the time-join temporal equijoin on the surrogate, and temporal equijoin on the temporal attribute. Based on the physical organization of the database and on the semantics of the operators, several algorithms were developed to process these joins efficiently. The primary cost variables were identified for each algorithm and their performance is compared to that of a conventional nested-loop join procedure. It is shown that the algorithms developed can reduce processing costs significantly.>

Rule processing strategies in expert database systems which involve rules conditional on join results of base relations are studied. In particular, those rules that require very fast response time in their evaluation are considered. It is proposed to materialize the results of firing a rule in a relation, the rule relation. Performance evaluation of several strategies shows that under the clustered B-trees, strategies using pattern relations perform better than those without pattern relations. The strategy with skinny pattern relations performs poorly in comparison to that with bulky pattern relations. The selective bulky pattern strategy performs better than the bulky pattern strategy. The selective pattern strategy outperforms other strategies in terms of expected total cost. However, it always uses more storage space than the direct materialization.>

In currency-based updates, processing a query to a materialized view has to satisfy a currency constraint which specifies the maximum time lag of the view data with respect to a transaction database. Currency-based update policies are more general than periodical, deferred, and immediate updates; they provide additional opportunities for optimization and allow updating a materialized view from other materialized views. Algorithms for determining the source and timing of view updates and validating the resulting cost savings through simulation results are presented.>

Many algorithms for replicated data concurrency control are based on voting methods. Techniques are developed for optimizing the assignment of votes in an environment where intersite communications costs are nonuniform and individual site reliabilities vary. These techniques apply to all algorithms that are based on voting. Availability is considered as a realistic measure of reliability, and so is incorporated in an optimization model. The optimization model is based on minimizing communications costs subject to a given availability constraint. A semi-exhaustive algorithm is described for solving this model. The algorithm utilizes a signature-based method for identifying equivalent vote combinations and an efficient technique for computing availability. It is compared to an equal vote assignment to estimate the extent of possible savings in communications costs.>

The problem of updating materialized views in distributed database systems is discussed. An architecture and detailed procedures to update a collection of remote views with arbitrary refresh times by using a single differential file are prescribed. The efficiency of the update procedure is enhanced by adopting a multiple-query optimization approach and by introducing a powerful prescreening procedure to eliminate differential tuples. It is shown that even for a single remote view there are many instances where the presented update procedure performs better (with respect to total I/O and communication costs) than existing methods.>

Abstract This article addresses a problem that comes up frequently in network design, and routing. A source is to distribute flows to nodes in the network. Sending flow along an arc involves a fixed cost for using the arc and a variable cost for each ujnit of flow. We show tht the problem of finding a minimum cost collection of arcs along which flows will be directed is an NP‐hard problem. We describe a procedure of solving the problem to optimality and several heuristics. In particular, we conclude that the use of polynomially derived Lagrange multipliers yields good quality solutions and bounds and can be implemented in a distributed processing mode in the network.

The problem of updating materialized views in distributed database systems is discussed. An architecture and detailed procedures for updating a collection of remote views with arbitrary refresh times by using a single differential file are described. The efficiency of the update procedure is enhanced by adopting s multiquery optimization approach and by introducing a powerful prescreening procedure to eliminate differential tuples. It is shown that even for a single remote view, there are many instances where the update procedure performs better (with respect to total I/O and communication costs) than a base table approach.>

The problem of identifying common subexpressions and using them in the simultaneous optimization of multiple queries is dealt with. In particular, emphasis is placed on the strategy of selecting access plans for single queries and their integration into a global access plan that takes advantage of common tasks. A dynamic programming algorithm is presented for the selection of individual access plans such that the resulting global access plan is of minimum processing cost. The computational complexity of this algorithm represents a significant improvement over existing algorithms.>

The problem of multidimensional file partitioning (MDFP) arises in large databases that are subject to frequent range queries on one or more attributes. In an MDFP scheme, the search attribute space is partitioned into cells, which are mapped to physical disk locations. This mapping preserves the order of the search attribute values so that range queries can be answered most efficiently, while maintaining good performance for other types of queries. Recently, MDFP schemes have been suggested to include both dynamic and static file organizations. Optimal and heuristic MDFP algorithms are developed for the static case. The results of extensive computational experiments show that the proposed heuristics perform better than known static ones. It is also shown that incorporating a static algorithm into a dynamic MDFP such as a grid file at conversion and/or periodical reorganization points significantly improves the resulting storage utilization of the data file and decreases the size of the directory file.>

In this paper, we propose a partitioning scheme of files in a temporal database system, and develop algorithms to minimize the overflow associated with that scheme. The proposed partitioning is suitable for range queries and aggregation operations along the time dimension. Simulation results show that the partitioning algorithms proposed in this paper result in better performance than in the case of a grid-type partitioning.

In this paper we examine the semantics and develop constructs for temporal data independent of any traditional data model, such as the relational or network data models. Unlike many other works which extend existing models to support temporal data, our purpose is to characterize the properties of temporal data and operators over them without being influenced by traditional models which were not specifically designed to model temporal data. We develop data constructs that represent sequences of temporal values, identify their semantic properties, and define operations over these structures.

This paper analyses the problem of joining two horizontally partitioned relations in a distributed database system using a semi-join strategy. A mathematical model is developed and the problem is proved to be NP-complete with respect to the number of fragments. Lower bounding and heuristic procedures are proposed, and the results of computational experiments are reported. These results reveal a good performance of the heuristic procedures, and demonstrate the benefit (in terms of communication cost savings) of using semi-join operations to reduce the size of fragments prior to their transmission to the join site.

Abstract The general Node‐Weighted Steiner Tree problem is an extension of the standard Steiner Tree problem by the addition of node‐associated weights. This article analyzes a special case of that problem, where the set of nodes, which must be included in the solution tree, consists of a single node, and all node weights are negative. The special case is shown to be NP‐Complete, its integer programming formulation is presented, and heuristic procedures are proposed. Using Lagrangian relaxation and subgradient optimization, tight lower bounds were derived and utilized by a branch and bound algorithm. The effectiveness of the developed procedures is demonstrated by a set of computational experiments.

This paper addresses the problem of optimizing queries that involve set operations (set queries) in a distributed relational database system. A particular emphasis is put on the optimization of such queries in horizontally partitioned database systems. A mathematical programming model of the set query problem is developed and its NP-completeness is proved. Solution procedures are proposed and computational results presented. One of the main results of the computational experiments is that, for many queries, the solution procedures are not sensitive to errors in estimating the size of results of set operations.

This paper analyzes the problem of joining two horizontally partitioned relations in a distributed database system. Two types of semijoin strategies are introduced, local and remote. Local semijoins are performed at the site of the restricted relation (or fragment), and remote semijoins can be performed at an arbitrary site. A mathematical model of a semijoin strategy for the case of remote semijoins is developed, and lower bounding and heuristic procedures are proposed. The results of computational experiments are reported. The experiments include an analysis of the heuristics' performance relative to the lower bounds, sensitivity analysis, and error analysis. These results reveal a good performance of the heuristic procedures, and demonstrate the benefit of using semijoin operations to reduce the size of fragments prior to their transmission. The algorithms for the case of remote semijoins were found to be superior to the algorithms for the case of local semijoins. In addition, we found that the estimation accuracy of the selectivity factors has a significant effect on the incurred communication cost.