waashk/acm huggingface dataset:
presentation  presentation is intended to encompass notations and languages for expressing models. this session will focus on the linguistic and notational choices made in particular approaches. emphasis will be placed on common ideas. for example, there have been some assertions from proponents of the predicate calculus that it is a notation that is capable of expressing essentially all the interesting and important concepts that are encountered in other notations. emphasis will also be placed on why the design choices were made, why things are being represented a certain way, and what the effects of those choices were.  the purpose of this workshop is to try to bring us all closer together. trying to bring us to a common terminology is something i don't have much hope for at this point. however, getting us to recognize in other areas problems and solutions we have encountered in our own work is something that i think is very possible, and i think it has happened already to a certain extent. i see that as a goal of this session.
join and semijoin algorithms for a multiprocessor database machine  this paper presents and analyzes algorithms for computing joins and semijoins of relations in a multiprocessor database machine. first, a model of the multiprocessor architecture is described, incorporating parameters defining i/o, cpu, and message transmission times that permit calculation of the execution times of these algorithms. then, three join algorithms are presented and compared. it is shown that, for a given configuration, each algorithm has an application domain defined by the characteristics of the operand and result relations. since a semijoin operator is useful for decreasing i/o and transmission times in a multiprocessor system, we present and compare two equi-semijoin algorithms and one non-equi-semijoin algorithm. the execution times of these algorithms are generally linearly proportional to the size of the operand and result relations, and inversely proportional to the number of processors. we then compare a method which consists of joining two relations to a method whereby one joins their semijoins. finally, it is shown that the latter method, using semijoins, is generally better. the various algorithms presented are implemented in the sabre database system; an evaluation model selects the best algorithm for performing a join according to the results presented here. a first version of the sabre system is currently operational at inria.  patrick valduriez georges gardarin
natural language querying (session overview)  the interface between a user and a software system should match the needs and background of the user. many query languages are built to aid clerks and managers in the performance of their jobs. therefore, a good query language would require no low level programming skills of its users. usually very high level nonprocedural languages are used because they eliminate low level artifacts such as loops. an appealing high level language would be the user's natural language. natural language should require no training or refresher courses for successful use.  unfortunately, natural language interfaces have their own problems. ambiguity is a major problem and can arise in a variety of ways. ambiguous modifiers (e.g., "list the growers of orange trees.") and ambiguous pronoun references ("who was doug flutie's high school coach? also, what are his statistics?") are just two examples. a casual user of the system may also assume a shared background with the system. the doug flutie query assumes the system knows that flutie is a football player and that his (or his coach's) statistics refer to football achievement; not academic, physical or other measures. resolving these and other problems requires an extremely complex and, as yet, unachieved interactive interface.  this complexity can be reduced if we settle for something less than unrestricted natural language. one simplification is to restrict the domain of discourse to the specific database being queried. other possible restrictions would be on the allowable form of a query, vocabulary, pronoun references, etc. many questions arise about restricted natural language query systems. some of the possible questions are:  how do various types of restrictions affect use of a natural language query system?  how can we combine the strengths of restricted natural language, menus and formal language in an integrated query system?  how does a restricted natural language query system perform in the "real world" compared to a formal language query system?  the three papers in this session address themselves to these questions, respectively.  charles welty
database states and their tableaux  recent work considers a database state to satisfy a set of dependencies if there exists a satisfying universal relation whose projections contain each of the relations in the state. such relations are called weak instances for the state. we propose the set of all weak instances for a state as an embodiment of the information represented by the state. we characterize states that have the same set of weak instances by the equivalence of their associated tableaux. we apply this notion to the comparison of database schemes and characterize all pairs of schemes such that for every legal state of one of them there exists an equivalent legal state of the other one. we use this approach to provide a new characterization of boyce-codd normal form relation schemes.  alberto o. mendelzon
distributed database/file systems (session overview): introduction  during the last fifteen years database management has grown so quickly that today it is found on machines of every size from the largest mainframes to the smallest micro computers. almost without exception, the production information systems which use database technology store the data at single site, usually local to the main processor. the reasons for this fact are:  the most expensive component of a computing system has traditionally been the central processing unit. duplicating central processors at multiple sites, until recently, was cost prohibitive.  relatively slow transmission speed and resulting poor performance made distribution infeasible.  algorithms and other techniques for solving the problems in 2 above have been slow in coming.  commercially available software has been slow in reaching the marketplace because of 1, 2 and 3 above.  with the relatively recent advancements in price performance of new machines offered by every vendor, distribution of data to multiple sites is rapidly becoming commonplace. no longer is the cost of the central processing unit an obstacle to distributing the processing associated with distributed databases. the processing power needed for distributed database systems is already in place in most big corporations. micro computers are being used in almost every department for word processing, spreadsheets and other local computational needs. local area networks connecting these micro computers allow rapid access to data stored at different sites.  john c. peck
line operations network growth issues (panel session, abstract only)  the task of keeping customer impact to a minimum while attempting to grow, modernize and improve the network in todays packet switching environment is becoming increasingly more difficult. as the network evolves and the customer demand for higher network availability increases, the need for line operations personnel to reduce customer impact has presented a unique challenge for innovative ideas to accomplish this objective.  although the equipment supplier may provide excellent technical documentation for the provisioning, testing and maintenance of their products, they cannot provide the means to administer, manage and control a large network. this is the sole area where the network provider is responsible for deciding how his network will impact the customer.  this presentation will deal with some of the operational problems encountered in growing a network from 5 nodes to 55 nodes over a period of 9 years. some of the subject areas that will be covered are: the maintenance window - is it required?; administrative documentation; utilization of network statistics; hardware retrofits; and software updates - major and minor. these are but a few of the problem areas challenging packet switching network providers today. their resolution are limited only by the imagination of the personnel charged with the responsibility of resolving them.  g. d. white
integrating pc's into the information center (session overview)  since the concept of the information center was developed at ibm canada in 1976, it has often raised as many questions as it answered. as originally conceived, the information center was to provide training, support, and data access to selected members of the user community so that they could develop idiosyncratic applications or produce new one-time reports. the goal was to reduce the programming load on an under-staffed data processing department by cutting demands for program development.  the wide spread introduction of low-cost, powerful, personal desk-top computers had a tremendous impact on the nature and function of traditional data processing departments. the information center appeared to offer an ideal way to integrate the burgeoning numbers of microcomputers into the more conventional mainframe computer environments of most large business organizations.  this session addresses several of the underlying factors involved in both the theory and practice of information center utilization. the first paper examines the background of the information center concept and the methods in which information centers are actually being used by industrial organizations in the san diego area. the investigation points out that information centers are, in fact, very popular, but there is a diversity of management responses about the best way to use microcomputers within the information center framework. the paper also stresses that the shift in computer power to the user can have profound effects on the role of computer science and information center departments in preparing professionals for their business and scientific careers.  the second paper examines the use of microcomputers in the information center in a different way. it considers the "best" programming language aspect of the problem. the feasibility of using microcomputer-based implementations of prolog within the information center environment is studied. several distinct applications are examined and examples of prolog programs are presented. the paper concludes that prolog is particularly well suited to both business and scientific problems often faced by microcomputer users.  the last paper considers the problem of training the heterogeneous user population that is associated with the typical information center. training must cover the entire spectrum, ranging from computer operations to application programming, to data security. the paper reviews microcomputer- based training packages as well as more traditional training devices.  norman e. sondak
the grid file: an adaptable, symmetric multikey file structure  traditional file structures that provide multikey access to records, for example, inverted files, are extensions of file structures originally designed for single-key access. they manifest various deficiencies in particular for multikey access to highly dynamic files. we study the dynamic aspects of file structures that treat all keys symmetrically, that is, file structures which avoid the distinction between primary and secondary keys. we start from a bitmap approach and treat the problem of file design as one of data compression of a large sparse matrix. this leads to the notions of a grid partition of the search space and of a grid directory, which are the keys to a dynamic file structure called the grid file. this file system adapts gracefully to its contents under insertions and deletions, and thus achieves an upper bound of two disk accesses for single record retrieval; it also handles range queries and partially specified queries efficiently. we discuss in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.  j. nievergelt hans hinterberger kenneth c. sevcik
extreme programming: a discipline of software development (invited paper) (abstract only)  you can look at software development as a system with inputs and outputs. as with any system, software development needs negative feed-back loops to keep it from oscillating. the negative feedback loops traditionally used --- separate testing groups, documentation, lengthy release cycles, reviews --- succeed at keeping certain aspects under control, but they tend to have only long term benefits. what if we could find a set of negative feedback loops that kept software development under control, but that people wanted to do, even under stress, and that contributed to productivity both short and long term?  kent beck
performance evaluation and control of distributed systems (session overview)  distributed systems are modeled with three interesting techniques in the papers of this session. "a task-partitioning problem for a distributed real- time control data processing system," is presented by shi, hu and wang, all of the beijing institute of aeronautics and astronautics. miluzinovic, from purdue, and crnkovic, from the university of miami, are the authors of "state transition times for limited access contention multiple access schemes." "performance evaluation of concurrent systems using timed petri nets" is the subject of zuberek's paper. zuberek is from the university of newfoundland.  four major factors: 1) inteprocessor messages, 2) cpu rate, 3) memory capacity and 4) number of processors, are analyzed by shi, hu and wang. their examination leads to four partitioning principles which, in turn, are used to derive a model of partitioning. while confronting the typical computational intractable problems, the authors present a static algorithm for a good, if not optimal, partitioning.  milutinovic and crnkovic examine limited contention schemes for bus topology local area networks. limited contention schemes attempt to provide the advantages of both contention-based and conflict-free access strategies. simulation results reported support the authors' recommendations for robust binary adaptive access schemes for certain applications.  performance of concurrent systems is modeled by zuberek using μ-timed petri nets and the finite state markov chains isomorphic to such nets. m-timed petri nets are petri nets with firing times are: 1) assigned to transitions and 2) are exponentially distributed random variables. an example application is presented by the author.  stephen nemecek
the john henry syndrome (panel session)(abstract only): humans vs. machines as fpga designers  human designers have done amazing things with fpgas. these designs challenge our assumptions about the speeds and densities acheivable by programmable hardware. but with multi-million gate designs and increasingly complex fpga architectures is there really any place for the hand-crafted design anymore? is there a way that cad tools can incorporate the techniques and knowledge of designers to create high-density, high-performance implementations automatically? or will the tools and architectures always lag the applications, thereby guaranteeing abundant job opportunities for fpga design experts?  herman schmit ray andraka philip friedin satnam singh tim southgate
high level design automation tools (session overview)  as vlsi circuits become more complex, traditional design methods and tools have become inadequate to handle the job of assisting a designer in producing a correct design in a reasonable amount of time. new tools that support top down design techniques must be used. checking the functionality of a large vlsi design is analogous to checking the correctness of a large software design, but other factors, such as testability and manufacturability must also be considered. this session presents some work done in designing tools to support the higher levels of this design process.  first we identify some of the stages in the design of vlsi. the first paper, by agrawal and poon, gives one view of the vlsi design process, with emphasis on the manufacturability of the resulting design. once the functionality of the system has been specified, the architecture of the system is specified as an interconnection of high level blocks described behaviorally. this architectural level design is then refined into a functional level design. a design at the functional level consists of behaviorally defined blocks usually smaller than blocks at the architectural level. examples are memories, registers, alus, etc. (the reader should be warned that there is no generally accepted terminology to describe these refinement levels.) blocks at the functional level are well defined in the sense that they can easily be refined into a design at a lower level, often through use of a library of descriptions of functional level components.  simulation is extremely important in assessing the correctness of a functional level design. the functionality of the simulated circuit can be checked against higher level specifications, and some high level timing analysis can be done. an example of a functional simulator is helix, described by coelho in the second paper.  the next step is gate level design, using either logic gates or gate array macros as primitives. gate level simulation done here offers a more detailed look at the detailed function and timing of the circuit. stick level and detailed timing simulation is done after gate level design. we consider these as well as layout and routing as low level design issues, and beyond the scope of this session.  more and more of the cost of digital product comes from testing, making sure that what is manufactured works according to specification. this is done by applying test vectors to the product. these vectors are evaluated by doing fault simulation of the design.  fault simulation has been traditionally done at the gate level. for complex designs this has become impractical because of memory requirements and extremely long simulation times. the solution to this problem is to do fault simulation at a higher than gate level. however, only gate level fault models have been widely accepted as accurate. simulating some areas of the circuit at the gate level and the rest at the functional level allows detailed fault simulation of regions of interest to be done quickly. the third paper, by rogers and abraham, present a fault simulator that allows this simulation technique.  scott davidson
reverse engineering and system renovation - an annotated bibliography to facilitate research in the field of reverse engineering and system renovation we have compiled an annotated bibliography. we put the contributions not only in alphabetical order but also grouped by topic so that readers focusing on a certain topic can read their annotations in the alphabetical listing. we also compiled an annotated list of pointers to information about reverse engineering and system renovation that can be reached via internet. for the sake of ease we also incorporated a brief introduction to the field of reverse engineering. m. g. j. van den brand p. klint c. verhoef
protein geometry as a function of time  the title of this talk is intentionally obscure since the range of tim e to be discussed is not given. the talk will start with decades (i.e. history). what did a protein look like in the 1940s? what were the methods that provided the "pictures"? what mathematical support was useful? how did the problems of protein structure develop in the ensuing decades?  protein stability - reduce the time scale from decades to days or minutes. what did "denaturation" mean in the 30's through the &amp;ldq; uo;50"s? what does it mean today? what did the molecular biology revolution do to our views of the structure of proteins? a multiple answer question. the genes and their immediate products are linear polymers. the comparison and analysis of simple linear lists of characters has absolutely required the development of new mathematical tools to even get off the starting blocks. data acquisition, data banks, and data analysis are all moving along in high gear. the problems produced by the division of science into smaller and smaller sections each with its own developing vocabulary are increasing exponentially.  today chemical investigations can be carried out at the femtosecond time scale. do we on the biological side really care. most of biology is in the micro to multisecond range or longer, but even macromolecules have important functions in the picosecond region. refinement of x-ray structures is not as good as it should be. where is the problem? nmr like all other spectroscopic procedures has an intrinsic time base. x-ray diffraction is better for static structures, nmr should spend much more of its effort on time specifications where, in principal, it beats the x-ray procedures hands down. cryoelectron microscopy is pushing spatial resolution to lower and lower limits. bridging the gaps between the em and the x-ray/nmr regions in both space and time requires major mathematical help. as solutions to some of these problems appear, the problems are simply made worse  frederic m. richards
domain names (panel session, abstract only): more questions than answers  the darpa domain name project raises several interesting questions about the underlying assumptions and issues involved in providing a hierarchical naming scheme in an environment the size of the internet. for example, the project was motivated by the growth of the internet. however, because the proliferation of hosts took place within the sites belonging to the internet (due in part to an increase in the number of workstations and other small machines), and not necessarily in the number of sites, a less general solution that maintained a centralized and fully distributed site table, with each site running a name server for its hosts, would have been sufficient.  in addition, the distributed implementation of the name to address database uncovered several fundamental naming and addressing issues that had been ignore by the original centralized approach. for example, name servers and resolvers must be able to select a reasonable internet address for hosts connected to the internet at multiple points. the decentralized solution also raises questions about authority over host names.  larry l. peterson