waashk/acm huggingface dataset:
temporal fds on complex objects  temporal functional dependencies (tfd) are defined for temporal databases that include object identity. it is argued that object identity can overcome certain semantic diffuculties with existing temporal relational data models. practical applications of tfds in object bases are discussed. reasoning about tfds is at the center of this paper. it turns out that the distinction between acyclic and cyclic schemas is significant. for acyclic schemas, a complete axiomatization for finite implication is given and an algorithm for deciding finite implication provided. the same axiomatization is proven complete for unrestricted implication in unrestricted schemas, which can be cyclic. an interesting result is that there are cyclic schemas for which unrestricted and finite implication do not coincide. tfds relate and extend some earlier work on dependency theory in temporal databases. throughout this paper, the construct of tfd is compared with the notion of temporal fd introduced by wang et al. (1997). a comparison with other related work is provided at the end of the article.  jef wijsen
closure maintenance in an object-oriented query model  an object- algebra is presented as a formal query model for object-oriented data models. the algebra serves not only to access and manipulate the structure and behavior of objects, but it also supports the creation of new objects and the introduction of new relationships into the schema. it provides a more powerful and flexible tool than messages for effectively dealing with complex situations and meeting associative access requirements. operands as well as the results of operations in the proposed algebra are formally characterized as a pair of sets---a set of objects capturing the states and a set of message expressions comprised of sequences of messages modeling the object behavior. the closure property is achieved in a natural way by letting the results of operations possess the same characteristics as the operands in an algebra expression. some operators of the algebra resemble those of the relational algebra but with different syntax and semantics. additional operators are introduced to complement them. a class is shown to posses the properties of an operand by defining a set of objects and deriving a set of message expressions for it. furthermore, the result of an object algebra expression is shown to have the characteristics of a class whose superclass/subclass relationships with its operand class(es) can be established providing a mechanism to properly and persistently place it in the class lattice (schema).  reda alhajj faruk polat
pen computing (abstract): the new frontier  while all types of computers are ultimately turing machines, this "reduction- and- abstraction" obscures the way people actually experience computing. about every 10 years, a new type of machine is invented that changes our understanding of computation. from the mysterious glass house mainframes of the 1960s, ministered by white-coated experts, to today's friendly personal computers, our sense of the role of computing in our lives has undergone a dramatic transformation.  the next wave of this evolution is the "pen computer." a small group of early pioneers has quietly redefined how most people will experience computation in the future, and refocused what we will do with this power.  the pen computer derives its heritage from pen and paper, rather than from the typewriter, as personal computers do. it can be carried and used as a folder or notebook would, rather than as a piece of office equipment in a box. these new social characteristics allow a pen computer to be used in settings where keyboard devices are inappropriate or disruptive. data is entered by handwriting, sketching, and scribbling, rather than typing, pointing, and clicking. images are manipulated directly on a visually active surface, rather than remotely. the subjective experience of using a pen computer is unique and utterly personal.  this talk will attempt to present the new face that computing will have for future users.  s. jerrold kaplan
data model issues for object-oriented applications  presented in this paper is the data model for orion, a prototype database system that adds persistence and sharability to objects created and manipulated in object- oriented applications. the orion data model consolidates and modifies a number of major concepts found in many object- oriented systems, such as objects, classes, class lattice, methods, and inheritance. these concepts are reviewed and three major enhancements to the conventional object-oriented data model, namely, schema evolution, composite objects, and versions, are elaborated upon. schema evolution is the ability to dynamically make changes to the class definitions and the structure of the class lattice. composite objects are recursive collections of exclusive components that are treated as units of storage, retrieval, and integrity enforcement. versions are variations of the same object that are related by the history of their derivation. these enhancements are strongly motivated by the data management requirements of the orion applications from the domains of artificial intelligence, computer-aided design and manufacturing, and office information systems with multimedia documents.  jay banerjee hong-tai chou jorge f. garza won kim darrell woelk nat ballou hyoung-joo kim
technique for universal quantification in sql  universal quantification is expressed in ansi sql with negated existential quantification because there is no direct support for universal quantification in ansi sql. however, the lack of explicit support for universal quantification diminishes the userfriendliness of the language because some queries are expressed more naturally using universal quantification than they are using negated existential quantification. it is the intent of this paper to describe a technique to facilitate the construction of universal quantification queries in ansi sql. the technique is based upon a proposed extension to ansi sql to incorporate explicit general support for universal quantification.  claudio fratarcangeli
duplex: a distributed collaborative editing environment in large scale  duplex is a distributed collaborative editor for users connected through a large-scale environment such as the internet. large-scale implies heterogeneity, unpredictable communication delays and failures, and inefficient implementations of techniques traditionally used for collaborative editing in local area networks. to cope with these unfavorable conditions, duplex proposes a model based on splitting the document into independent parts, maintained individually and replicated by a kernel. users act on document parts and interact with co-authors using a local environment providing a safe store and recovery mechanisms against failures or divergence with co-authors. communication is reduced to a minimum, allowing disconnected operation. atomicity, concurrency, and replica control are confined to a manageable small context.  françois pacull alain sandoz andre schiper
user performance with command, menu, and iconic interfaces  performance and subjective reactions of 76 users of varying levels of computer experience were measured with 7 different interfaces representing command, menu, and iconic interface styles. the results suggest three general conclusions:  there are large usability differences between contemporary systems,  there is no necessary tradeoff between ease of use and ease of learning,  interface style is not related to performance or preference (but careful design is).  difficulties involving system feedback, input forms, help systems, and navigation aids occurred in all styles of interface: command, menu, and iconic. new interface technology did not solve old human factors problems.  john whiteside sandra jones paula s. levy dennis wixon
social choice theory and distributed decision making  strategies of distributed decision making based on social choice theory can be used to create a balance between organizational complexity and uncertainty. although group decision support systems (gdss's) have included options for making human collective choices, their design has not been based on optimal rules. social choice theory can also be used to improve the reliability of decisions made by nodes in distributed computer networks. three examples illustrate the application of this theory: human computer-mediated distributed decision making, electing a coordinator to reorganize a failed distributed network, and using weighted votes to improve network reliability.  arnold b. urken
self-spacial join selectivity estimation using fractal concepts  the problem of selectivity estimation for queries of nontraditional databases is still an open issue. in this article, we examine the problem of selectivity estimation for some types of spatial queries in databases containing real data. we have shown earlier [faloutsos and kamel 1994] that real point sets typically have a nonuniform distribution, violating consistently the uniformity and independence assumptions. moreover, we demonstrated that the theory of fractals can help to describe real point sets. in this article we show how the concept of fractal dimension, i.e., (noninteger) dimension, can lead to the solution for the selectivity estimation problem in spatial databases. among the infinite family of fractal dimensions, we consider here the hausdorff fractal dimension d0 and the "correlation" fractal dimension d2. specifically, we show that (a) the average number of neighbors for a given point set follows a power law, with d2 as exponent, and (b) the average number of nonempty range queries follows a power law with e d0 as exponent (e is the dimension of the embedding space). we present the formulas to estimate the selectivity for "biased" range queries, for self-spatial joins, and for the average number of nonempty range queries. the result of some experiments on real and synthetic point sets are shown. our formulas achieve very low relative errors, typically about 10%, versus 40%--100% of the formulas that are based on the uniformity and independence assumptions.  alberto belussi christos faloutsos
a security machanism for statistical database  the problem of user inference in statistical databases is discussed and illustrated with several examples. it is assumed that the database allows "total," "average," "count," and "percentile" queries; a query may refer to any arbitrary subset of the database. methods for protecting the security of such a database are considered; it is shown that any scheme which gives "statistically correct" answers is vulnerable to penetration. a precise definition of compromisability (in a statistical sense) is given. a general model of user inference is proposed; two special cases of this model appear to contain all previously published strategies for compromising a statistical database. a method for protecting the security of such a statistical database against these types of user inference is presented and discussed. it is shown that the number of queries required to compromise the database can be made arbitrarily large by accepting moderate increases in the variance of responses to queries. a numerical example is presented to illustrate the application of the techniques discussed.  leland l. beck
information system behavior specification by high level petri nets  the specification of an information system should include a description of structural system aspects as well as a description of the system behavior. in this article, we show how this can be achieved by high- level petri nets--- namely, the so-called nr/t-nets (nested-relation/transition nets). in nr/t-nets, the structural part is modeled by nested relations, and the behavioral part is modeled by a novel petri net formalism. each place of a net represents a nested relation scheme, and the marking of each place is given as a nested relation of the respective type. insert and delete operations in a nested relational database (nf2-database) are expressed by transitions in a net. these operations may operate not only on whole tuples of a given relation, but also on "subtuples" of existing tuples. the arcs of a net are inscribed with so-called filter tables, which allow (together with an optional logical expression as transition inscription) conditions to be formulated on the specified (sub-) tuples. the occurrence rule for nr/t-net transitions is defined by the operations union, intersection, and "negative" in lattices of nested relations. the structure of an nr/t-net, together with the occurrence rule, defines classes of possible information system procedures, i.e., sequences of (possibly concurrent) operations in an information system.  andreas oberweis peter sander
supporting workspace awareness in groupware (video program) (abstract only)  real-time groupware systems often let each participant control their own view into a shared workspace. however, when collaborators do not share the same view they lose their awareness about where and how others are interacting with the workspace artifacts. we have designed a number of add-on awareness windows that help people regain this awareness. two general strategies and several variations are illustrated in this video that extend work done in a few other groupware systems. first, radar overviews shrink the entire workspace to fit within a single window. awareness is indicated by overlaying the overview with boxes representing others' viewports, by telepointers that show where they are working, and by seeing changes to objects in the workspace as they are made. the workspace can be represented within the radar overview as a scaled miniature, by stylized objects, or by its semantic structure. second, two types of detailed views show some or all of what another person can see, providing awareness of fine-grained details of others' actions.  carl gutwin saul greenberg mark roseman
clearboard: a seamless medium for shared drawing and conversation with eye contact  this paper introduces a novel shared drawing medium called clearboard. it realizes (1) a seamless shared drawing space and (2) eye contact to support realtime and remote collaboration by two users. we devised the key metaphor: "talking through and drawing on a transparent glass window" to design clearboard. a prototype of clearboard is implemented based on the "drafter- mirror" architecture. this paper first reviews previous work on shared drawing support to clarify the design goals. we then examine three methaphors that fulfill these goals. the design requirements and the two possible system architectures of clearboard are described. finally, some findings gained through the experimental use of the prototype, including the feature of "gaze awareness", are discussed.  hiroshi ishii minoru kobayashi
retrospective on a year of participatory design using the pictive technique  pictive is a participatory design technique for increasing the direct and effective involvement of users and other stakeholders in the design of software. this paper reviews a year of the use of pictve on products and research prototypes at bellcore. what we have learned is illustrated through five brief case studies. the paper concludes with a summary of our current pictive practice, expressed as three developing, interrelated models: an object model, a process model, and a participation model.  michael j. muller
using wordnet to disambiguate word senses for text retrieval  this paper describes an automatic indexing procedure that uses the "is-a" relations contained within wordnet and the set of nouns contained in a text to select a sense for each plysemous noun in the text. the result of the indexing procedure is a vector in which some of the terms represent word senses instead of word stems. retrieval experiments comparing the effectivenss of these sense-based vectors vs. stem-based vectors show the stem-based vectors to be superior overall, although the sense-based vectors do improve the performance of some queries. the overall degradation is due in large part to the difficulty of disambiguating senses in short query statements. an analysis of these results suggests two conclusions: the is-a links define a generalization/specialization hierarchy that is not sufficient to reliably select the correct sense of a noun from the set of fine sense distinctions in wordnet; and missing correct matches because of incorrect sense resolution has a much more deleterious effect on retrieval performance than does making spurious matches.  ellen m. voorhees
a chase too far?  in a previous paper we proposed a novel method for generating alternative query plans that uses chasing (and back-chasing) with logical constraints. the method brings together use of indexes, use of materialized views, semantic optimization and join elimination (minimization). each of these techniques is known separately to be beneficial to query optimization. the novelty of our approach is in allowing these techniques to interact systematically, eg. non- trivial use of indexes and materialized views may be enabled only by semantic constraints.  we have implemented our method for a variety of schemas and queries. we examine how far we can push the method in term of complexity of both schemas and queries. we propose a technique for reducing the size of the search space by "stratifying" the sets of constraints used in the (back)chase. the experimental results demonstrate that our method is practical (i.e., feasible _and_ worthwhile).  lucian popa alin deutsch arnaud sahuguet val tannen
on estimating the cardinality of the projection of a database relation  we present an analytical formula for estimating the cardinality of the projection on certain attributes of a subset of a relation in a relational database. this formula takes into account a priori knowledge of the semantics of the real-world objects and relationships that the database is intended to represent. experimental testing of the formula shows that it has an acceptably low percentage error, and that its worst-case error is smaller than the best- known formula. furthermore, the formula presented here has the advantage that it does not require a scan of the relation.  rafiul ahad k. v. bapa dennis mcleod
lh*rs: a high-availability scalable distributed data structure using reed solomon codes  lh*rs is a new high-availability scalable distributed data structure (sdds). the data storage scheme and the search performance of lh*rs are basically these of lh*. lh*rs manages in addition the parity information to tolerate the unavailability of k 1 server sites. the value of k scales with the file, to prevent the reliability decline. the parity calculus uses the reed -solomon codes. the storage and access performance overheads to provide the high- availability are about the smallest possible. the scheme should prove attractive to data-intensive applications.  witold litwin thomas schwarz
why control of the concurrency level in distributed systems is more fundamental than deadlock management  over the past years, stress has been put on global deadlock processing in distributed database management systems. this paper presents the main results of evaluation studies which were intended to provide clues for the choice of a concurrency control mechanism for the scot project. the relationship between deadlock management algorithm and concurrency level is exhibited. their respective influence on system performance is studied in the light of simulations of several concurrency control techniques. a good algorithm for concurrency control is that which controls the concurrency level while solving, as a side effect, the deadlock question.  r. balter p. berard p. decitre
recognition and reasoning in an awareness support system for generation of storyboard-like views of recent activity  awareness support system are based on formal and specific context information such as location, or on video-mediated general context information such asa view into a remote office. we propose a new approach based on fusion of these different kinds of context information. in this approach we distinguish white box context, used by the awareness system for reasoning, and black box context, which can only be interpreted by humans. our approach uses a variety of perception techniques to obtain white box context from audio and video streams. white box context is then used for further processing of context information, for instance to derive additional context. it is further used to generate a storyboard-like multimedia representation of collected and extracted context information. this storyboard provides a condensed view of recent activity to collaboration partners.  datong chen hans-werner gellersen
semantic data modeling of hypermedia associations  many important issues in the design and implementation of hypermedia system functionality focus on the way interobject connections are represented, manipulated, and stored. a prototypic system called hb1 is being designed to meet the storage needs of next-generation hypermedia system architectures. hb1 is referred to as a hyperbase management system (hbms) because it supports, not only the storage and manipulation of information, but the storage and manipulation of the connectivity data that link information together to form hypermedia. among hb1's distinctions is its use of a semantic network database system to manage physical storage. here, basic semantic modeling concepts as they apply to hypermedia systems are reviewed, and experiences using a semantic database system in hb1 are discussed.  semantic data models attempt to provide more powerful mechanisms for structuring objects than are provided by traditional approaches. in hb1, it was necessary to abstract interobject connectivity, behaviors, and information for hypermedia. building on top of a semantic database system facilitated such a separation and made the structural aspects of hypermedia conveniently accessible to manipulation. this becomes particularly important in the implementation of structure-related operations such as structural queries. our experience suggests that an integrated semantic object-oriented database paradigm appears to be superior to purely relational, semantic, or object- oriented methodologies for representing the structurally complex interrelationships that arise in hypermedia.  john l. schnase john j. leggett david l. hicks ron l. szabo
getting some perspective: using process descriptions to index document history  process descriptions are used in workflow and related systems to describe the flow of work and organisational responsibility in business processes, and to aid in coordination. however, the division of a working process into a sequence of steps provides only a partial view of the work involved. in many cases, the performance of individual tasks in a larger process may depend on interpretations and understandings of how other aspects of the work were conducted.  we present an example from an ethnographic investigation of one particular organisation, and introduce a mechanism, which we call "perspectives," for dealing with it. a "perspective" uses the process description to provide an index into the history of a document moving through a process. perspectives allow workflow systems to manage and present information about the execution of specific process instances within the general frame of abstract process descriptions.  paul dourish richard bentley rachel jones allan maclean