11146897
Constructing Inter-relational Rules for Semantic Query Optimisation
Semantic query optimisation is the process by which a user query is transformed into a set of alternative queries each of which returns the same answer as the original. The most efficient of these alternatives is then selected, for execution, using standard cost estimation techniques. The query transformation process is based on the use of semantic knowledge in the form of rules which are generated either during the query process itself or are constructed according to defined heuristics. Previous research has tended to focus on constructing rules applicable to single relations and does not take advantage of the additional semantic knowledge, inherent in most databases, associated with relational joins. Our paper seeks to address this weakness by showing how the rule derivation process may be extended to the generation of inter-relational rules using an approach based on inductive learning.
955470
Improved Data Retrieval Using Semantic Transformation
Semantic query optimisation uses knowledge about properties of the data, represented as a set of subset descriptor rules, to transform a query into another form that can be executed in a more efficient manner but still yields the same result as the original query. Commonly this ’semantic knowledge’ in the form of rules is generated either during the query process itself or else is constructed in advance according to defined heuristics. Over a period of time the rule set may, therefore, become very large and the number of semantically equivalent queries that may be derived rises exponentially. Each rule use creates a new equivalent query. The problem is to identify one near optimal alternative query in a time that is minimal and also short relative to the overall query execution time. In this paper we propose a method for measuring the effectiveness of each rule and present a fast algorithm which selects the most cost effective transformations to directly yield the optimal alternative query. Experiments carried out on a large publicly available dataset show worthwhile savings using the approach.
2933100
A Statistical Approach to Rule Selection in Semantic Query Optimisation
Semantic Query Optimisation makes use of the semantic knowledge of a database (rules) to perform query transformation. Rules are normally learned from former queries fired by the user. Over time, however, this can result in the rule set becoming very large thereby degrading the efficiency of the system as a whole. Such a problem is known as the utility problem. This paper seeks to provide a solution to the utility problem through the use of statistical techniques in selecting and maintaining an optimal rule set. Statistical methods have, in fact, been used widely in the field of Knowledge Discovery to identify and measure relationships between attributes. Here we extend the approach to Semantic Query Optimisation using the Chi-square statistical method which is integrated into a prototype query optimiser developed by the authors. We also present a new technique for calculating Chi-square, which is faster and more efficient than the traditional method in this situation.
10379830
Extended Query Answering Using Integrity Rules
The conventional use of databases is commonly restricted to the retrieval of factual data in the form of tuples or records. However most databases also contain metadata in the form of integrity rules which can provide a rich source of additional information not normally available to the user. Integrity rules define what data values and relationships may exist within the database and so their interrogation can provide answers as to whether a certain database state is possible. Our paper describes how this may be achieved and specifies a formal approach to implementing such an enquiry system.
52849083
Data extraction from Web data sources
An explanation is given of the basic data structures used in a new page analysis technique to create wrappers (data extractors) for the result pages produced by Web sites in response to user qeries via Web page forms. The key structure called a tpGrid is a representation of the web page, which is easier to analyse than the raw HTML code. The analysis looks for repetition patterns of sets of tagSets, which are defined in the paper.
6242831
Distributing the Derivation and Maintenance of Subset Descriptor Rules
This draft paper describes a solution to the rule maintenance problem for data descriptor rules derived from data that may subsequently change. The method utilises any available computers in the local area network, to derive and maintain rule sets.
5441653
Integrating targeted cycle-time reduction into the capital planning process
This paper describes the development and application of an integrated static capacity and dynamic simulation analysis methodology for purchasing equipment capacity. The goal of the study is to address targeted cycle time objectives in a start up recording head wafer manufacturing facility at Seagate Technology, Minneapolis, MN. The short product cycle time, coupled with the competitive nature of the disc drive industry, has made cycle time reduction one of the most important objectives of production capacity planning. This paper describes an equipment procurement strategy in which static capacity analysis is used to identify an initial equipment set with a low slack capacity variable on each tool group. Simulation analysis is then used to identify the critical tool groups that contribute to cycle time delays. The Seagate Industrial Engineering team used the simulation analysis tool Factory Explorer(R) from Wright, Williams and Kelly to perform the cycle time reduction analysis. This targeted approach is compared to the traditional static capacity planning approach of globally applying reserve capacity buffers of 20% or more to achieve the same cycle time reduction goal. Overall, the targeted approach has proven to be efficient in terms of minimizing capital equipment expenditures and also effective on the factory floor.
6898048
Supporting manufacturing with simulation: model design, development, and deployment
In this paper, we identify and discuss the features we believe are key to the successful use of simulation as a manufacturing support tool. The discussion begins with three sample projects drawn from the authors' industrial and consulting experiences. Using these projects as motivation, we discuss the ideal project lifecycle model design, development, and deployment. For model design, we emphasize the importance of a clear and consistent specification, articulated in a written document. This specification should identify project customers, goals, and deliverables. We next review a range of model development options, stressing the existence of many non-simulation alternatives. We also discuss methods for model verification and validation. Finally, we consider the difficulties of model deployment, including simulation output analysis, data maintenance, and model integration. We close with several suggestions on how best to present simulation results to a management audience.
17448440
Effective implementation of cycle time reduction strategies for semiconductor back-end manufacturing
Using discrete event simulation models, a study was conducted to evaluate the current production practices of a high volume semiconductor back-end operation. The overall goal was to find potential areas for productivity improvement that would collectively yield a 60% reduction in manufacturing cycle time. The paper presents the simulation methodology and findings pertaining to analysis of the Assembly, Burn-In, and Test operations. Many of the recommendations identified can be implemented at no additional cost to the factory. The most significant opportunities for improvement are in the Test area, the system constraint. Additionally, the model is extremely sensitive to changes in operator staffing levels, an accurate reflection of many back-end operations. The model shows that the cumulative impact of these recommendations is a 41% reduction in average cycle time, a significant contribution to the overall goal.
28156050
An Introduction to Hyperarithmetical Functions
6721869
A Performance Study of Deployment Factors in Wireless Mesh Networks
We present a measurement-parameterized performance study of deployment factors in wireless mesh networks using three performance metrics: client coverage area, backhaul tier connectivity, and fair mesh capacity. For each metric, we identify and study topology factors and architectural features which strongly influence mesh performance via an extensive set of Monte Carlo simulations capturing realistic physical layer behavior. Our findings include: (i) A random topology is unsuitable for a large-scale mesh deployment due to doubled node density requirements, yet a moderate level of perturbations from ideal grid placement has a minor impact on performance. (ii) Multiple backhaul radios per mesh node is a cost-effective deployment strategy as it leads to mesh deployments costing 50% less than with a single-radio architecture, (iii) Dividing access and backhaul connections onto two separate radios does not use the second radio efficiently as it only improves fair mesh capacity 40% to 80% for most users. This is in contrast to using the second radio to move half the user population to a new network operated on the second radio. This work adds to the understanding of mesh deployment factors and their general impact on performance, providing further insight into practical mesh deployments.