waashk/acm huggingface dataset:
ripple joins for online aggregation  we present a new family of join algorithms, called ripple joins, for online processing of multi-table aggregation queries in a relational database management system (dbms). such queries arise naturally in interactive exploratory decision-support applications.  traditional offline join algorithms are designed to minimize the time to completion of the query. in contrast, ripple joins are designed to minimize the time until an acceptably precise estimate of the query result is available, as measured by the length of a confidence interval. ripple joins are adaptive, adjusting their behavior during processing in accordance with the statistical properties of the data. ripple joins also permit the user to dynamically trade off the two key performance factors of on-line aggregation: the time between successive updates of the running aggregate, and the amount by which the confidence-interval length decreases at each update. we show how ripple joins can be implemented in an existing dbms using iterators, and we give an overview of the methods used to compute confidence intervals and to adaptively optimize the ripple join "aspect-ratio" parameters. in experiments with an initial implementation of our algorithms in the postgres dbms, the time required to produce reasonably precise online estimates was up to two orders of magnitude smaller than the time required for the best offline join algorithms to produce exact answers.  peter j. haas joseph m. hellerstein
an algebraic approach to static analysis of active database rules  rules in active database systems can be very difficult to program due to the unstructured and unpredictable nature of rule processing. we provide static analysis techniques for predicting whether a given rule set is guaranteed to terminate and whether rule execution is confluent (guaranteed to have a unique final state). our methods are based on previous techniques for analyzing rules in active database systems. we improve considerably on the previous techniques by providing analysis criteria that are much less conservative: our methods often determine that a rule set will terminate or is confluent when previous methods could not make this determination. our improved analysis is based on a "propagation" algorithm, which uses an extended relational algebra to accurately determine when the action of one rule can affect the condition of another, and determine when rule actions commute. we consider both conditon- action rules and event- condition-action-rules, making our approach widely applicable to relational active database rule languages and to the trigger language in the sql:1999 standard.  elena baralis jennifer widom
use of mouse buttons  two experimental tasks were designed to test use of multiple-button mice. in the first, number of errors made and time to complete subtasks were measured as subjects attempted to depress one, two, or three buttons under three sets of conditions. in the second, subjects were asked to indicate true or false either by pressing one of two different buttons or by clicking a single button one or two times. people tended to be faster and more accurate using different buttons than different numbers of clicks.  lynne a. price carlos a. cordova
interactive simulation in a multi-person virtual world  a multi-user virtual world has been implemented combining a flexible-object simulator with a multisensory user interface, including hand motion and gestures, speech input and output, sound output, and 3-d stereoscopic graphics with head-motion parallax. the implementation is based on a distributed client/server architecture with a centralized dialogue manager. the simulator is inserted into the virtual world as a server. a discipline for writing interaction dialogues provides a clear conceptual hierarchy and the encapsulation of state. this hierarchy facilitates the creation of alternative interaction scenarios and shared multiuser environment.  christopher codella reza jalili lawrence koved j. bryan lewis daniel t. ling james s. lipscomb david a. rabenhorst chu p. wang alan norton paula sweeney greg turk
flexibility and control for dynamic workflows in the worlds environment  this paper presents a model and prototype implementation, called obligations, for handling flexible, dynamic changes to workflows. the model uses multiple inheritance and an overhead transparency metaphor to construct a network of activities. each 'sheet' holds portions of the network to be constructed. some of these sheets contain local modifications that are not shared among other similar activities and others hold general specifications that all instances should follow, assuming that they have not been locally modified. when all the sheets are stacked together, they create a composite view of the network. individual sheets can be removed and replaced with newer, presumably compatible, sheets that change the network. this type of replacement can be encoded into surrogates which automatically carry out the replacements to keep the obligation up-to-date. the obligation system has a built in error detection scheme that determines if network construction is invalid and, if so, disallows execution of the portions of the network that are in error.  douglas p. bogia simon m. kaplan
peirce: a relational dbms for small systems  peirce is an interactive relational database management system intended for mini and microcomputers, with an extensible command facility, query, based on codd's relational algebra and supporting a clerk oriented interface.  peirce contains three major independent on-line modules: dba, query, and csu.  dba provides the data definition and data dictionary facilities and is discussed in section 2.  query provides both a relational algebra data manipulation language and a clerk oriented interface. query is also discussed in section 2.  command sequences are discussed in section 3.  we discuss the virtual file facilities of peirce (which include the updating of virtual files) in section 4.  the underlying storage structure, namely entry order sequence with secondary indexes, was chosen primarily with simplicity of recovery in mind and is discussed in section 5.  in section 6 we discuss the control commands if and for, which help to conveniently avoid having a host language facility.  we conclude in section 7 by describing further work planned on peirce.  martin k. solomon carl d. kirshen
model management and structured modeling: the role of an information resource dictionary system  models have historically occupied an ambiguous position within organizations. management acceptance of management science and operations research models for decision-making has lagged far behind technical advances in these areas. structured modeling has emerged as a unifying approach to the modeling process with potential to reduce this ambiguity. structured modeling is primarily oriented to the individual, however. a way of incorporating structured modeling into the organizational framework via existing information resource channels is discussed. a relational model is presented for an information resource dictionary system (irds). this irds model is then extended to accommodate representation of structured models. this extension of the irds can answer queries about structured modeling as well as model instances. the concept of an active irds is introduced and an example presented of how an active irds can be linked with an optimization algorithm. the conclusion is that the irds is a suitable vehicle for incorporating model management and structured modeling as part of an organization's information resource management environment.  d. r. dolk
the use of anaphoric resolution for document description in information retrieval  this study investigated two hypotheses concerning the use of anaphors in information retrieval. the first hypothesis, that anaphors tend to refer to integral concepts rather than to peripheral concepts, was well supported. two samples of documents, one in psychology and the other in computer science, were examined by subject experts who judged the centrality of phrases which were referred to anaphorically. the second hypothesis, that various term weighting schemes are affected differently by anaphoric resolution, was also well supported. it was found that schemes which incorporate document length into the calculations produce much smaller increases in term weights for terms occurring in anaphoric resolutions than do those which do not consider document length. it is concluded that although anaphoric resolution has potential for better representing the "aboutness" of a document, care must be taken in choosing both the anaphoric classes to be resolved and the term weighting schemes to be used in measuring a document's topicality.  s. bonzi e. liddy
physical design of a menu relational database system package (abstract only)  this paper outlines the design, implementation, and capabilities of a menu drive transportable relational database package. after identifying the goals of the system, a top down strategy, via data flow diagrams was used to outline the physical design of the package. during the physical design phase, the detail functions and design procedures of the dol, dml, system support, and control routines were identified. the package is written in ansi fortran 66 and implemented on a decsystem-10. since ansi fortran 66 compilers are available for the majority of mini and micro computer systems, this system can be implemented on different systems with a minimum of conversion efforts.  asad khailany arnold gasper
view updates in relational databases with an independent scheme  a view on a database is a mapping that provides a user or application with a suitable way of looking at the data. updates specified on a view have to be translated into updates on the underlying database. we study the view update translation problem for a relational data model in which the base relations may contain (indexed) nulls.  the representative instance is considered to be the correct representation of all data in the database; the class of views that is studied consists of total projections of the representative instance. only independent database schemes are considered, that is, schemes for which global consistency is implied by local consistency. a view update can be an insertion, a deletion, or a modification of a single view tuple.  it is proven that the constant complement method of bancilhon and spyratos is too restrictive to be useful in this context. structural properties of extension joins are derived that are important for understanding views. on the basis of these properties, minimal algorithms for translating a single view- tuple update are given.  rom langerak
workload models for dbms performance evaluation  a hierarchy of workload models to support database management system performance measurement and evaluation studies is defined herein. the hierarchy is structured so that each successive layer represents database design, dbms functionality and workload characterization in progressively greater detail. the design of the hierarchy was influenced by the ansi/x3/sparc (3) model for dbms architecture, by senko's diam (20), by scheuermann's dbms model (19) and by sevcik's layered model for database system performance evaluation (21). the hierarchical layers clearly isolate dbms functionality from organizational activities and underlying machine characteristics.  specific modeling techniques for deriving both database design and workload models at each level of the hierarchy are identified. the database design models form the basis for defining certain critical components of the workload models. the hierarchy of workload models facilitates a clear separation of the relevant performance measurement and evaluation issues and objectives based upon an increasingly detailed view of the total computing environment.  figure 1 illustrates the major layers of the hierarchy. the remainder of this paper defines the workload models developed at each layer and the measurement parameters and performance metrics derived therein.  evans j. adams
incremental and interactive sequence mining  the discovery of frequent sequences in temporal databases is an important data mining problem. most current work assumes that the database is static, and a database update requires rediscovering all the patterns by scanning the entire old and new database. in this paper, we propose novel techniques for maintaining sequences in the presence of a) database updates, and b) user interaction (e.g. modifying mining parameters). this is a very challenging task, since such updates can invalidate existing sequences or introduce new ones. in both the above scenarios, we avoid re-executing the algorithm on the entire dataset, thereby reducing execution time. experimental results confirm that our approach results in execution time improvements of up to several orders of magnitude in practice.  s. parthasarathy m. j. zaki m. ogihara s. dwarkadas
on optimizing an sql-like nested query  sql is a high-level nonprocedural data language which has received wide recognition in relational databases. one of the most interesting features of sql is the nesting of query blocks to an arbitrary depth. an sql-like query nested to an arbitrary depth is shown to be composed of five basic types of nesting. four of them have not been well understood and more work needs to be done to improve their execution efficiency. algorithms are developed that transform queries involving these basic types of nesting into semantically equivalent queries that are amenable to efficient processing by existing query-processing subsystems. these algorithms are then combined into a coherent strategy for processing a general nested query of arbitrary complexity.  won kim
tracing the lineage of view data in a warehousing environment  we consider the view data lineageproblem in a warehousing environment: for a given data item in a materialized warehouse view, we want to identify the set of source data items that produced the view item. we formally define the lineage problem, develop lineage tracing algorithms for relational views with aggregation, and propose mechanisms for performing consistent lineage tracing in a multisource data warehousing environment. our result can form the basis of a tool that allows analysts to browse warehouse data, select view tuples of interest, and then "drill-through" to examine the exact source tuples that produced the view tuples of interest.  yingwei cui jennifer widom janet l. wiener
a homogeneous relational model and query languages for temporal databases  in a temporal database, time values are associated with data item to indicate their periods of validity. we propose a model for temporal databases within the framework of the classical database theory. our model is realized as a temporal parameterization of static relations. we do not impose any restrictions upon the schemes of temporal relations. the classical concepts of normal forms and dependencies are easily extended to our model, allowing a suitable design for a database scheme. we present a relational algebra and a tuple calculus for our model and prove their equivalence. our data model is homogeneous in the sense that the periods of validity of all the attributes in a given tuple of a temporal relation are identical. we discuss how to relax the homogeneity requirement to extend the application domain of our approach.  shashi k. gadia
a computing research repository: why not solve the problems first?  the computing research repository (corr) described by halpern is potentially a powerful tool for researchers in computing science.in its current form, however, shortcomings exist that restrict its value and that,in the long term,might strongly undermine its usefulness.important aspects that have insufficiently been taken care of are (1) the quality and consequently the reliability of the material stored, (2) the still restricted submission of material,which implies that other sources have to be consulted by researchers as well, (3) the still unsound financial basis of the project, and (4) the confusion that may easily arise when a preliminary version is stored in the corr, while a different final version is published in a journal.  a. j. van loon
estimating the relative usability of two interfaces: heuristic, formal, and empirical methods compared  two alternative user interface designs were subjected to user testing to measure user performance in a database query task. user performance was also estimated heuristically in three different ways and by use of formal goms modelling. the estimated values for absolute user performance had very high variability, but estimates of the relative advantage of the fastest interface were less variable. choosing the fastest of the two designs would have a net present value more than 1,000 times the cost of getting the estimates. a software manager would make the correct choice every time in our case study if decisions were based on at least three independent estimates. user testing was 4.9 times as expensive as the cheapest heuristic method but provided better performance estimates.  jakob nielsen victoria l. phillips
a new normal form for nested relations  we consider nested relations whose schemes are structured as trees, called scheme trees, and introduce a normal form for such relations, called the nested normal form. given a set of attributes u, and a set of multivalued dependencies (mvds) m over these attributes, we present an algorithm to obtain a nested normal form decomposition of u with respect to m. such a decomposition has several desirable properties, such as explicitly representing a set of full and embedded mvds implied by m, and being a faithful and nonredundant representation of u. moreover, if the given set of mvds is conflict-free, then the nested normal form decomposition is also dependency-preserving. finally, we show that if m is conflict-free, then the set of root-to-leaf paths of scheme trees in nested normal form decomposition is precisely the unique 4nf decomposition [9, 16] of u with respect to m.  z. meral ozsoyoglu li-yan yuan
majic and desktopmajic conferencing system (video program) (abstract only)  this video shows a multiparty videoconferencing system "majic" and a multiparty desktop conferencing system "desktopmajic". majic is composed of 2 video cameras, 2 video projectors, a one-way transparent screen, and a tilted workstation forming a desk. life-size video images of participants are projected without boundaries onto a large curved screen as if users in remote locations are sitting around a table attending a meeting together. majic supports gaze awareness and multiple eye-contact among the participants. moreover, a shared work space is provided at the center, enabling users to carry on a discussion in a manner comparable to face-to-face meetings.  although majic is very effective, it needs a high speed network and special facilities. desktopmajic is implemented on a convential computer workstation, and supports pseudo gaze awareness and pseudo hand action. still-picture portraits of the user in 9 different gaze directions are sent to every desktopmajic in advance, and an appropriate one is dynamically selected during the conference to reflect where the user is paying attention. moreover, other participants' mouse cursors on the shared application window are linked to their portrait window, allowing each user to intuitively see which cursor belongs to whom. since desktopmajic does not need a high speed network, it may work smoothly even in a telephone or wireless network environment.  ken-ichi okada shunsuke tanaka yutaka matsushita
harp: a distributed query system for legacy public libraries and structured databases  the main purpose of a digital library is to facilitate users easy access to enormous amount of globally networked information. typically, this information includes preexisting public library catalog data, digitized document collections, and other databases. in this article, we describe the distributed query system of a digital library prototype system known as harp. in the harp project, we have designed and implemented a distributed query processor and its query front-end to support integrated queries to preexisting public library catalogs and structured databases. this article describes our experiences in the design of an extended sequel (sql) query language known as harpsql. it also presents the design and implementation of the distributed query system. our experience in distributed query processor and user interface design and development will be highlighted. we believe that our prototyping effort will provide useful lessons to the development of a complete digital library infrastructure.  ee-peng lim ying lu
computer science research in office automation  whether an "office" is situated in academia, business, industry or government, the potential application of computer and communication technologies toward its more effective functioning presents particularly complex and challenging problems to researchers in computer science. it is no longer satisfactory to merely have a separate, supportive computer center configured on a centralized basis with its hardware/software/database constituents designed for and situated in a tightly controlled, remote computer room, accessible only to well-trained staff. instead a modern-day office demands distributed processing and access for potentially all of its employees. it is forcing us to consider the networking of a number of heterogeneous types of computers and terminals with various kinds of nonspecialist users who need or want suitable access from their personal workstations. this precipitates not only "distribution" of hardware, but also systems software, applications software, databases, network control, access security, and more.  indeed, if we define an automated office (or a computer-based office system) to be an organizational/technological entity which encompasses a set of resources (computer hardware, software, databases, communications equipment, people, etc.) working in some specified pattern(s) of interconnection, interdependency or relation toward the accomplishment of one or more organizational objectives, we have quite a job on our hands in terms of applied research which can support the design of such a system. not only must its low-level functioning with respect to its component resources be addressed; attention must also be paid to putting those pieces together into an effectively operating complete system. the latter requires research with a global view and with abilities to conceptualize, model, analyze, synthesize and integrate the various component parts and related considerations toward creating a unified, harmonious whole.  siegfried treu
a use of drawing surfaces in different collaborative settings  two-person design sessions were studied in three different settings: face-to- face, geographically separated with an audio/video link, and a telephone-only connection. in all settings, the designers' uses of a drawing surface were noted. many similar drawing surface activities occurred in all design settings even though the settings did not each allow for the same sharing and interaction with the drawing surfaces. observations suggest that the process of creating drawings may be as important to the design process as the drawings themselves. these preliminary results raise issues for further study, particularly with respect to computer support for collaborative drawing surface use.  sara a. bly