waashk/acm huggingface dataset:
present and future directions in data warehousing many large organizations have developed data warehouses to support decision making. the data in a warehouse are subject oriented, integrated, time variant, and nonvolatile. a data warehouse contains five types of data: current detail data, older detail data, lightly summarized data, highly summarized data, and metadata. the architecture of a data warehouse includes a backend process (the extraction of data from source systems), the warehouse, and the front-end use (the accessing of data from the warehouse). a data mart is a smaller version of a data warehouse that supports the narrower set of requirements of a single business unit. data marts should be developed in an integrated manner in order to avoid repeating the "silos of information" problem.an operational data store is a database for transaction processing systems that uses the data warehouse approach to provide clean data. data warehousing is constantly changing, with the associated opportunities for practice and research, such as the potential for knowledge management using the warehouse. paul gray hugh j. watson
logical design of relational database schemes  we define extended conflict free dependencies in the context of functional and multivalued dependencies, and prove that there exists an acyclic, dependency preserving, 4nf database scheme if and only if the given set of dependencies has an extended conflict free cover. this condition can be checked in polynomial time. a polynomial time algorithm to obtain such a scheme for a given extended conflict free set of dependencies is also presented. the result is also applicable when the data dependencies consists of only functional dependencies, giving the necessary and sufficient condition for an acyclic, dependency preserving bcnf database scheme  l. y. yuan z. m. ozsoyoglu
incremental conceptual clustering from existing databases  conceptual clustering enhances the value of existing databases by revealing patterns in the data. these patterns may be useful for understanding trends, making predictions of future events from historical data, or synthesizing data records into meaningful clusters.  lode (learning on database environments) is an incremental conceptual clustering program. the premise of the lode system is that the task of discovering patterns in a large set of potentially noisy examples can be accomplished in a generate and test paradigm using generalization techniques to generate hypotheses describing similar examples and then testing the accuracy of these hypotheses by comparing them to examples. the lode system is an implementation of this premise.  lode was used to analyze keystroke data collected from novices learning to use the vi editor. the analysis shows that lode discovered descriptions of recurring patterns of errors made by the novices that are known as mode errors.  james r. rowland gregg t. vesonder
dynamic functional dependencies and database aging  a simple extension of the relational model is introduced to study the effects of dynamic constraints on database evolution. both static and dynamic constraints are used in conjunction with the model. the static constraints considered here are functional dependencies (fds). the dynamic constraints involve global updates and are restricted to certain analogs of fds, called "dynamic" fds. the results concern the effect of the dynamic constraints on the static constraints satisfied by the database in the course of time. the effect of the past history of the database on the static constraints is investigated using the notions of age and age closure. the connection between the static constraints and the potential future evolution of the database is briefly discussed using the notions of survivability and survivability closure.  victor vianu
an information retrieval perspective on fuzzy database systems (acm 82 panel session)  database in which domain values are not crisp and precise exhibit properties normally associated with information retrieval systems. for instance, a boolean query induces a membership value for each tuple (i.e., record) that is analogous in function to a similarity measure. thus, precision and recall measures are legitimate areas of interest that pertain to fuzzy databases but not ordinary databases. these ideas will be expounded in the context of a database for expert advice on national energy policies.  bill p. buckles
pointing in entertainment-oriented environments: appreciation versus performance multimedia applications for consumer entertainment often employ a point-and-select interaction style, borrowed from more task-oriented computer applications. the environment of use and the pointing devices involved are so different, however, that a higher importance should be attributed to the users' appreciation of the pointing device than to its efficiency or any other objective performance measure. we set up an experiment to investigate how appreciation and performance measures relate. the experiment involved six different input devices, two cd-i titles and 16 subjects making both voluntary and prescribed cursor control movements. for the mouse-like pointing devices we obtained a fitts' law-like dependence on target width and target distance. this was, however, not replicated for any of the other input devices, mainly owing to a positive influence of cursor constraints. concerning the relation of the performance measures with the users' appreciation, we found that neither time-to-target nor relative-path-length on its own is a reliable indicator of the users' appreciation. together, however, they might explain the appreciation scores to a considerable extent. j. h. d. m. westerink k. van den reek
selectively materializing data in mediators by analyzing source structure, query distribution and maintenance cost  we present an approach to selecting data to materialize in web based information mediators by analyzing multiple factors. an issue in building web based information mediators is how to improve the query response time given the high response time for retrieving data from remote web sources. we had earlier presented a framework for optimizing the performance of information mediators by selectively materializing data. in this paper we describe our approach for automatically selecting the portion of data that must be materialized by analyzing a combination of several factors, namely the distribution of user queries, the structure of sources and the update cost.  naveen ashish craig a. knoblock cyrus shahabi
apl programming: a psychological model  this paper seeks to provide insights into the psychological dynamics of programming in apl. these insights should allow the practitioner to better approach the apl programming environment and may stimulate more in-depth, empirical research into these psychological dynamics. the paper approaches apl both as a language and as a system which maps problems into solutions. the paper is analytical versus empirical in nature. the author draws on the plethora of work related to the topic of the paper in the development of a model of programming in apl.  raymond c. hooker
a simple reference string sampling method  the performance of a process executing in a virtual memory environment is largely determined by the interaction between the process's memory referencing behavior and the system's memory management policies. the structure of the memory reference string, reflected in such quantities as the page fault rate, the stack depth distribution, and the working set size, has traditionally been expensive to measure because of the overhead in capturing every memory reference. this paper reports on the development and testing of a sampling technique designed to extract accurate measurements of reference string characteristics while recording only a part of the complete reference string. the cost of the measurements is controlled by the sampling rate. results in this paper are based on experiments using synthetic reference strings from an lru generative model.  james wittneben dennis kafura
efficient and extensible algorithms for multi query optimization  complex queries are becoming commonplace, with the growing use of decision support systems. these complex queries often have a lot of common sub- expressions, either within a single query, or across multiple such queries run as a batch. multiquery optimization aims at exploiting common sub- expressions to reduce evaluation cost. multi-query optimization has hither-to been viewed as impractical, since earlier algorithms were exhaustive, and explore a doubly exponential search space.  in this paper we demonstrate that multi-query optimization using heuristics is practical, and provides significant benefits. we propose three cost-based heuristic algorithms: volcano-sh and volcano-ru, which are based on simple modifications to the volcano search strategy, and a greedy heuristic. our greedy heuristic incorporates novel optimizations that improve efficiency greatly. our algorithms are designed to be easily added to existing optimizers. we present a performance study comparing the algorithms, using workloads consisting of queries from the tpc-d benchmark. the study shows that our algorithms provide significant benefits over traditional optimization, at a very acceptable overhead in optimization time.  prasan roy s. seshadri s. sudarshan siddhesh bhobe
joyce+: model and language for multi-site distributed systems  the models and languages most widely used for distributed systems programming (such as ada, csp, and occam) do not explicitly consider the process execution site, they assume a synchronous communication scheme of "rendezvous" style, and require that each process recognize the names of their interlocutors. joyce+ is a modification of the joyce language defined by brinch hansen [brinch 87, brinch 89]. in the joyce+ model each process is executed in a specific site, it is assumed that the communication between processes at the same site is much more faster than between processes at different sites, and it is also assumed that the communication between processes is not always reliable. for this multi-site environment an asynchronous communication scheme is considered, eliminating waiting states for a process that sends a message to another process. furthermore, modelling communication between processes through "channel" objects, the spaces for process names become independents.  in this paper the joyce+ model for multi-site distributed systems is presented and the operational semantic of the asynchronous communication between processes is illustrated with petri nets. the syntax of the joyce+ language is presented in terms of the guarded commands language [dijkstra 75]. the expressive power of the joyce+ language in distributed synchronization problems with timeout handling is illustrated through examples. finally, we discuss about software development environments (based on joyce+) for distributed systems over multi- and mono-process computer networks.  index terms \\- languages for distributed systems, tools and methodologies for distributed systems.  maría consuelo franky
an efficient video segmentation scheme for mpeg video stream using macroblock information  in this paper we propose and implement an efficient scheme for automatically detecting the abrupt shot changes in a video stream compressed in mpeg video format. in the proposed scheme, the type of each macroblock in a b-frame is compared with the type of corresponding macroblock (i.e. the macroblock in the same position) of the previous b-frame. the results of comparisons are accumulated and compared to a threshold in order to decide if a shot change occurs. since the proposed scheme uses not only information about the type of each macroblock but also its location, it can provide more robust detection capability. moreover, since the proposed scheme can also detect shot changes in both i- and p-frames based on the information in b-frame, it can detect a changing point more precisely, that is, the granularity of detection is the frame in the proposed scheme.  johngho nang seungwook hong youngin ihm
a new basis for the weak instance model  a new definition of the weak instance model is presented, which does not consider the missing values as existent though unknown, but just assumes that no information is available about them. it is possible to associate with the new definition logical theories that do not contain universally quantified variables. the new model enjoys various desirable properties of the old weak instance model, with respect to dependency satisfaction, query answering, and associated logical theories.  p. atzeni m. c. de bernardis
situated evaluation for cooperative systems  this paper discusses an evaluation of the mead prototype, a multi-user interface generator tool particularly for use in the context of air traffic control (atc). the procedures we adopted took the form of opportunistic and informal evaluation sessions with small user groups, including air traffic controllers (atcos). we argue that informal procedures are a powerful and cost effective method for dealing with specific evaluation issues in the context of cscw but that wider issues are more problematic. most notably, identifying the "validity" or otherwise of cscw systems requires that the context of use be taken seriously, necessitating a fundamental re-appraisal of the concept of evaluation.  michael twidale david randall richard bentley
the psychology of multimedia databases  multimedia information retrieval in digital libraries is a difficult task for computers in general. humans on the other hand are experts in perception, concept representation, knowledge organization and memory retrieval. cognitive psychology and science describe how cognition works in humans, but can offer valuable clues to information retrieval researchers as well. cognitive psychologists view the human mind as a general-purpose ysymbol-processing system that interacts with the world. a multimedia yinformation retrieval system can also be regarded as a symbol-processing system that interacts with the environment. its underlying information retrieval model can be seen as a cognitive framework that describes how the describe the design and implementation of a combined text/image retrieval system (as an example of a multimedia retrieval system) that is inspired by cognitive theories such as paivio's dual coding theory and marr's theory of perception. user interaction and an automatically created thesaurus that maps text concepts and internal image concept representations, generated by various feature extraction algorithms, improve the query formulation process of the image retrieval system. unlike most``multimedia databases'' found in literature, this image retrieval system uses the the functionality provided by an extensible multimedia dbmsthat itself is part of an open distributed environment.  mark g. l. m. van doorn arjen p. de vries
detection, analysis and rendering of audience reactions in distributed multimedia performance  recent advances in distributed multimedia technologies encourage the development of interactive performance systems. these systems allow multiple users to take part in a performance either as players or spectators and influence its development in real time. however, in order for these applications to become effective they have to provide meaningful interaction capabilities and adequate means of expression to all the participants. this research provide an interaction framework that seeks to address these requirements. in particular, the system allows players and spectators to exchange messages during the performance. these messages describe player actions and audience reactions. furthermore, the framework monitors the development of the event and analyzes the behavior of the participants in order to: (i) detect and render shared audience reactions (ii) achieve a high degree of audience engagement. finally, the system synchronizes the presentation of audience reactions with performance developments at each site. this method has been applied in mission, a multi-player game on the web.  nikitas m. sgouros
nfql: the natural forms query language  a means by which ordinary forms can be exploited to provide a basis for nonprocedural specification of information processing is discussed. the natural forms query language (nfql) is defined. in nfql data retrieval requests and computation specifications are formulated by sketching ordinary forms to show what data are desired and update operations are specified by altering data on filled-in forms. the meaning of a form depends on a store of knowledge that includes extended abstract data types for defining elementary data items, a database scheme defined by an entity-relationship model, and a conceptual model of an ordinary form. based on this store of knowledge, several issues are addressed and resolved in the context of nfql. these issues include automatic generation of query expressions from weak specifications, the view update problem, power and completeness, and a heuristic approach to resolving computational relationships. a brief status report of an implementation of nfql is also given.  david w. embley
an optimality proof of the lru-k page replacement algorithm  this paper analyzes a recently published algorithm for page replacement in hierarchical paged memory systems [o'neil et al. 1993]. the algorithm is called the lru-k method, and reduces to the well-known lru (least recently used) method for k = 1. previous work [o'neil et al. 1993; weikum et al. 1994; johnson and shasha 1994] has shown the effectiveness for k > 1 by simulation, especially in the most common case of k = 2. the basic idea in lru-k is to keep track of the times of the last k references to memory pages, and to use this statistical information to rank-order the pages as to their expected future behavior. based on this the page replacement policy decision is made: which memory-resident page to replace when a newly accessed page must be read into memory. in the current paper, we prove, under the assumptions of the independent reference model, that lru-k is optimal. specifically we show: given the times of the (up to) k most recent references to each disk page, no other algorithm a making decisions to keep pages in a memory buffer holding n \\- 1 pages based on this infomation can improve on the expected number of i/os to access pages over the lru-k algorithm using a memory buffer holding n pages. the proof uses the bayesian formula to relate the space of actual page probabilities of the model to the space of observable page numbers on which the replacement decision is acutally made.  elizabeth j. o'neil patrick e. o'neil gerhard weikum
on wrapping query languages and efficient xml integration  modern applications (web portals, digital libraries, etc.) require integrated access to various information sources (from traditional dbms to semistructured web repositories), fast deployment and low maintenance cost in a rapidly evolving environment. because of its flexibility, there is an increasing interest in using xml as a middleware model for such applications. xml enables fast wrapping and declarative integration. however, query processing in xml- based integration systems is still penalized by the lack of an algebra with adequate optimization properties and the difficulty to understand source query capabilities. in this paper, we propose an algebraic approach to support efficient xml query evaluation. we define a general purpose algebra suitable for semistructured on xml query languages. we show how this algebra can be used, with appropriate type information, to also wrap more structured query languages such as oql or sql. finally, we develop new optimization techniques for xml-based integration systems.  vassilis christophides sophie cluet jerome simeon
a magnifier tool for video data  we describe an interface prototype, the hierarchical video magnifier, which allows users to work with a video source at fine-levels of detail while maintaining an awareness of temporal context. the technique allows the user to recursively magnify the temporal resolution of a video source while preserving the levels of magnification in a spatial hierarchy. we discuss how the ability to inspect and manipulate hierarchical views of temporal magnification affords a powerful tool for navigating, analyzing and editing video streams.  michael mills jonathan cohen yin yin wong
join processing in database systems with large main memories  we study algorithms for computing the equijoin of two relations in a system with a standard architecture hut with large amounts of main memory. our algorithms are especially efficient when the main memory available is a significant fraction of the size of one of the relations to he joined; but they can be applied whenever there is memory equal to approximately the square root of the size of one relation. we present a new algorithm which is a hybrid of two hash-based algorithms and which dominates the other algorithms we present, including sort-merge. even in a virtual memory environment, the hybrid algorithm dominates all the others we study.  finally, we describe how three popular tools to increase the efficiency of joins, namely filters, babb arrays, and semijoins, can he grafted onto any of our algorithms.  leonard d. shapiro
introducing groupware into organizations (workshop session)(abstract only): what leads to successes and failures?  this full-day workshop is intended for designers, researchers, and decision- makers to discuss and compare their experiences with designing and introducing groupware in an organizational context. considering the impact that groupware has had on collaboration in recent years, there are relatively few published studies on experiences with introducing groupware. with so few comparisons, it is difficult to develop and appropriate framework which could guide its introduction. yet it is important not only to understand successes and failiures with methods, but also design and methodology compromises that groupware implementers must live with.  workshop participants shall present and discuss their experinces with requirement anlalysis, design and realization, training, user support/mediation, roles in the design team, and user acceptance. one goal of the workshop is to identify commonalities between different methods associated with successes and problems in order to move in the direction of developing approaches that will benefit users in system adaptation. an important issue here will be to view the introduction of groupware as an integrated organizational and technological development, i.e., a design of technology, work, and organizations.  gloria mark wolfgang prinz volker wulf vidar hepsoe
enabling dynamic content caching for database-driven web sites  web performance is a key differentiation among content providers. snafus and slowdowns at major web sites demonstrate the difficulty that companies face trying to scale to a large amount of web traffic. one solution to this problem is to store web content at server-side and edge-caches for fast delivery to the end users. however, for many e-commerce sites, web pages are created dynamically based on the current state of business processes, represented in application servers and _databases_. since application servers, databases, web servers, and caches are independent components, there is no efficient mechanism to make changes in the database content reflected to the cached web pages. as a result, most application servers have to mark dynamically generated web pages as non-cacheable. in this paper, we describe the architectural framework of the cacheportal system for enabling dynamic content caching for database-driven e-commerce sites. we describe techniques for intelligently invalidating dynamically generated web pages in the caches, thereby enabling _caching_ of web pages generated based on database contents. we use some of the most popular components in the industry to illustrate the deployment and applicability of the proposed architecture.  k. selçuk candan wen-syan li qiong luo wang-pin hsiung divyakant agrawal