IRList Digest Tuesday, 15 November 1988 Volume 4 : Issue 54 Today's Topics: Abstracts - Dissertations selected by S. Humphrey News addresses are Internet: fox@vtopus.cs.vt.edu BITNET: foxea@vtcc1.bitnet (replaces foxea@vtvax3) ---------------------------------------------------------------------- Date: Tue, 30 Aug 88 13:36:21 EDT From: "Susanne M. HUMPHREY" To: fox%vtopus.cs.vt.edu@RELAY.CS.NET, humphrey@MCS.NLM.NIH.GOV Subject: new set of dissertations for IRList Ed, file ends with line END OF FILE. --Susanne [ AN University Microfilms Order Number ADG88-05223. AU COX, MICHAEL JAMES. IN Polytechnic University Ph.D 1988, 141 pages. TI PERFORMANCE ANALYSIS OF A CONCURRENCY CONTROL ALGORITHM USING PREALLOCATION. DE Computer Science. AB Databases today contain large volumes of information. High speed access devices allow for faster retrieval of that information than was probably ever conceived possible by the first database designers. However, many users wishing to access a given portion of that database at the same time can interfere with each other. Concurrency control algorithms attempt to eliminate this interference. During the last ten years many concurrency control algorithms have been proposed and some have been proven correct. But it is also important to measure their performance. One way to control concurrency is by locking objects. A number of performance studies have been conducted and a survey of them and their relevance to this work is included. However in most cases it is extremely difficult to compare the different studies. Many previous studies point out that locking reduces throughput. An important problem is to quantify this behavior. This study attempts to answer this question through the analysis of a simple algorithm, static locking with predeclared locks. The amount of parallelism that the system can support using this algorithm was also determined. Simulations were performed to confirm the analysis. Using the experience gained from these simulations, a new analytical model was developed. This model is flexible enough to measure performance for varying processor and equipment configurations. This model has the potential to be used in analyzing other concurrency control algorithms, and provide a standard means for comparison. ] [ AN University Microfilms Order Number ADG88-04049. AU HARTUNG, RONALD LEE. IN The Ohio State University Ph.D 1987, 175 pages. TI ADAPT: A GENERIC ICONIC TOOL FOR STRUCTURAL VIEWING OF INFORMATION. DE Computer Science. AB ADAPT is an adaptive browser style user interface for large volumes of information. It was developed as a part of the TRIAD project at The Ohio State University. ADAPT provides an iconic interface to an information base by providing a structural view of relationships and entities. ADAPT is usable on multiple systems and domains, and can access multiple information sources simultaneously. The objective of this interface is to assist the user in a cognitively supportive manner: that is, in a manner akin to methods the user would employ manually. This is achieved by giving the user control over content and context of the displays. A query mechanism is used to form displays interactively under user control as well as to provide predefined displays under the control of the system designer or administrator. This dissertation describes a mathematical model as a specification of ADAPT's operation. The mathematical model is based on an augmented multigraph formalism and operations defined on it. The model is used to show basic completeness of the operations and computational bounds. An architecture for the adaptive display tool is given, and the mapping from an information source in a problem domain to a multigraph representation is illustrated with the TRIAD system. The general precepts used to form mappings for arbitrary domains are described. A justification of the ADAPT design is also provided. This is built on two arguments. First, existing results from cognitive engineering are used as an argument for the nature of the human interface. This uses existing work in the domain of program understanding. Second, the "completeness" of ADAPT is demonstrated by the ability to produce the full range of standard diagrams used in computer system design. Finally, the existing prototype of ADAPT on the TRIAD system is described and critiqued. This was constructed on an IBM 4331 system using GDDM graphics. ] [ AN University Microfilms Order Number ADG88-04708. AU IBRAHIM, MAMDOUH H. IN The University of Utah Ph.D 1987, 148 pages. TI DATABASE LOADING BY EXAMPLES: A LEARNING APPROACH TO LOADING INFORMATION RETRIEVAL DATABASES. DE Computer Science. AB Machine learning from examples has been a growing research area within the artificial intelligence field where its application to real world problems proved to be very successful. This dissertation describes research in the area of learning from examples and its application to the domain of information retrieval systems. The research concentrates on learning concepts presented by the user through examples and the utilization of these concepts to load the document databases. Loading of document databases requires reformatting and identifying of key words, phrases, headers, etc., for indexing. A description language and a set of operators were designed and implemented, as part of the research, to describe the given examples and the concept definitions. The concept descriptions are generated from the user's examples by applying two generalization techniques: incremental generalization (data-driven), and refinement generalization (model-driven). For each given example, the incremental generalization builds an intermediate description which covers the example and all the previously given ones. Heuristic rules control the generation and prune the search for the best intermediate description in the space of all possible descriptions. The refinement generalization forms a Maximally Generalized Description (MGD) of the concept by generalizing the last intermediate description based on the application of appropriate generalization operators. The MGD is then used to generate new examples and present them to the user. The refinement of the MGD depends on the user's responses to the generated examples. A refined MGD that excludes all negative examples of a concept is a complete and consistent description of the concept. Production rules incorporate the final descriptions along with associated functions to be executed when data from the document match the descriptions. A prototype system is implemented as a C program for the IBM-PC to demonstrate the validity of the approach discussed in this dissertation. ] [ AN University Microfilms Order Number ADGD--80802. AU KITINYA, SYLIVANO CHILULI NONGA. IN University of Durham (United Kingdom) Ph.D 1987, 179 pages. TI RELATIONAL MULTIMEDIA DATABASES. DE Computer Science. AB Available from UMI in association with The British Library. Requires signed TDF. This thesis is concerned with the design and implementation of a Relational Multimedia Database System, in short RMDBS. RMDBS is designed to efficiently use storage space and manipulate various kinds of data; attribute data, bit-mapped pictures, and programs in binary code. RMDBS is an integrated system which enables the user to manage and control operations on the different forms of data in a user friendly manner. This means that even non-experienced users can work with the system. The work described in this thesis is novel in that a true multimedia database has been implemented within the framework of a traditional relational DBMS. Previous work in this area has concentrated either in building database management systems for storing picture-based data or multimedia databases which are not true database management systems. RMDBS is implemented using the Revelation database management system. ] [ AN This item is not available from University Microfilms International ADG05-62611. AU LEE, YUK CHEUNG. IN The University of New Brunswick (Canada) Ph.D 1987. TI CONCEPTUAL MODELS FOR GEOGRAPHIC INFORMATION SYSTEMS. DE Computer Science. AB Most geographic information systems (GISs) use the planar graph to model topological relationships. This model is effective for most applications but possesses two major deficiencies. The first deficiency is caused by the flatness of the planar graph, which renders the representation of layered features and phenomona rather difficult. The second deficiency is caused by the limited set of topological elements, namely nodes, arcs, and polygons, supported by a traditional planar graph. This makes the representation of general networks consisting of both arcs and polygons, as in the case of a drainage network, rather awkward. The main objective of this thesis is to extend the planar graph model to accommodate layers and general networks. This results in a set of conceptual models including the simple planar graph model and others with various degrees of vertical inter-relationship. An adaptive data structure is designed to support all the models, and model operators are also implemented. Among the operators are those required to perform model transformations and those for locally updating the topology. ] [ AN University Microfilms Order Number ADGD--80693. AU SADEGHI, RUBIK. IN Dundee College of Technology (United Kingdom) Ph.D 1987, 186 pages. TI A DATABASE QUERY LANGUAGE FOR OPERATIONS ON HISTORICAL DATA. DE Computer Science. AB Available from UMI in association with The British Library. Requires signed TDF. Information in most existing database management systems reflects only the current state of the data. However, many real world applications require the storage of and access to historical information. In this thesis a historical model is presented which integrates comprehensive time processing capabilities into the relational model. The role of time in this model is examined, as is the effect of time on relational algebra. An algebra for historical relations is defined. Finally the Historical Query Language (HQL) is defined and implemented. HQL is designed to allow users to interrogate the historical database in a natural way without referring to the time domain explicitly. HQL has a user friendly syntax and supports user-defined functions and recursion. ] [ AN University Microfilms Order Number ADG88-06703. AU SHAOUT, ADNAN KHALIL. IN Syracuse University Ph.D 1987, 188 pages. TI MATCHING ATTRIBUTED FUZZY TOURNAMENTS AND APPLICATIONS IN PATTERN RECOGNITION. DE Computer Science. AB Graph matching is an important tool in many applications including scene analysis, pattern recognition, image processing, and information retrieval. For example, one way to recognize a given structure in an image is to represent the image by a graph and match it with similar graphs representing the prototype structures using an appropriate distance measure. Attributed Fuzzy Tournaments (AFT's) are a special type of attributed fuzzy graphs which are useful to represent uncertainties inherent to many real-world problems. A distance measure between two AFT's is defined and a new algorithm that finds the matching between two Attributed Fuzzy Transitive Tournaments (AFTT's) is introduced. The matching between two AFTT's is the matching configuration between components of both AFTT's, such that the overall distance measure between two AFTT's possesses the minimum value. Useful applications of the proposed algorithm can be found in pattern matching, where the nodes of an AFT represent the objects in the pattern and the arcs represent the relationships among the objects. Uncertainties of the scene are represented via fuzzy membership values associated with the nodes and arcs. Examples showing the usefulness of the algorithm in pattern matching are shown through handwritten English and Arabic character recognition, scene analysis, scene description, information retrieval, pattern classification, and map updating. ] [ AN University Microfilms Order Number ADGD--80690. AU PATEL, VARSHA. IN Council for National Academic Awards (United Kingdom) Ph.D 1987, 298 pages. TI A FRAMEWORK FOR EVALUATING INFORMATION SYSTEMS DEVELOPMENT METHODOLOGIES. DE Engineering, System Science. AB Available from UMI in association with The British Library. Requires signed TDF. Information Systems can now be developed in a formal and methodical way using an Information Systems Development Methodology (ISM). A number of these have energed over the last fifteen years so that comparisons have been required. Up to now these have been based on selective aspects of the ISM studied. This thesis presents a 'method' for conducting a complete evaluation of an ISM. The evaluation method consists of a step by step evaluation programme (EP) for analysing ISMs. Four known ISMs were assessed using the EP; during their assessment refinements to the EP were discovered and subsequently incorporated into the EP. The four ISMs are: (1) DeMarco's Structured Analysis and System Specification, (2) NCC's ISM, (3) Mumford's Participative Approach and (4) SofTech's Structured Analysis and Design Techniques (SADT). Although SADT and DeMarco's ISM seemed very similar initially, the evaluation programme showed the latter to be much more complete. The EP is based on Wasserman's criteria for an ISM, with some changes. One additional criterion is the nature of the fundamental building blocks of an ISM. This concept is clarified and incorporated in the EP. The research clearly proves that the EP helps to pinpoint gaps in an ISM which are not obvious from other perspectives. The EP also includes the study of the connectivity of the chain of events. This criterion, implicit in DeMarco's methods, was used explicitly in the two case studies. The EP allows the key features of an ISM to be isolated. As shown in the thesis the results of this process, when carried out for many ISMs permits them to be ranked from the viewpoint of each evaluation criterion. The thesis shows that the system life cycle perspective is a good starting point for ISM evaluations. However, evaluations based purely on a life cycle model only highlight an overview. The thesis also suggests how the results from an evaluated ISM may be used for project estimation. ] [ AN University Microfilms Order Number ADG88-03649. AU HSIAO, BRYAN C. IN University of California, Los Angeles Ph.D 1987, 202 pages. TI THE PROCESSING OF QUALITATIVE INFORMATION IN A NATURAL LANGUAGE CONTEXT. DE Information Science. AB Although non-structured decision problems are difficult to handle, human decision makers have been effective in this domain in terms of providing answers to fulfill the decision needs promptly. To embed such a capability in computing systems, various approaches, including Bayesian inference, fuzzy logic and monotonic reasoning, have been proposed to work on the notion of inexactness. All seem persuasive in certain aspects, yet none functions as robust as human decision makers. By taking information in the form of natural language, we compare different perceptions of inexactness (uncertainty, ambiguity and qualitativeness) and suggest that qualitativeness in natural language is an advantage, not a drawback; it should be identified, not modeled, and processed, not resolved. Hence we propose that qualitative lexical items form scales, and these scales can be bundled into a boolean lattice (Q-context). This lattice then is interpreted in Keenan and Faltz's boolean semantic theory to establish a theoretic linguistic connection. Further, to examine the properties of the Q-context, results in other lattice related studies are adopted to check several computational issues. Research in switching theory help us explore the limitations on its representation, Hall's node placement algorithm provides some insights for allocating lexical items within it, and fractal theory allows us to study its recursiveness for the learning potential. The selection of lexical items is triggered and governed by the evolution of inferences in the discourses of a conversation, and executed in boolean operations. The evolution of inferences, called reasoning flow $\Re$, is an automation which consists of inductive, deductive and conductive inferences, along with boolean and nesting operators. Since human decision makers rarely leave problems indecisive, nor backtrack long considerations, the continuous nested reasoning flow in $\Re$ models this fact by accepting qualitative answers to hedge off most of the unknowns. By doing this, the continuity of the thinking process can be maintained, and effectiveness be achieved. In general, the modeling of linguistic scales in a lattice structure suggests a way of handling qualitativeness similar to that of human beings. It captures more of the elusive notion's nature and may help develop more robust information systems. ] [ AN University Microfilms Order Number ADGD--80638. AU MAYHEW, PAMELA JEAN. IN University of East Anglia (United Kingdom) Ph.D 1987, 342 pages. TI AN INVESTIGATION OF INFORMATION SYSTEMS PROTOTYPING. DE Information Science. AB Available from UMI in association with The British Library. Requires signed TDF. This thesis is concerned with the use of prototyping during the development of information systems. Prototyping is a process which involves early practical demonstration of relevant parts of the desired system. This is carried out with a view to improving both the quality and timeliness of the target system. The quality of an information system is largely determined by its adequacy as a tool for human users. Prototyping serves to enhance the communication between developers and users, and through this to increase the suitability of the resulting information system. An investigation into the traditional phase oriented approach to systems development reveals that in certain circumstances it can result in incorrect or at best disappointing systems. The prototyping approach is examined as a possible alternative. Particular attention is paid to its use with respect to typical characteristics of information systems. This is followed by an investigation into all aspects of prototyping. One aspect, that of the construction of prototypes, is dealt with separately and includes an examination of a variety of tools and techniques. Three of these approaches form part of an experiment in building prototypes. Each method is used to build prototypes of the same system. This provides the opportunity to compare approaches in terms of time, cost, and ease of maintenance, with the existing system. Prototyping is used during the development of a genuine system in a commercial environment. Special consideration is given to both the organisation and the control of prototyping. This project is closely monitored and documented in detail. In conclusion, recommendations are made concerning the use of prototyping during information systems development. Further research areas are also highlighted. ] [ AN University Microfilms Order Number ADG88-04184. AU NORMAN, RONALD JULES. IN The University of Arizona Ph.D 1987, 303 pages. TI INTEGRATED DEVELOPMENT ENVIRONMENTS IN SUPPORT OF INFORMATION SYSTEMS DESIGN METHODOLOGIES AND SYSTEMS ANALYSTS' PRODUCTIVITY. DE Information Science. AB Integrated development environment products, called CASE technology by practitioners, are being purchased by enterprises to assist systems analysts with the analysis and design of information systems. This work surveys users of a commercially available CASE product. Ninty-one users from 47 enterprises in the U.S. and Canada responded to the personal computer based survey. This work analyses the perceptions of the respondents in an attempt to determine productivity improvement over manual methods. Using the perceptions of the respondents, the component parts of the CASE product were rank ordered in terms of improved productivity. In addition to this, a psychometric preference scaling method was used to interpret the relatedness of the component parts to each other, again based on the perceptions of the respondents. ]