A model of induction is presented. Knowledge that people use for inductive concept learning is represented explicitly in terms of default schemas. Therefore, concept learning can be viewed as nonmonotonic reasoning in default logic. A computational procedure is also provided as an implementation of the idea presented.>

In distributed DBMSs, one major issue in developing a horizontal fragmentation technique is what criteria to use to guide the fragmentation. The authors propose to use, in addition to typical user queries, particular knowledge about the data itself. Use of this knowledge allows revision of typical user queries into more precise forms. The revised query expressions produce better estimations of user reference clusters to the database than the original query expressions. The estimated user reference clusters form a basis to partition relations horizontally. In the proposed approach, an ordinary many-sorted language is extended to represent the queries and knowledge compatibly. This knowledge is identified in terms of five axiom schemata. An inference procedure is developed to apply the knowledge to the queries deductively.>

An exact solution for the performance analysis of a typical single-bus multiprocessor system is presented. The multiprocessor system is modeled by a Markovian queueing network. An r-stage hypoexponential distribution or an r-stage hyperexponential distribution is used to represent the nonexponential service times. Consequently, the equilibrium probabilities of two-dimensional Markov chains are expressed by simple recurrence relations. Processing efficiency is used as the primary measure of performance. To investigate the effects of different service time distributions on system performance, comparative results are obtained for a large set of input parameters. The numerical results illustrate that processing efficiency attains its maximum value for a constant (deterministic) service time; if service time of common memory is hypoexponentially distributed, then approximating the service time by an exponential distribution produces less than 6% error on the system performance.>

A shared-memory multiprocessor having clusters of processing elements and memory modules is considered. Each cluster has two others as its neighbors. The clusters are interconnected in such a way that the memory modules of a cluster can also be accessed by the processors of the neighboring clusters besides its own processors through its cluster interconnection network. The processors and memories of all clusters are also connected to a shared interconnection network. This permits processors to access memory modules of the non-neighboring clusters. Generalized multistage interconnection networks are used for both types of connections. The time required to access memory modules is reduced by scheduling tasks sharing large data with each other on neighboring clusters or on the same cluster thereby providing for memory access a low latency path through the cluster interconnection network. The time to access memory modules of the non-neighboring clusters also reduces due to reduced contention and because of fewer requests going through the shared interconnection network. Since the memory modules of a cluster are the main memory modules, an additional level of cluster memory is not required. This alleviates the data coherence problem. A Markov chain model is used to study the performance of this multiprocessor under circuit switching. Considerable improvement in performance over a simple shared memory multiprocessor using multistage interconnection network is observed. The model is extended to study the effects of synchronized memory access to shared data.

A key component of a dynamic dataflow processor, the matching unit, has been identified as a major bottleneck. An alternative implementation for the matching unit is presented. This implementation increases the operating bandwidth of the unit by allowing token-matching operations to be done concurrently. The adoption of the proposed implementation also reveals throughput limitations of other units within the processor. As a result, a configuration for a dynamic dataflow processor is proposed that is believed to be cost-effective, to give high performance, and to be capable of incremental performance improvement.>

A methodology is given for modeling a problem and solving it using the A* algorithm. The heuristic used for A* is mechanically generated from the simplified problem, which is derived by relaxing each of the predicate formulas describing the rules and the goal state of the problem. The generated heuristic satisfies the conditions of admissibility and monotonicity. The methodology is applicable for solving general problems. The overall procedure for this methodology is illustrated by four well-known problems, namely, the eight-puzzle problem, the traveling salesman problem, the robot planning problem, and the consistent labeling problem. The values of the heuristics generated by this procedure are compared to the corresponding values of problem-oriented heuristics reported in the literature.>

The authors develop and present a large set of parallel algorithms for implementing the join operation on a shared-memory multiprocessor database machine. The development of these algorithms follows a structured approach. The major steps involved in the processing of the join operation by the machine are first identified. Then, alternative join algorithms are constructed by concatenating the different ways of performing these steps. A study of the performance of the proposed algorithms is presented. This study shows, among other things, that for a given hardware configuration there is not just one overall best performing join algorithm, but rather different algorithms score the best performance, depending on the characteristics of the data participating in the join operation.>

Article Free Access Share on Partitioning a relational database horizontally using a knowledge-based approach Authors: D. G. Shin Computing Research Laboratory, The University of Michigan, Ann Arbor, MI Computing Research Laboratory, The University of Michigan, Ann Arbor, MIView Profile , K. B. Irani Computing Research Laboratory, The University of Michigan, Ann Arbor, MI Computing Research Laboratory, The University of Michigan, Ann Arbor, MIView Profile Authors Info & Claims SIGMOD '85: Proceedings of the 1985 ACM SIGMOD international conference on Management of dataMay 1985 Pages 95–105https://doi.org/10.1145/318898.318906Published:01 May 1985Publication History 3citation300DownloadsMetricsTotal Citations3Total Downloads300Last 12 Months22Last 6 weeks3 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

This paper presents an architectural design for a back-end database machine (DBM) suitable for supporting multiple-user, on-line, very large relational database systems (systems with capacities larger than 1010 bytes). This machine is called the Michigan Relational Database Machine (MIRDM). In designing such a machine a structured approach is followed. First, the DBM's proposed so far are reviewed using a novel classification scheme. Second, this review, the very large relational database system requirements, and the restrictions imposed by the current and near-future state of technology are used to formulate a set of design guidelines. Consequently, an architecture for a cost-effective DBM that meets this set of guidelines is synthesized. Some of the algorithms developed for implementing the primitives of the new machine are also presented. Finally, we highlight some of the important differences between the new DBM and some of the previously proposed ones.

A closed-form solution for the performance analysis of multiple-bus multiprocessor systems is presented. A Markovian queueing network model has been developed to investigate the effects of memory and bus contentions on the system performance. The symmetrical structure of the Markov chains of the queueing model makes it possible to demonstrate that the local balance is satisfied. Consequently, the probabilities of the states of Markov chains can be expressed by simple formulas. Processing efficiency is used as a performance measure. However, this method is easily extendable to other performance measures. To investigate the effects of the system design parameters on the multiprocessor system performance, comparative results have been obtained for a large family of multiprocessor configurations from unibus to bus-sufficient systems.

This paper is concerned with minimizing the delay due to data communication during the execution of a parallel algorithm on an SIMD computer with a two-way circular unit-shift interconnection network. Algorithms are developed which determine, for a given parallel procedure, the order of computation within that procedure, for every parallel arithmetic expression, the alignment of operands for every binary operation, and the mapping and remapping of data into physical memories so that the communication cost is minimized. The proposed algorithms are applicable to array variables with special types of index functions.

In this paper the combined problem of communication network design and file allocation is studied for supercomputer networks. The network topology is restricted to be maximally connected and of minimal diameter in order to enhance network reliability as well as to reduce communication cost and delay.

This paper presents two queueing network models which correspond to different implementations of the lock management algorithm for concurrent transaction processing in a database system. These models are developed to investigate the effects of varying the granularity of locks and the degree of multiprogramming on the performance of a database system. A numerical example is presented for a set of apparently realistic parameters and its results are discussed. In addition to other conclusions, these results also confirm the result of Ries and Stonebraker, using a simulation model [9], that a relatively coarse granularity is sufficient to allow enough parallelism for efficient resource utilization. In contrast with simulation models, the queueing network models presented in this paper allow us to examine more closely the cause-effect relationships of concurrent transaction processing in a database system at less cost.

The production of an appropriate CODASYL Data Base Task Group (DBTG) Data Description Language (DDL) schema for a given data management application is a significant design problem. This research is devoted to the development of a methodology to automate and optimize the design of DBTG schema structures, using analytic modelling and optimization techniques.

Network diagrams are a frequent means of problem description in many technical disciplines.However, problem-oriented graphic systems which use network diagrams as the medium of communication require translators.These accept the information provided in the network diagrams, associate mathematical meaning with the symbols of the diagram, and then transform that meaning into a model of the entire network which is capable of computer solution.A formal framework for these operations, constituting a useful linguistic approach to the translator functions, is offered.The approach is illustrated for Markovian queueing networks.