waashk/acm huggingface dataset:
class modification in the gemstone object-oriented dbms  we are currently designing a class modification methodology for gemstone. we describe the current status of the design. we choose from two basic approaches and then introduce those aspects of gemstone necessary for an understanding of the paper. after defining a set of invariants for gemstone databases, we discuss specific class modification operations in terms of maintaining these invariants. we next discuss several issues that impact class modification. these issues include concurrency and authorization, and lead to difficult choices.  d. jason penney jacob stein
a new normal form for the design of relational database schemata  this paper addresses the problem of database schema design in the framework of the relational data model and functional dependencies. it suggests that both third normal form (3nf) and boyce-codd normal form (bcnf) supply an inadequate basis for relational schema design. the main problem with 3nf is that it is too forgiving and does not enforce the separation principle as strictly as it should. on the other hand, bcnf is incompatible with the principle of representation and prone to computational complexity. thus a new normal form, which lies between these two and captures the salient qualities of both is proposed. the new normal form is stricter than 3nf, but it is still compatible with the representation principle. first a simpler definition of 3nf is derived, and the analogy of this new definition to the definition of bcnf is noted. this analogy is used to derive the new normal form. finally, it is proved that bernstein's algorithm for schema design synthesizes schemata that are already in the new normal form.  carlo zaniolo
expressing business rules  point-and-click expression builders, for instance limits and type consistency.  structured english, for more complex restrictions and logical inferences.  entity life history or state transition diagrams, for both basic and more advanced state transition rules.  data model or class model extensions, for basic property rules.  no matter how the rules are captured, there should be a single, unified conceptual representation "inside" of the man-machine boundary. "inside" here means transparent to the specifiers, but visible to analysis tools (e.g., for conflict analysis) and to rule engines or business logic servers (for run-time processing).  inside, there may be still other representations. for processing and performance reasons, there might be many physical representations of the rules, optimized for particular tools or hardware/software environments.  the result is actually three layers of representation: external, conceptual, and internal. this is strongly reminiscent of the old ansi/sparc three-schema architecture for data. this should not be surprising since rules simply build on terms and facts, which can be ultimately represented by data.  where is this research now? a new, more concise representation scheme is under development. one focus of this scheme is a formal expression of how non-atomic rule types are derived from atomic ones. this would allow reduction of rules to a common base of fundamental rule types, in order to support automatic analysis of conflict and overlap in systematic fashion.  this is opening exciting new avenues of research, and significant opportunities for those interested in getting involved.  ronald g. ross
index research (panel session): forest or trees?  indexes and access methods have been a staple of database research --- and indeed of computer science in general --- for decades. a glance at the contents of this year's sigmod and pods proceedings shows another bumper crop of indexing papers.  given the hundreds of indexing papers published in the database literature, a pause for reflection seems in order. from a scientific perspective, it is natural to ask why definitive indexing solutions have eluded us for so many years. what is the grand challenge in indexing? what basic complexities or intricacies underlie this large body of work? what would constitute a successful completion of this research agenda, and what steps will best move us in that direction? or is it the case that the problem space branches in so many ways that we should expect to continuously need to solve variants of the indexing problem?  from the practitioner's perspective, the proliferation of indexing solutions in the literature may be more confusing than helpful. comprehensively evaluating the research to date is a near-impossible task. an evaluation has to include both functionality (applicability to the practitioner's problem, integration with other data management services like buffer management, query processing and transactions) as well as performance for the practitioner's workloads. unfortunately, there are no standard benchmarks for advanced indexing problems, and there has been relatively little work on methodologies for index experimentation and customization. how should the research community promote technology transfer in this area? are the new extensibility interfaces in object-relational dbmss conducive to this effort?  joseph m. hellerstein hans-peter kriegel david comet christos falsutsos raghu ramakrishnan paul brown
the memory extender personal filing system  the benefits of electronic information storage are enormous and largely unrealized. as its cost continues to decline, the number of files in the average user's personal database may increase substantially. how is a user to keep track of several thousand, perhaps several hundred thousand, files? the memory extender (me) system improves the user interface to a personal database by actively modeling the user's own memory for files and for the context in which these files are used. files are multiply indexed through a network of variably weighted term links. context is similarly represented and is used to minimize the user input necessary to disambiguate a file. files are retrieved from the context through a spreading-activation-like process. the system aims towards an ideal in which the computer provides a natural extension to the user's own memory.  w. p. jones
multidatabase interdependencies in industry  in this paper we address the problem of data consistency between interrelated data. in industrial environments, lack of consistent data creates difficulties in interoperation between systems and often requires manual interventions to restart operations that fail due to inconsistent data. we report the results of a study to understand applicability, adequacy and advantages of a framework we had proposed earlier to specify interdatabase dependencies in multidatabase environments. we studied several existing bellcore systems and identified examples of interdependent data. the examples demonstrate that the framework allows precise and detailed specification of complex interdependencies that lead to efficient strategies to enforce the consistency requirements among the corporate data managed in multiple databases. we believe that our specification framework can help in the maintenance of data that meet a business's consistency needs, reduce time consuming and costly manual operations, and provide data of better quality to end users.  amit p. sheth george karabatis
an extension of conflict-free multivalued dependency sets  several researchers (beeri, bernstein, chiu, fagin, goodman, maier, mendelzon, ullman, and yannakakis) have introduced a special class of database schemes, called acyclic or tree schemes. beeri et al. have shown that an acyclic join dependency, naturally defined by an acyclic database scheme, has several desirable properties, and that an acyclic join dependency is equivalent to a conflict-free set of multivalued dependencies. however, since their results are confined to multivalued and join dependencies, it is not clear whether we can handle functional dependencies independently of other dependencies.  in the present paper we define an extension of a conflict-free set, called an extended conflict-free set, including multivalued dependencies and functional dependencies, and show the following two properties of an extended conflict- free set:  there are three equivalent definitions of an extended conflict-free set. one of them is defined as a set including an acyclic joint dependency and a set of functional dependencies such that the left and right sides of each functional dependency are included in one of the attribute sets that construct the acyclic join dependency.  for a relation scheme with an extended conflict-free set, there is a decomposition into third normal form with a lossless join and preservation of dependencies.  hirofumi katsuno
query optimization by simulated annealing  query optimizers of future database management systems are likely to face large access plan spaces in their task. exhaustively searching such access plan spaces is unacceptable. we propose a query optimization algorithm based on simulated annealing, which is a probabilistic hill climbing algorithm. we show the specific formulation of the algorithm for the case of optimizing complex non-recursive queries that arise in the study of linear recursion. the query answer is explicitly represented and manipulated within the closed semiring of linear relational operators. the optimization algorithm is applied to a state space that is constructed from the equivalent algebraic forms of the query answer. a prototype of the simulated annealing algorithm has been built and few experiments have been performed for a limited class of relational operators. our initial experience is that, in general, the algorithm converges to processing strategies that are very close to the optimal. moreover, the traditional processing strategies (e.g., the semi-naive evaluation) have been found to be, in general, suboptimal.  yannis e. ioannidis eugene wong
ensuring relaxed atomicity for flexible transactions in multidatabase systems  global transaction management requires cooperation from local sites to ensure the consistent and reliable execution of global transactions in a distributed database system. in a heterogeneous distributed database (or multidatabase) environment, various local sites make conflicting assertions of autonomy over the execution of global transactions. a flexible transaction model for the specification of global transactions makes it possible to deal robustly with these conflicting requirements. this paper presents an approach that preserves the semi-atomicity (a weaker form of atomicity) of flexible transactions, allowing local sites to autonomously maintain serializability and recoverability. we offer a fundamental characterization of the flexible transaction model and precisely define the semi-atomicity. we investigate the commit dependencies among the subtransactions of a flexible transaction. these dependencies are used to control the commitment order of the subtransactions. we next identify those restrictions that must be placed upon a flexible transaction to ensure the maintenance of its semi-atomicity. as atomicity is a restrictive criterion, semi-atomicity enhances the class of executable global transactions.  aidong zhang marian nodine bharat bhargava omran bukhres
a robust framework for content-based retrieval by spatial similarity in image databases  a framework for retrieving images by spatial similarity (friss) in ima ge databases is presented. in this framework, a robust retrieval by spatial similarity (rss) algorithm is defined as one that incorporates both directional and topological spatial constraints, retrieves similar images, and recognized images even after they undergo translation, scaling, rotation (both perfect and multiple), or any arbitrary combination of transformatioins. the friss framework is discussed and used as a base for comparing various existing rss algorithms. analysis shows that none of them satisfies all the friss specifications. an algorithm, simdtc, is then presented. simdtc introduces the concept of a rotation correction angle(rca) to align objects in one image spatially closer to matching objects in another image for more accurate similarity assessment. similarity between two images is a function of the number of common objects between them and the closeness of directional and topological spatial relationships between object pairs in both images. the simdtc retrieval is invariant under translation, scaling, and perfect rotation, and the algorithm is able to rank multiple rotation variants. the algorithm was tested using synthetic images and the tessa image database. analysis shows the robustness of the simdtc algorithm over current algorithms.  essam a. el-kwae mansur r. kabuka
a normal form for relational databases that is based on domains and keys  a new normal form for relational databases, called domain-key normal form (dk/nf), is defined. also, formal definitions of insertion anomaly and deletion anomaly are presented. it is shown that a schema is in dk/nf if and only if it has no insertion or deletion anomalies. unlike previously defined normal forms, dk/nf is not defined in terms of traditional dependencies (functional, multivalued, or join). instead, it is defined in terms of the more primitive concepts of domain and key, along with the general concept of a "constraint." we also consider how the definitions of traditional normal forms might be modified by taking into consideration, for the first time, the combinatorial consequences of bounded domain sizes. it is shown that after this modification, these traditional normal forms are all implied by dk/nf. in particular, if all domains are infinite, then these traditional normal forms are all implied by dk/nf.  ronald fagin
formal semantics for time in databases  the concept of a historical database is introduced as a tool for modeling the dynamic nature of some part of the real world. just as first-order logic has been shown to be a useful formalism for expressing and understanding the underlying semantics of the relational database model, intensional logic is presented as an analogous formalism for expressing and understanding the temporal semantics involved in a historical database. the various components of the relational model, as extended to include historical relations, are discussed in terms of the model theory for the logic ils, a variation of the logic il formulated by richard montague. the modal concepts of intensional and extensional data constraints and queries are introduced and contrasted. finally, the potential application of these ideas to the problem of natural language database querying is discussed.  james clifford david s. warren
a case study of a multimedia co-working task and the resulting interface design of a collaborative communication tool  the video viewer is a communication tool that allows two users to share video information across a network. the design of this tool was based on the results of a case study involving two multimedia, collaborative workstations situated in two separate rooms. users performed several tasks collaboratively using different media in an unstructured environment (i.e., there were four monitors to increase screen space and there was no specific interface for guidance). this video outlines the case study, the preliminary case study results and how these results effected the interface design of the video viewer.  amanda ropa bengt ahlström
management of interface design in humanoid  today's interface design tools either force designers to handle a tremendous number of design details, or limit their control over design decisions. neither of these approaches taps the true strengths of either human designers or computers in the design process. this paper presents a human-computer collaborative system that uses a model-based approach for interface design to help designers on decision making, and utilizes the bookkeeping capabilities of computers for regular and tedious tasks. we describe (a) the underlying modeling technique and an execution environment that allows even incompletely- specified designs to be executed for evaluation and testing purposes, and (b) a tool that decomposes high-level design goals into the necessary implementation steps, and helps designers manage the myriad of details that arise during design.  ping luo pedro szekely robert neches
parallel query processing in shared disk database systems  system developments and research on parallel query processing have concentrated either on "shared everything" or "shared nothing" architectures so far. while there are several commercial dbms based on the "shared disk" alternative, this architecture has received very little attention with respect to parallel query processing. a comparison between shared disk and shared nothing reveals many potential benefits for shared disk with respect to parallel query processing. in particular, shared disk supports more flexible control over the communication overhead for intra-transaction parallelism, and a higher potential for dynamic load balancing and efficient processing of mixed oltp/query workloads. we also sketch necessary extensions for transaction management (concurrency/coherency control, logging/recovery) to support intra- transaction parallelism in the shared disk environment.  erhard rahm
reasoning about functional dependencies generalized for semantic data models  we propose a more general form of functional dependency for semantic data models that derives from their common feature in which the separate notions of domain and relation in the relational model are combined into a single notion of class. this usually results in a richer terminological component for their query languages, whereby terms may navigate through any number of properties, including none. we prove the richer expressiveness of this more general functional dependency, and exhibit a sound and complete set of inference axioms. although the general problem of decidability of their logical implication remains open at this time, we present decision procedures for cases in which the dependencies included in a schema correspond to keys, or in which the schema itself is acyclic. the theory is then extended to include a form of conjunctive query. of particular significance is that the query becomes an additional source of functional dependency. finally, we outline several applications of the theory to various problems in physical design and in query optimization. the applications derive from an ability to predict when a query can have at most one solution.  grant e. weddell
multiway spatial joins due to the evolution of geographical information systems, large collections of spatial data having various thematic contents are currently available. as a result, the interest of users is not limited to simple spatial selections and joins, but complex query types that implicate numerous spatial inputs become more common. although several algorithms have been proposed for computing the result of pairwise spatial joins, limited work exists on processing and optimization of _multiway spatial joins_. in this article, we review pairwise spatial join algorithms and show how they can be combined for multiple inputs. in addition, we explore the application of _synchronous traversal_ (st), a methodology that processes synchronously all inputs without producing intermediate results. then, we integrate the two approaches in an engine that includes st and pairwise algorithms, using dynamic programming to determine the optimal execution plan. the results show that, in most cases, multiway spatial joins are best processed by combining st with pairwise methods. finally, we study the optimization of very large queries by employing randomized search algorithms. nikos mamoulis dimitris papadias
the relation between problems in large-scale concurrent systems and distributed databases  we first describes the state of the art in models of concurrency. the models are analyzed along two dimensions: communication and computation. the paper then discusses some problems which make it difficult to realize large-scale concurrent systems. such problems include compositionality, heterogeneity, debugging, resource management, and concurrency control. some useful comparisons are drawn to problems in distributed databases and it is argued that solutions to these problems cross disciplinary boundaries. finally, the paper discusses trends in building concurrent computers and provides some expectations for the future.  g. agha
applying an update method to a set of receivers  in the context of object databases, we study the application of an update method to a collection of receivers rather than to a single one. the obvious strategy of applying the update to the receivers one after the other, in some arbitrary order, brings up the problem of order independence. on a very general level, we investigate how update behavior can be analyzed in terms of certain schema annotations, called colorings. we are able to characterize those colorings that always describe order-independedent updates. we also consider a more specific model of update methods implemented in the relational algebra. order-independence of such algebraic methods is undecidable in general, but decidable if the expressions used are positive. finally, we consider an alternative parallel strategy for set-oriented applications of algebraic update methods and compare and relate it to the sequential strategy.
designing a children's digital library with and for children  this paper describes preliminary work carried out to design a children's digital library of stories and poems with and for children aged 11-14 years old. we describe our experience in engaging children as design partners, and propose a digital library environment and design features to provide an engaging, successful learning experience for children using it for collaborative writing.  yin leng theng norliza mohd-nasir harold thimbleby george buchanan matthew jones
the use of data type information in an interactive database environment  despite the enormous advances that have been made in the specification of data types and data models in the fields of programming languages, databases and artificial intelligence; there remain a number of problems in attempting to unify the various approaches to the formal description of data. the purpose of this brief paper is to examine these problems from the point (or points) of view of those people---designers, administrators, applications programmers, and end-users---whose main interest is with databases. in particular, we hope to display special concern for the tools provided for the end-user, who should be the final beneficiary of whatever advances are made.  in order to pin down some of these problems, it is worthwhile to attempt a definition of certain terms used in databases:  1\\. a data model (or database management system if one is describing an implementation) is a set of parameterized or "generic" data types.  2\\. a database schema is a set of data types that result from instantiating the generic types of the data model to produce a set of data types that describe the data to be stored.  3\\. a database is an instantiation of those types defined by a schema.  peter buneman ira winston
a unified approach to indexing and retrieval of information  this paper takes another look at information retrieval. it starts from the purposes of retrieval, looks at what people would like from a retrieval system, builds a conceptual model for how a retrieval system could work and from that determines what and how to do appropriate indexing to fit the model. the approach leads to the idea of the duality of indexing and retrieval. the ideas are illustrated by giving the design of a text based system and of a system to store pictures of faces. it is shown that the underlying mechanisms are the same for both systems and it suggests that other retrieval systems using this approach will have similar structures. other implications of the approach are that retrieval and indexing can be monitored by the machine and the systems can learn to better respond to human needs. ongoing research in this area is outlined.  kevin cox