waashk/acm huggingface dataset:
empirically-based re-design of a hypertext encyclopedia  this paper reports on the processes used and guidelines discovered in re- designing the user interface of the hypertext encyclopedia, hyperholmes. the re-design was based on the outcomes of a previous experiment and was evaluated experimentally. results showed that the new system resulted in superior performance and somewhat different styles of navigation compared to the old system and to paper. the study provides empirical support for design guidelines relating to tiled windows, navigation tools, graphics and hierarchical navigation.  keith instone barbee mynatt teasley laura marie leventhal
exploiting constraint-like data characterizations in query optimization  query optimizers nowadays draw upon many sources of information about the database to optimize queries. they employ runtime statistics in cost-based estimation of query plans. they employ integrity constraints in the query rewrite process. primary and foreign key constraints have long played a role in the optimizer, both for rewrite opportunities and for providing more accurate cost predictions. more recently, other types of integrity constraints are being exploited by optimizers in commercial systems, for which certain semantic query optimization techniques have now been implemented.  these new optimization strategies that exploit constraints hold the promise for good improvement. their weakness, however, is that often the "constraints" that would be useful for optimization for a given database and workload are not explicitly available for the optimizer. data mining tools can find such "constraints" that are true of the database, but then there is the question of how this information can be kept by the database system, and how to make this information available to, and effectively usable by, the optimizer.  we present our work on _soft constraints_ in db2. a soft constraint is a syntactic statement equivalent to an integrity constraint declaration. a soft constraint is not really a constraint, per se, since future updates may undermine it. while a soft constraint is valid, however, it can be used by the optimizer in the same way integrity constraints are. we present two forms of soft constraint: _absolute_ and _statistical_. an absolute soft constraint is consistent with respect to the _current_ state of the database, just in the same way an integrity constraint must be. they can be used in rewrite, as well as in cost estimation. a statistical soft constraint differs in that it may have some degree of violation with respect to the state of the database. thus, statistical soft constraints cannot be used in rewrite, but they can still be used in cost estimation.  we are working long-term on absolute soft constraints. we discuss the issues involved in implementing a facility for absolute soft constraints in a database system (and in db2), and the strategies that we are researching. the current db2 optimizer is more amenable to adding facilities for statistical soft constraints. in the short-term, we have been implementing pathways in the optimizer for statistical soft constraints. we discuss this implementation.  parke godfrey jarek gryz calisto zuzarte
integrity constraints for xml  integrity constraints are useful for semantic specification, query optimization and data integration. the id/idref mechanism provided by xml dtds relics on a simple form of constraint to describe references. yet, this mechanism is not sufficient to express semantic constraints, such as keys or inverse relationships, or stronger, object-style references. in this paper, we investigate integrity constraints for xml, both for semantic purposes and to improve its current reference mechanism. we extend dtds with several families of constraints, including key, foreign key, inverse constraints and constraints specifying the semantics of object identities. these constraints are useful both for native xml documents and to preserve the semantics of data originating in relational or object databases. complexity and axiomatization results are established for the (finite) implication problems associated with these constraints. these results also extend relational dependency theory on the interaction between (primary) keys and foreign keys. in addition, we investigate implication of more general constraints, such as functional, inclusion and inverse constraints defined in terms of navigation paths.  wenfei fan jerome simeon
an extension of the relational data model to incorporate ordered domains we extend the relational data model to incorporate partial orderings into data domains, which we call the ordered relational model. within the extended model, we define the partially ordered relational algebra (the pora) by allowing the ordering predicate &amp;sqsube; to be used in formulae of the selection operator ( ). the pora expresses exactly the set of all possible relations that are invariant under order-preserving automorphism of databases. this result characterizes the expressiveness of the pora and justifies the development of ordered sql (osql) as a query language for ordered databases. osql provides users with the capability of capturing the semantics of ordered data in many advanced applications, such as those having temporal or incomplete information. ordered functional dependencies (ofds) on ordered databases are studied, based on two possible extensions of domain orderings: pointwise ordering and lexicographical ordering. we present a sound and complete axiom system for ofds in the first case and establish a set of sound and complete chase rules for ofds in the second. our results suggest that the implication problems for both cases of ofds are decidable and that the enforcement of ofds in ordered relations are practically feasible. in a wider perspective, the proposed model explores an important area of object- relational databases, since ordered domains can be viewed as a general kind of data type.
on-line documentation for application systems  a critical factor in application development is delivering timely documentation to the end-user. an interactive solution to the development, maintenance, and distribution of application documentation meets this need. a table-driven software package provides control for three levels of user documentation, forming an immediately available description of application systems in an on-line environment. users may select any or all descriptive information for a system. at the detailed level the choice is menu driven.  documentation levels are:  summary/overview--- provides scope and purpose of system.  detailed operating level---lists terminal prompts, examples of appropriate user responses, and explanatory material to guide the user.  news---brief descriptions of any changes which affect the end-user.  designed for ease of maintenance, the modular file structure facilitates addition, replacement, insertion, and deletion of user documentation. the system allows programmer interaction to install user documentation and provides the system librarian with central control. features exist which provide documentation status reports and track usage by end-user, giving the librarian tools to determine the priorities with which systems are addressed. remote high speed printing and terminal display are available for all documentation.  the paper will describe system specifications, design criteria, and give examples of the implementation.  kimberly hourigan carolyn stockdale
lore: a database management system for semistructured data  lore (for lightweight object repository) is a dbms designed specifically for managing semistructured information. implementing lore has required rethinking all aspects of a dbms, including storage management, indexing, query processing and optimization, and user interfaces. this paper provides an overview of these aspects of the lore system, as well as other novel features such as dynamic structural summaries and seamless access to data from external sources.  jason mchugh serge abiteboul roy goldman dallas quass jennifer widom
fine-grained sharing in a page server oodbms  for reasons of simplicity and communication efficiency, a number of existing object-oriented database management systems are based on page server architectures; data pages are their minimum unit of transfer and client caching. despite their efficiency, page servers are often criticized as being too restrictive when it comes to concurrency, as existing systems use pages as the minimum locking unit as well. in this paper we show how to support object- level locking in a page server context. several approaches are described, including an adaptive granularity approach that uses page-level locking for most pages but switches to object-level locking when finer-grained sharing is demanded. we study the performance of these approaches, comparing them to both a pure page server and a pure object server. for the range of workloads that we have examined, our results indicate that a page server is clearly preferable to an object server. moreover, the adaptive page server is shown to provide very good performance, generally outperforming the pure page server, the pure object server, and the other alternatives as well.  michael j. carey michael j. franklin markos zaharioudakis
sap r/3 (tutorial): a database application system  many database applications in the real world are no longer built on top of a stand-alone database system. rather, generic (standard) application systems are employed in which the database system is one integrated component. sap is the market leader for integrated business administration systems, and its sap r/3 product is a comprehensive software system which integrates modules for finance, material management, sales and distribution, etc. from an architectural point of view, sap r/3 is a client/server application system with a relational database system as back-end. sap supports a choice between a variety of commercial relational database products.  alfons kemper donald kossmann florian matthes
optimal and approximate computation of summary statistics for range aggregates  fast estimates for aggregate queries are useful in database query optimization, approximate query answering and online query processing. hence, there has been a lot of focus on "selectivity estimation", that is, computing summary statistics on the underlying data and using that to answer aggregate queries fast and to a reasonable approximation. we present two sets of results for range aggregate queries, which are amongst the most common queries.  first, we focus on a histogram as summary statistics and present algorithms for constructing histograms that are provably optimal (or provably approximate) for range queries; these algorithms take (pseudo-) polynomial time. these are the first known optimality or approximation results for arbitrary range queries; previously known results were optimal only for restricted range queries (such as equality queries, hierarchical or prefix range queries).  second, we focus on wavelet-based representations as summary statistics and present fast algorithms for picking wavelet statistics that are provably optimal for range queries. no previously-known wavelet-based methods have this property.  we perform an experimental study of the various summary representations show the benefits of our algorithms over the known methods.  anna c. gilbert yannis kotidis s. muthukrishnan marin j. strauss
semantics for null extended nested relations  the nested relational model extends the flat relational model by relaxing the first normal form assumption in order to allow the modeling of complex objects. much of the previous work on the nested relational model has concentrated on defining the data structures and query language for the model. the work done on integrity constraints in nested relations has mainly focused on characterizing subclasses of nested relations and defining normal forms for nested relations with certain desirable properties.  in this paper we define the semantics of nested relations, which may contain null values, in terms of integrity constraints, called null extended data dependencies, which extend functional dependencies and join dependencies encountered in flat relational database theory. we formalize incomplete information in nested relations by allowing only one unmarked generic null value, whose semantics we do not further specify. the motivation for the choice of a generic null is our desire to investigate only fundamental semantics which are common to all unmarked null types. this lead us to define a preorder on nested relations, which allows us to measure the relative information content of nested relations. we also define a procedure, called the extended chase procedure, for testing satisfaction of null extended data dependencies and for making inferences by using these null extended data dependencies. the extended chase procedure is shown to generalize the classical chase procedure, which is of major importance in flat relational database theory. as a consequence of our approach we are able to capture the novel notion of losslessness in nested relations, called herein null extended lossless decomposition. finally, we show that the semantics of nested relations are a natural extension of the semantics of flat relations.  mark levene george loizou
a unified environment for fusion of information retrieval approaches  prior work has shown that combining results of various retrieval approaches and query representations can improve search effectiveness. today, many meta- search engines exist which combine the results of various search engines in the hopes of improving overall effectiveness. however, the combination of results from different search engines masks variations in parsers, and other indexing techniques (stemming, stop words, etc.) this makes it difficult to assess the utility of the fusion technique. we have implemented the two most prevalent retrieval strategies: probabilistic and vector space using the same parser and the same relational retrieval engine. first, we identified a model that enables the fusion of an arbitrary number of sources. next, we tested various linear combinations of these two methods as well as various thresholds for identifying retrieved documents. our results show some improvement of effectiveness, but they also provide us for a baseline from which we can continue with other retrieval strategies and test the effect of fusing these strategies.  m. catherine mccabe abdur chowdhury david a. grossman ophir frieder
towards tractable algebras for bags  bags, i.e. sets with duplicates, are often used to implement relations in database systems. in this paper we study the expressive power of algebras for manipulating bags. the algebra we present is a simple extension of the nested relation algebra. our aim is to investigate how the use of bags in the language extends its expressive power, and increases its complexity. we consider two main issues, namely (i) the relationship between the depth of bag nesting and the expressive power, and (ii) the relationship between the algebraic operations, and their complexity and expressive power. we show that the bag algebra is more expressive than the nested relation algebra (at all levels of nesting), and that the difference may be subtle. we establish a hierarchy based on the structure of algebra expressions. this hierarchy is shown to be highly related to the properties of the powerset operator.  stephane grumbach tova milo
heuristic algorithms for distributed query processing  this paper examines heuristic algorithms for processing distributed queries using generalized joins. as this optimization problem is np-hard heuristic algorithms are deemed to be justified. a heuristic algorithm to form/formulate strategies to process queries is presented. it has a special property in that its overhead can be "controlled": the higher its overhead the better the strategies it produces. modeling on a test-bed of queries is used to demonstrate that there is a trade-off between the strategy's execution and formulation delays. the modeling results also support the notion that simple greedy heuristic algorithms such as are proposed by many researchers are sufficient in that they are likely to lead to near-optimal strategies and that increasing the overhead in forming strategies is only marginally beneficial. both the strategy formulation and execution delays are examined in relation to the number of operations specified by the strategy and the total size of partial results.  p. bodorik j. s. riordon
computation-tuple sequences and object histories  a record-based, algebraically-oriented model is introduced for describing data for "object histories" (with computation), such as checking accounts, credit card accounts, taxes, schedules, and so on. the model consists of sequences of computation tuples defined by a computation-tuple sequence scheme (css). the css has three major features (in addition to input data): computation (involving previous computation tuples), "uniform" constraints (whose satisfaction by a computation-tuple sequence u implies satisfaction by every interval of u), and specific sequences with which to start the valid computation-tuple sequences. a special type of css, called "local," is singled out for its relative simplicity in maintaining the validity of a computation- tuple sequence. a necessary and sufficient condition for a css to be equivalent to at least one local css is given. finally, the notion of "local bisimulatability" is introduced for regarding two css as conveying the same information, and two results on local bisimulatability in connection with local css are established.  seymour ginsburg katsumi tanaka
information retrieval using a singular value decomposition model of latent semantic structure  in a new method for automatic indexing and retrieval, implicit higher-order structure in the association of terms with documents is modeled to improve estimates of term-document association, and therefore the detection of relevant documents on the basis of terms found in queries. singular-value decomposition is used to decompose a large term by document matrix into 50 to 150 orthogonal factors from which the original matrix can be approximated by linear combination; both documents and terms are represented as vectors in a 50- to 150- dimensional space. queries are represented as pseudo-documents vectors formed from weighted combinations of terms, and documents are ordered by their similarity to the query. initial tests find this automatic method very promising.  g. w. furnas s. deerwester s. t. dumais t. k. landauer r. a. harshman l. a. streeter k. e. lochbaum
split menus: effectively using selection frequency to organize menus  when some items in a menu are selected more frequently than others, as is often the case, designers or individual users may be able to speed performance and improve preference ratings by placing several high-frequency items at the top of the menu. design guidelines for split menus were developed and applied. split menus were implemented and tested in two in situ usability studies and a controlled experiment. in the usability studies performance times were reduced by 17 to 58% depending on the site and menus. in the controlled experiment split menus were significantly faster than alphabetic menus and yielded significantly higher subjective preferences. a possible resolution to the continuing debate among cognitive theorists about predicting menu selection times is offered. we conjecture and offer evidence that, at least when selecting items from pull- down menus, a logarithmic model applies to familiar (high-frequency) items, and a linear model to unfamiliar (low-frequency) items.  andrew sears ben shneiderman
incremental data structures and algorithms for dynamic query interfaces  dynamic query interfaces (dqis) form a recently developed method of database access that provides continuous realtime feedback to the user during the query formulation process. previous work shows that dqis are elegant and powerful interfaces to small databases. unfortunately, when applied to large databases, previous dqi algorithms slow to a crawl. we present a new approach to dqi algorithms that works well with large databases.  egemen tanin richard beigel ben shneiderman
computational properties of metaquerying problems  metaquerying is a datamining technology by which hidden dependencies among several database relations can be discovered. this tool has already been successfully applied to several real-world applications. recent papers provide only very preliminary results about the complexity of metaquerying. in this paper we define several variants of metaquerying that encompass, as far as we know, all variants defined in the literature. we study both the combined complexity and the data complexity of these variants. we show that, under the combined complexity measure, metaquerying is generally intractable (unless p=np), but we are able to single out some tractable interesting metaquerying cases (whose combined complexity is logcfl-complete). as for the data complexity of metaquerying, we prove that, in general, this is in p, but lies within ac0 in some interesting cases. finally, we discuss the issue of equivalence between metaqueries, which is useful for optimization purposes.  f. angiulli r. ben-eliyahu-zohary l. palopoli g. b. ianni
optimization of queries with user-defined predicates  relational databases provide the ability to store user-defined functions and predicates which can be invoked in sql queries. when evaluation of a user- defined predicate is relatively expensive, the traditional method of evaluating predicates as early as possible is no longer a sound heuristic. there are two previous approaches for optimizing such queries. however, neither is able to guarantee the optimal plan over the desired execution space. we present efficient techniques that are able to guarantee the choice of an optimal plan over the desired execution space. the optimization algorithm with complete rank-ordering improves upon the naive optimization algorithm by exploiting the nature of the cost formulas for join methods and is polynomial in the number of user-defined predicates (for a given number of relations.) we also propose pruning rules that significantly reduce the cost of searching the execution space for both the naive algorithm as well as for the optimization algorithm with complete rank-ordering, without compromising optimality. we also propose a conservative local heuristic that is simpler and has low optimization overhead. although it is not always guaranteed to find the optimal plans, it produces close to optimal plans in most cases. we discuss how, depending on application requirements, to determine the algorithm of choice. it should be emphasized that our optimization algorithms handle user-defined selections as well as user-defined join predicates uniformly. we present complexity analysis and experimental comparison of the algorithms.  surajit chaudhuri kyuseok shim
utilizing first-order logic in query processing  the purpose of this research is to improve on the current membership algorithms and their applications in relational database model and information retrieval. a new technique proposed which makes up for deficiencies existing methods. this membership algorithm based on full first-order logic, extending sagiv's prepositional calculus approach. our technique does not assign one relation name (association) to all database dependencies like the representation of nicolas. finally, it may be used to improve relation schema design. furthermore, we can utilize our technique derive data retrieval programs for answering queries, an idea that has not previously appeared in the literature.  djamshid asgari lawrence henschen