%%% -*-BibTeX-*- %%% ==================================================================== %%% BibTeX-file{ %%% author = "Nelson H. F. Beebe", %%% version = "1.19", %%% date = "10 July 2008", %%% time = "10:20:24 MDT", %%% filename = "vldbj.bib", %%% address = "University of Utah %%% Department of Mathematics, 110 LCB %%% 155 S 1400 E RM 233 %%% Salt Lake City, UT 84112-0090 %%% USA", %%% telephone = "+1 801 581 5254", %%% FAX = "+1 801 581 4148", %%% URL = "http://www.math.utah.edu/~beebe", %%% checksum = "21567 17685 98175 977473", %%% email = "beebe at math.utah.edu, beebe at acm.org, %%% beebe at computer.org (Internet)", %%% codetable = "ISO/ASCII", %%% keywords = "BibTeX; bibliography; Very Large Data Bases %%% Journal; VLDB Journal", %%% license = "public domain", %%% supported = "yes", %%% docstring = "This is a COMPLETE bibliography of %%% publications in the VLDB journal: Very Large %%% Data Bases (CODEN VLDBFR, ISSN 1066-8888 %%% (print), 0949-877X (electronic)), originally %%% published by Springer Verlag on behalf of the %%% VLDB Endowment, and now published by the ACM. %%% %%% Publication of the VLDB Journal begain with %%% volume 1, number 1, in 1992, and the journal %%% is normally published quarterly, although %%% occasionally, issues are combined, or volumes %%% are split across year boundaries. %%% %%% There is an editorial World Wide Web site at %%% %%% http://SunSITE.Informatik.RWTH-Aachen.DE/dblp/db/journals/vldb/ %%% %%% and a publisher Web site at %%% %%% http://link.springer.de/link/service/journals/00778/index.htm %%% http://portal.acm.org/toc.cfm?id=J869 %%% %%% At version 1.19, the year coverage looked %%% like this: %%% %%% 1992 ( 7) 1998 ( 22) 2004 ( 23) %%% 1993 ( 19) 1999 ( 8) 2005 ( 22) %%% 1994 ( 22) 2000 ( 36) 2006 ( 29) %%% 1995 ( 24) 2001 ( 25) 2007 ( 26) %%% 1996 ( 19) 2002 ( 23) 2008 ( 59) %%% 1997 ( 22) 2003 ( 23) %%% %%% Article: 409 %%% %%% Total entries: 409 %%% %%% This bibliography was prepared largely from %%% the Web pages at the editorial and publisher %%% sites. %%% %%% Spelling has been verified with the UNIX %%% spell and GNU ispell programs using the %%% exception dictionary stored in the companion %%% file with extension .sok. %%% %%% BibTeX citation tags are uniformly chosen %%% as name:year:abbrev, where name is the %%% family name of the first author or editor, %%% year is a 4-digit number, and abbrev is a %%% 3-letter condensation of important title %%% words. Citation tags were automatically %%% generated by software developed for the %%% BibNet Project. %%% %%% In this bibliography, entries are sorted in %%% publication order within each journal, %%% using bibsort -bypages. %%% %%% The checksum field above contains a CRC-16 %%% checksum as the first value, followed by the %%% equivalent of the standard UNIX wc (word %%% count) utility output of lines, words, and %%% characters. This is produced by Robert %%% Solovay's checksum utility.", %%% } %%% ==================================================================== @Preamble{ "\ifx \undefined \ocirc \def \ocirc #1{{\accent'27#1}}\fi" } %%% ==================================================================== %%% Acknowledgement abbreviations: @String{ack-nhfb = "Nelson H. F. Beebe, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|"} %%% ==================================================================== %%% Journal abbreviations: @String{j-VLDB-J = "VLDB Journal: Very Large Data Bases"} %%% ==================================================================== %%% Bibliography entries, sorted in publication order: @Article{Breitbart:1992:TMI, author = "Yuri Breitbart and Abraham Silberschatz and Glenn R. Thompson", title = "Transaction Management Issues in a Failure-Prone Multidatabase System Environment", journal = j-VLDB-J, volume = "1", number = "1", pages = "1--39", month = jul, year = "1992", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:23 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb1.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/b/Breitbart:Yuri.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Silberschatz:Abraham.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/t/Thompson:Glenn_R=.html", abstract = "This paper is concerned with the problem of integrating a number of existing, off-the-shelf local database systems into a multidatabase system that maintains consistency in the face of concurrency and failures. The major difficulties in designing such systems stem from the requirements that local transactions be allowed to execute outside the multidatabase system control, and that the various local database systems cannot participate in the execution of a global commit protocol. A scheme based on the assumption that the component local database systems use the strict two-phase locking protocol is developed. Two major problems are addressed: How to ensure global transaction atomicity without the provision of a commit protocol, and how to ensure freedom from global deadlocks.", acknowledgement = ack-nhfb, keywords = "algorithms; deadlock recovery; performance; reliability; serializibility; transaction log", xxauthor = "Yuri Breitbart and Avi Silberschatz and Glenn R. Thompson", xxpages = "1--40", } @Article{Nodine:1992:CTH, author = "Marian H. Nodine and Stanley B. Zdonik", title = "Cooperative Transaction Hierarchies: Transaction Support for Design Applications", journal = j-VLDB-J, volume = "1", number = "1", pages = "41--80", month = jul, year = "1992", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:23 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb1.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/n/Nodine:Marian_H=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/z/Zdonik:Stanley_B=.html", abstract = "Traditional atomic and nested transactions are not always well-suited to cooperative applications, such as design applications. Cooperative applications place requirements on the database that may conflict with the serializability requirement. They require transactions to be long, possibly nested, and able to interact with each other in a structured way. We define a transaction framework, called a {\em cooperative transaction hierarchy}, that allows us to relax the requirement for atomic, serializable transactions to better support cooperative applications. In cooperative transaction hierarchies, we allow the correctness specification for groups of designers to be tailored to the needs of the application. We use {\em patterns\/} and {\em conflicts\/} to specify the constraints imposed on a group's history for it to be correct. We also provide some primitives to smooth the operation of the members. We characterize deadlocks in a cooperative transaction hierarchy, and provide mechanisms for deadlock detection and resolution. We examine issues associated with failure and recovery.", acknowledgement = ack-nhfb, keywords = "cooperation; deadlock detection; design transactions; non-serializability; transaction hierarchies; transaction synchronization; version management", } @Article{Spaccapietra:1992:MIA, author = "Stefano Spaccapietra and Christine Parent and Yann Dupont", title = "Model Independent Assertions for Integration of Heterogeneous Schemas", journal = j-VLDB-J, volume = "1", number = "1", pages = "81--126", month = jul, year = "1992", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:23 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb1.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/d/Dupont:Yann.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/p/Parent:Christine.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Spaccapietra:Stefano.html", abstract = "Due to the proliferation of database applications, the integration of existing databases into a distributed or federated system is one of the major challenges in responding to enterprises' information requirements. Some proposed integration techniques aim at providing database administrators (DBAs) with a view definition language they can use to build the desired integrated schema. These techniques leave to the DBA the responsibility of appropriately restructuring schema elements from existing local schemas and of solving inter-schema conflicts. This paper investigates the {\em assertion-based\/} approach, in which the DBA's action is limited to pointing out corresponding elements in the schemas and to defining the nature of the correspondence in between. This methodology is capable of: ensuring better integration by taking into account additional semantic information (assertions about links); automatically solving structural conflicts; building the integrated schema without requiring conforming of initial schemas; applying integration rules to a variety of data models; and performing view as well as database integration. This paper presents the basic ideas underlying our approach and focuses on resolution of structural conflicts.", acknowledgement = ack-nhfb, keywords = "conceptual modeling; database design and integration; distributed databases; federated databases; heterogeneous databases; schema integration", } @Article{Hsiao:1992:FDSa, author = "David K. Hsiao", title = "Federated Databases and Systems: Part {I} --- {A} Tutorial on Their Data Sharing", journal = j-VLDB-J, volume = "1", number = "1", pages = "127--179", month = jul, year = "1992", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:23 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb1.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/h/Hsiao:David_K=.html", abstract = "The issues and solutions for the interoperability of a class of heterogeneous databases and their database systems are expounded in two parts. Part I presents the data-sharing issues in federated databases and systems. Part II, which will appear in a future issue, explores resource-consolidation issues. {\em Interoperability\/} in this context refers to data sharing among heterogeneous databases, and to resource consolidation of computer hardware, system software, and support personnel. {\em Resource consolidation\/} requires the presence of a database system architecture which supports the heterogeneous system software, thereby eliminating the need for various computer hardware and support personnel. The class of heterogeneous databases and database systems expounded herein is termed {\em federated}, meaning that they are joined in order to meet certain organizational requirements and because they require their respective application specificities, integrity constraints, and security requirements to be upheld. Federated databases and systems are new. While there are no technological solutions, there has been considerable research towards their development. This tutorial is aimed at exposing the need for such solutions. A taxonomy is introduced in our review of existing research undertakings and exploratory developments. With this taxonomy, we contrast and compare various approaches to federating databases and systems.", acknowledgement = ack-nhfb, keywords = "attribute-based; data-model-and-language-to-data-model-and-language mappings; database conversion; hierarchical; network; object-oriented; relational; schema transformation; transaction translation", xxpages = "127--180", } @Article{Breitbart:1992:OMT, author = "Yuri Breitbart and Hector Garcia-Molina and Abraham Silberschatz", title = "Overview of Multidatabase Transaction Management", journal = j-VLDB-J, volume = "1", number = "2", pages = "181--240", month = oct, year = "1992", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:23 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb1.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/b/Breitbart:Yuri.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/g/Garcia=Molina:Hector.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Silberschatz:Abraham.html", abstract = "A multidatabase system (MDBS) is a facility that allows users access to data located in multiple autonomous database management systems (DBMSs). In such a system, {\em global transactions\/} are executed under the control of the MDBS. Independently, {\em local transactions\/} are executed under the control of the local DBMSs. Each local DBMS integrated by the MDBS may employ a different transaction management scheme. In addition, each local DBMS has complete control over all transactions (global and local) executing at its site, including the ability to abort at any point any of the transactions executing at its site. Typically, no design or internal DBMS structure changes are allowed in order to accommodate the MDBS. Furthermore, the local DBMSs may not be aware of each other and, as a consequence, cannot coordinate their actions. Thus, traditional techniques for ensuring transaction atomicity and consistency in homogeneous distributed database systems may not be appropriate for an MDBS environment. The objective of this article is to provide a brief review of the most current work in the area of multidatabase transaction management. We first define the problem and argue that the multidatabase research will become increasingly important in the coming years. We then outline basic research issues in multidatabase transaction management and review recent results in the area. We conclude with a discussion of open problems and practical implications of this research.", acknowledgement = ack-nhfb, keywords = "multidatabase; recovery; reliability; serializability; transaction; two-level serializability", xxauthor = "Yuri Breitbart and Hector Garcia-Molina and Avi Silberschatz", } @Article{Drew:1992:TII, author = "Pamela Drew and Roger King and Dennis Heimbigner", title = "A Toolkit for the Incremental Implementation of Heterogeneous Database Management Systems", journal = j-VLDB-J, volume = "1", number = "2", pages = "241--284", month = oct, year = "1992", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:23 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb1.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/d/Drew:Pamela.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/h/Heimbigner:Dennis.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/k/King:Roger.html", abstract = "The integration of heterogeneous database environments is a difficult and complex task. The A la carte Framework addresses this complexity by providing a reusable and extensible architecture in which a set of heterogeneous database management systems can be integrated. The goal is to support incremental integration of existing database facilities into heterogeneous, interoperative, distributed systems. The Framework addresses the three main issues in heterogeneous systems integration. First, it identifies the problems in integrating heterogeneous systems. Second, it identifies the key interfaces and parameters required for autonomous systems to interoperate correctly. Third, it demonstrates an approach to integrating these interfaces in an extensible and incremental way. The A la carte Framework provides a set of reusable, integrating components which integrate the major functional domains, such as transaction management, that could or should be integrated in heterogeneous systems. It also provides a mechanism for capturing key characteristics of the components and constraints which describe how the components can be mixed and interchanged, thereby helping to reduce the complexity of the integration process. Using this framework, we have implemented an experimental, heterogeneous configuration as part of the object management work in the software engineering research consortium, Arcadia.", acknowledgement = ack-nhfb, keywords = "database toolkits; extensible databases; heterogeneous databases; heterogeneous transaction management; incremental integration; open architectures; reconfigurable architectures", } @Article{Hsiao:1992:FDSb, author = "David K. Hsiao", title = "Federated Databases and Systems: Part {II} --- {A} Tutorial on Their Resource Consolidation", journal = j-VLDB-J, volume = "1", number = "2", pages = "285--310", month = oct, year = "1992", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:23 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb1.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/h/Hsiao:David_K=.html", abstract = "The issues and solutions for the interoperability of a class of heterogeneous databases and their database systems are expounded in two parts. Part I presented the data-sharing issues in federated databases and systems (Hsiao, 1992). The present article explores resource-consolidation issues. {\em Interoperability\/} in this context refers to data sharing among heterogeneous databases, and to resource consolidation of computer hardware, system software, and support personnel. {\em Resource consolidation\/} requires the presence of a database system architecture which supports the heterogeneous system software, thereby eliminating the need for various computer hardware and support personnel. The class of heterogeneous databases and database systems expounded herein is termed {\em federated}, meaning that they are joined in order to meet certain organizational requirements and because they require their respective application specificities, integrity constraints, and security requirements to be upheld. Federated databases and systems are new. While there are no technological solutions, there has been considerable research towards their development. This tutorial is aimed at exposing the need for such solutions. A taxonomy is introduced in our review of existing research undertakings and exploratory developments. With this taxonomy, we contrast and compare various approaches to federating databases and systems.", acknowledgement = ack-nhfb, keywords = "attribute-based; data-model-and-language-to-data-model-and-language mappings; database conversion; hierarchical; network; object-oriented; relational; schema transformation; transaction translation", } @Article{Yu:1993:BMB, author = "Philip S. Yu and Douglas W. Cornell", title = "Buffer Management Based on Return on Consumption in a Multi-Query Environment", journal = j-VLDB-J, volume = "2", number = "1", pages = "1--37", month = jan, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:24 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/c/Cornell:Douglas_W=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/y/Yu:Philip_S=.html", abstract = "In a multi-query environment, the marginal utilities of allocating additional buffer to the various queries can be vastly different. The conventional approach examines each query in isolation to determine the optimal access plan and the corresponding locality set. This can lead to performance that is far from optimal. As each query can have different access plans with dissimilar locality sets and sensitivities to memory requirement, we employ the concepts of memory consumption and return on consumption (ROC) as the basis for memory allocations. Memory consumption of a query is its space-time product, while ROC is a measure of the effectiveness of response-time reduction through additional memory consumption. A global optimization strategy using simulated annealing is developed, which minimizes the average response over all queries under the constraint that the total memory consumption rate has to be less than the buffer size. It selects the optimal join method and memory allocation for all query types simultaneously. By analyzing the way the optimal strategy makes memory allocations, a heuristic threshold strategy is then proposed. The threshold strategy is based on the concept of ROC. As the memory consumption rate by all queries is limited by the buffer size, the strategy tries to allocate the memory so as to make sure that a certain level of ROC is achieved. A simulation model is developed to demonstrate that the heuristic strategy yields performance that is very close to the optimal strategy and is far superior to the conventional allocation strategy.", acknowledgement = ack-nhfb, keywords = "buffer management; join methods; query optimization; queueing model; simulated annealing; simulation", xxpages = "1--38", } @Article{Harder:1993:CCI, author = "Theo H{\"a}rder and Kurt Rothermel", title = "Concurrency Control Issues in Nested Transactions", journal = j-VLDB-J, volume = "2", number = "1", pages = "39--74", month = jan, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:24 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/h/H=auml=rder:Theo.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/r/Rothermel:Kurt.html", abstract = "The concept of nested transactions offers more decomposable execution units and finer-grained control over concurrency and recovery than `flat' transactions. Furthermore, it supports the decomposition of a `unit of work' into subtasks and their appropriate distribution in a computer system as a prerequisite of intratransaction parallelism. However, to exploit its full potential, suitable granules of concurrency control as well as access modes for shared data are necessary. In this article, we investigate various issues of concurrency control for nested transactions. First, the mechanisms for cooperation and communication within nested transactions should not impede parallel execution of transactions among parent and children or among siblings. Therefore, a model for nested transactions is proposed allowing for effective exploitation of intra-transaction parallelism. Starting with a set of basic locking rules, we introduce the concept of `downward inheritance of locks' to make data manipulated by a parent available to its children. To support supervised and restricted access, this concept is refined to `controlled downward inheritance.' The initial concurrency control scheme was based on S-X locks for `flat,' non-overlapping data objects. In order to adjust this scheme for practical applications, a set of concurrency control rules is derived for generalized lock modes described by a compatibility matrix. Also, these rules are combined with a hierarchical locking scheme to improve selective access to data granules of varying sizes. After having tied together both types of hierarchies (transaction and object), it can be shown how `controlled downward inheritance' for hierarchical objects is achieved in nested transactions. Finally, problems of deadlock detection and resolution in nested transactions are considered.", acknowledgement = ack-nhfb, keywords = "concurrency control; locking; nested transactions; object hierarchies", } @Article{Jensen:1993:UDT, author = "Christian S. Jensen and Leo Mark and Nick Roussopoulos and Timos K. Sellis", title = "Using Differential Techniques to Efficiently Support Transaction Time", journal = j-VLDB-J, volume = "2", number = "1", pages = "75--116", month = jan, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:24 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/j/Jensen:Christian_S=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/m/Mark:Leo.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/r/Roussopoulos:Nick.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Sellis:Timos_K=.html", abstract = "We present an architecture for query processing in the relational model extended with transaction time. The architecture integrates standard query optimization and computation techniques with new differential computation techniques. Differential computation computes a query incrementally or decrementally from the cached and indexed results of previous computations. The use of differential computation techniques is essential in order to provide efficient processing of queries that access very large temporal relations. Alternative query plans are integrated into a state transition network, where the state space includes backlogs of base relations, cached results from previous computations, a cache index, and intermediate results; the transitions include standard relational algebra operators, operators for constructing differential files, operators for differential computation, and combined operators. A rule set is presented to prune away parts of state transition networks that are not promising, and dynamic programming techniques are used to identify the optimal plans from the remaining state transition networks. An extended logical access path serves as a `structuring' index on the cached results and contains, in addition, vital statistics for the query optimization process (including statistics about base relations, backlogs, and queries---previously computed and cached, previously computed, or just previously estimated).", acknowledgement = ack-nhfb, keywords = "efficient query processing; incremental and decremental computation; temporal databases; transaction time", } @Article{Haritsa:1993:VBS, author = "Jayant R. Haritsa and Michael J. Carey and Miron Livny", title = "Value-Based Scheduling in Real-Time Database Systems", journal = j-VLDB-J, volume = "2", number = "2", pages = "117--152", month = apr, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:25 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/c/Carey:Michael_J=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/h/Haritsa:Jayant_R=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/l/Livny:Miron.html", abstract = "In a real-time database system, an application may assign a {\em value\/} to a transaction to reflect the return it expects to receive if the transaction commits before its deadline. Most research on real-time database systems has focused on systems where all transactions are assigned the same value, the performance goal being to minimize the number of missed deadlines. When transactions are assigned different values, the goal of the system shifts to maximizing the sum of the values of those transactions that commit by their deadlines. Minimizing the number of missed deadlines becomes a secondary concern. In this article, we address the problem of establishing a priority ordering among transactions characterized by both values and deadlines that results in maximizing the realized value. Of particular interest is the tradeoff established between these values and deadlines in constructing the priority ordering. Using a detailed simulation model, we evaluate the performance of several priority mappings that make this tradeoff in different, but fixed, ways. In addition, a `bucket' priority mechanism that allows the relative importance of values and deadlines to be controlled is introduced and studied. The notion of associating a penalty with transactions whose deadlines are not met is also briefly considered.", acknowledgement = ack-nhfb, keywords = "priority and concurrency algorithms; priority mapping; resource and data contention; transaction values and deadlines", } @Article{Grant:1993:QLR, author = "John Grant and Witold Litwin and Nick Roussopoulos and Timos K. Sellis", title = "Query Languages for Relational Multidatabases", journal = j-VLDB-J, volume = "2", number = "2", pages = "153--171", month = apr, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:25 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/g/Grant:John.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/l/Litwin:Witold.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/r/Roussopoulos:Nick.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Sellis:Timos_K=.html", abstract = "With the existence of many autonomous databases widely accessible through computer networks, users will require the capability to jointly manipulate data in different databases. A multidatabase system provides such a capability through a multidatabase manipulation language, such as MSQL. We propose a theoretical foundation for such languages by presenting a multirelational algebra and calculus based on the relational algebra and calculus. The proposal is illustrated by various queries on an example multidatabase. It is shown that properties of the multirelational algebra may be used for optimization and that every multirelational algebra query can be expressed as a multirelational calculus query. The connection between the multirelational languages and MSQL, the multidatabase version of SQL, is also investigated.", acknowledgement = ack-nhfb, keywords = "multidatabase; multirelational algebra; multirelational calculus; query optimization", xxpages = "153--172", } @Article{Neufeld:1993:GCT, author = "Andrea Neufeld and Guido Moerkotte and Peter C. Lockemann", title = "Generating Consistent Test Data for a Variable Set of General Consistency Constraints", journal = j-VLDB-J, volume = "2", number = "2", pages = "173--213", month = apr, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:25 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/l/Lockemann:Peter_C=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/m/Moerkotte:Guido.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/n/Neufeld:Andrea.html", abstract = "To address the problem of generating test data for a set of general consistency constraints, we propose a new two-step approach: First the interdependencies between consistency constraints are explored and a generator formula is derived on their basis. During its creation, the user may exert control. In essence, the generator formula contains information to restrict the search for consistent test databases. In the second step, the test database is generated. Here, two different approaches are proposed. The first adapts an already published approach to generating finite models by enhancing it with requirements imposed by test data generation. The second, a new approach, operationalizes the generator formula by translating it into a sequence of operators, and then executes it to construct the test database. For this purpose, we introduce two powerful operators: the generation operator and the test-and-repair operator. This approach also allows for enhancing the generation operators with heuristics for generating facts in a goal-directed fashion. It avoids the generation of test data that may contradict the consistency constraints, and limits the search space for the test data. This article concludes with a careful evaluation and comparison of the performance of the two approaches and their variants by describing a number of benchmarks and their results.", acknowledgement = ack-nhfb, keywords = "consistency; design; logic; test data; validation", xxpages = "173--214", xxtitle = "Generating consistent test data: restricting the search space by a generator formula", } @Article{Du:1993:SCU, author = "Weimin Du and Ahmed K. Elmagarmid and Won Kim and Omran A. Bukhres", title = "Supporting Consistent Updates in Replicated Multidatabase Systems", journal = j-VLDB-J, volume = "2", number = "2", pages = "215--241", month = apr, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:25 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/b/Bukhres:Omran_A=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/d/Du:Weimin.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/e/Elmagarmid:Ahmed_K=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/k/Kim:Won.html", abstract = "Replication is useful in multidatabase systems (MDBSs) because, as in traditional distributed database systems, it increases data availability in the presence of failures and decreases data retrieval costs by reading local or close copies of data. Concurrency control, however, is more difficult in replicated MDBSs than in ordinary distributed database systems. This is the case not only because local concurrency controllers may schedule global transactions inconsistently, but also because local transactions (at different sites) may access the same replicated data. In this article, we propose a decentralized concurrency control protocol for a replicated MDBS. The proposed strategy supports prompt and consistent updates of replicated data by both local and global applications without a central coordinator.", acknowledgement = ack-nhfb, keywords = "concurrency control; multidatabases; replica control; replicated data management; resolvable conflicts; serializability", } @Article{Anonymous:1993:Ca, author = "Anonymous", title = "Column", journal = j-VLDB-J, volume = "2", number = "2", pages = "??--??", month = apr, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:25 MDT 2008", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Anonymous:1993:Cb, author = "Anonymous", title = "Column", journal = j-VLDB-J, volume = "2", number = "2", pages = "??--??", month = apr, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:25 MDT 2008", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Tomasic:1993:SIP, author = "Anthony Tomasic and Hector Garcia-Molina", title = "Special Issue in Parallelism in Database Systems: Query Processing and Inverted Indices in Shared-Nothing Document Information Retrieval Systems", journal = j-VLDB-J, volume = "2", number = "3", pages = "243--275", month = jul, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Wed Sep 27 08:46:01 MDT 2000", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/g/Garcia=Molina:Hector.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/t/Tomasic:Anthony.html", acknowledgement = ack-nhfb, } @Article{Tomasic:1993:QPI, author = "Anthony Tomasic and Hector Garcia-Molina", title = "Query processing and inverted indices in shared: nothing text document information retrieval systems", journal = j-VLDB-J, volume = "2", number = "3", pages = "243--276", month = jul, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:26 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "The performance of distributed text document retrieval systems is strongly influenced by the organization of the inverted text. This article compares the performance impact on query processing of various physical organizations for inverted lists. We present a new probabilistic model of the database and queries. Simulation experiments determine those variables that most strongly influence response time and throughput. This leads to a set of design trade-offs over a wide range of hardware configurations and new parallel query processing strategies.", acknowledgement = ack-nhfb, keywords = "file organization; full text information retrieval; inverted file; inverted index; performance; query processing; shared-nothing; striping", } @Article{Ziane:1993:PQP, author = "Mikal Ziane and Mohamed Za{\"\i}t and Pascale Borla-Salamet", title = "Parallel Query Processing with Zigzag Trees", journal = j-VLDB-J, volume = "2", number = "3", pages = "277--301", month = jul, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:26 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/b/Borla=Salamet:Pascale.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/z/Za=iuml=t:Mohamed.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/z/Ziane:Mikal.html", abstract = "In this article, we describe our approach to the compile-time optimization and parallelization of queries for execution in DBS3 or EDS. DBS3 is a shared-memory parallel database system, while the EDS system has a distributed-memory architecture. Because DBS3 implements a parallel dataflow execution model, this approach applies to both architectures. Using randomized search strategies enables the exploration of a search space large enough to include zigzag trees, which are intermediate between left-deep and right-deep trees. Zigzag trees are shown to provide better response time than right-deep trees in case of limited memory. Performance measurements obtained using the DBS3 prototype show the advantages of zigzag trees under various conditions.", acknowledgement = ack-nhfb, keywords = "cost function; fragmentation; pipeline; search space", xxpages = "277--302", } @Article{Hua:1993:CDS, author = "Kien A. Hua and Yu-lung Lo and Honesty C. Young", title = "Considering Data Skew Factor in Multi-Way Join Query Optimization for Parallel Execution", journal = j-VLDB-J, volume = "2", number = "3", pages = "303--330", month = jul, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:26 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/h/Hua:Kien_A=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/l/Lo:Yu=lung.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/y/Young:Honesty_C=.html", abstract = "A consensus on parallel architecture for very large database management has emerged. This architecture is based on a shared-nothing hardware organization. The computation model is very sensitive to skew in tuple distribution, however. Recently, several parallel join algorithms with dynamic load balancing capabilities have been proposed to address this issue, but none of them consider multi-way join problems. In this article we propose a dynamic load balancing technique for multi-way joins, and investigate the effect of load balancing on query optimization. In particular, we present a join-ordering strategy that takes load-balancing issues into consideration. Our performance study indicates that the proposed query optimization technique can provide very impressive performance improvement over conventional approaches.", acknowledgement = ack-nhfb, keywords = "load balancing; multi-way join; parallel-database computer; query optimization", xxauthor = "Kien A. Hua and Yo Lung Lo and Honesty C. Young", } @Article{Zhang:1993:TGC, author = "Aidong Zhang and Ahmed K. Elmagarmid", title = "A Theory of Global Concurrency Control in Multidatabase Systems", journal = j-VLDB-J, volume = "2", number = "3", pages = "331--360", month = jul, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:26 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/e/Elmagarmid:Ahmed_K=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/z/Zhang:Aidong.html", abstract = "This article presents a theoretical basis for global concurrency control to maintain global serializability in multidatabase systems. Three correctness criteria are formulated that utilize the intrinsic characteristics of global transactions to determine the serialization order of global subtransactions at each local site. In particular, two new types of serializability, chain-conflicting serializability and sharing serializability, are proposed and hybrid serializability, which combines these two basic criteria, is discussed. These criteria offer the advantage of imposing no restrictions on local sites other than local serializability while retaining global serializability. The graph testing techniques of the three criteria are provided as guidance for global transaction scheduling. In addition, an optimal property of global transactions for determinating the serialization order of global subtransactions at local sites is formulated. This property defines the upper limit on global serializability in multidatabase systems.", acknowledgement = ack-nhfb, keywords = "chain-conflicting serializability; hybrid serializability; optimality; sharing serializability", } @Article{Anonymous:1993:SIP, author = "Anonymous", title = "Special issue in parallelism in database systems", journal = j-VLDB-J, volume = "2", number = "3", pages = "??--??", month = jul, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:26 MDT 2008", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Srinivasan:1993:PBT, author = "V. Srinivasan and Michael J. Carey", title = "Performance of {B$^+$} tree concurrency control algorithms", journal = j-VLDB-J, volume = "2", number = "4", pages = "361--406", month = oct, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:27 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/c/Carey:Michael_J=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Srinivasan:V=.html", abstract = "A number of algorithms have been proposed to access B$^+$-trees concurrently, but they are not well understood. In this article, we study the performance of various B$^+$-tree concurrency control algorithms using a detailed simulation model of B$^+$-tree operations in a centralized DBMS. Our study covers a wide range of data contention situations and resource conditions. In addition, based on the performance of the set of B$^+$-tree concurrency control algorithms, which includes one new algorithm, we make projections regarding the performance of other algorithms in the literature. Our results indicate that algorithms with updaters that lock-couple using exclusive locks perform poorly as compared to those that permit more optimistic index descents. In particular, the B-link algorithms are seen to provide the most concurrency and the best overall performance. Finally, we demonstrate the need for a highly concurrent long-term lock holding strategy to obtain the full benefits of a highly concurrent algorithm for index operations.", acknowledgement = ack-nhfb, keywords = "B+-tree structures; data contention; lock modes; performance; resource conditions; simulation models; workload parameters", xxtitle = "Performance of {B+} Tree Concurrency Algorithms", } @Article{Weikum:1993:MLT, author = "Gerhard Weikum and Christof Hasse", title = "Multi-Level Transaction Management for Complex Objects: Implementation, Performance, Parallelism", journal = j-VLDB-J, volume = "2", number = "4", pages = "407--453", month = oct, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:27 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/h/Hasse:Christof.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/w/Weikum:Gerhard.html", abstract = "Multi-level transactions are a variant of open-nested transactions in which the subtransactions correspond to operations at different levels of a layered system architecture. They allow the exploitation of semantics of high-level operations to increase concurrency. As a consequence, undoing a transaction requires compensation of completed subtransactions. In addition, multi-level recovery methods must take into consideration that high-level operations are not necessarily atomic if multiple pages are updated in a single subtransaction. This article presents algorithms for multi-level transaction management that are implemented in the database kernel system (DASDBS). In particular, we show that multi-level recovery can be implemented in an efficient way. We discuss performance measurements using a synthetic benchmark for processing complex objects in a multi-user environment. We show that multi-level transaction management can be extended easily to cope with parallel subtransactions within a single transaction. Performance results are presented with varying degrees of inter- and intratransaction parallelism.", acknowledgement = ack-nhfb, keywords = "atomicity; complex objects; inter- and intratransaction parallelism; multi-level transactions; performance; persistence; recovery", xxpages = "407--454", } @Article{Storey:1993:USR, author = "Veda C. Storey", title = "Understanding Semantic Relationships", journal = j-VLDB-J, volume = "2", number = "4", pages = "455--488", month = oct, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:27 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Storey:Veda_C=.html", abstract = "To develop sophisticated database management systems, there is a need to incorporate more understanding of the real world in the information that is stored in a database. Semantic data models have been developed to try to capture some of the meaning, as well as the structure, of data using abstractions such as inclusion, aggregation, and association. Besides these well-known relationships, a number of additional semantic relationships have been identified by researchers in other disciplines such as linguistics, logic, and cognitive psychology. This article explores some of the lesser-recognized semantic relationships and discusses both how they could be captured, either manually or by using an automated tool, and their impact on database design. To demonstrate the feasibility of this research, a prototype system for analyzing semantic relationships, called the Semantic Relationship Analyzer, is presented.", acknowledgement = ack-nhfb, keywords = "database design; database design systems; entity-relationship model; relational model; semantic relationships", } @Article{Tseng:1993:SMS, author = "Frank Shou-Cheng Tseng and Arbee L. P. Chen and W.-P. Yang", title = "Searching a Minimal Semantically-Equivalent Subset of a Set of Partial Values", journal = j-VLDB-J, volume = "2", number = "4", pages = "489--512", month = oct, year = "1993", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:27 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb2.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/c/Chen:Arbee_L=_P=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/t/Tseng:Frank_Shou=Cheng.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/y/Yang:W==P=.html", abstract = "Imprecise data exist in databases due to their unavailability or to data/schema incompatibilities in a multidatabase system. Partial values have been used to represent imprecise data. Manipulation of partial values is therefore necessary to process queries involving imprecise data. In this article, we study the problem of eliminating redundant partial values that result from a projection on an attribute with partial values. The redundancy of partial values is defined through the interpretation of a set of partial values. This problem is equivalent to searching a minimal semantically-equivalent subset of a set of partial values. A semantically-equivalent subset contains exactly the same information as the original set. We derive a set of useful properties and apply a graph matching technique to develop an efficient algorithm for searching such a minimal subset and therefore eliminating redundant partial values. By this process, we not only provide a concise answer to the user, but also reduce the communication cost when partial values are requested to be transmitted from one site to another site in a distributed environment. Moreover, further manipulation of the partial values can be simplified. This work is also extended to the case of multi-attribute projections.", acknowledgement = ack-nhfb, keywords = "bipartite graph; graph matching; imprecise data; minimal elements; multidatabase systems; partial values", xxauthor = "Frank S. C. Tseng and Arbee L. P. Chen and Wei Pang Yang", } @Article{Georgakopoulos:1994:CST, author = "Dimitrios Georgakopoulos and Marek Rusinkiewicz and Witold Litwin", title = "Chronological Scheduling of Transactions with Temporal Dependencies", journal = j-VLDB-J, volume = "3", number = "1", pages = "1--28", month = jan, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:28 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/g/Georgakopoulos:Dimitrios.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/l/Litwin:Witold.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/r/Rusinkiewicz:Marek.html", abstract = "Database applications often impose temporal dependencies between transactions that must be satisfied to preserve data consistency. The extant correctness criteria used to schedule the execution of concurrent transactions are either time independent or use strict, difficult to satisfy real-time constraints. On one end of the spectrum, serializability completely ignores time. On the other end, deadline scheduling approaches consider the outcome of each transaction execution correct only if the transaction meets its real-time deadline. In this article, we explore new correctness criteria and scheduling methods that capture temporal transaction dependencies and belong to the broad area between these two extreme approaches. We introduce the concepts of {\em succession dependency\/} and {\em chronological dependency\/} and define correctness criteria under which temporal dependencies between transactions are preserved even if the dependent transactions execute concurrently. We also propose a {\em chronological scheduler\/} that can guarantee that transaction executions satisfy their chronological constraints. The advantages of chronological scheduling over traditional scheduling methods, as well as the main issues in the implementation and performance of the proposed scheduler, are discussed.", acknowledgement = ack-nhfb, keywords = "concurrent succession; execution correctness; partial rollbacks; synchronization; transaction ordering", } @Article{Whang:1994:DMD, author = "Kyu Young Whang and Sang Wook Kim and Gio Wiederhold", title = "Dynamic Maintenance of Data Distribution for Selectivity Estimation", journal = j-VLDB-J, volume = "3", number = "1", pages = "29--51", month = jan, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:28 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/k/Kim:Sang=Wook.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/w/Whang:Kyu=Young.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/w/Wiederhold:Gio.html", abstract = "We propose a new dynamic method for multidimensional selectivity estimation for range queries that works accurately independent of data distribution. Good estimation of selectivity is important for query optimization and physical database design. Our method employs the multilevel grid file (MLGF) for accurate estimation of multidimensional data distribution. The MLGF is a dynamic, hierarchical, balanced, multidimensional file structure that gracefully adapts to nonuniform and correlated distributions. We show that the MLGF directory naturally represents a multidimensional data distribution. We then extend it for further refinement and present the selectivity estimation method based on the MLGF. Extensive experiments have been performed to test the accuracy of selectivity estimation. The results show that estimation errors are very small independent of distributions, even with correlated and/or highly skewed ones. Finally, we analyze the cause of errors in estimation and investigate the effects of various parameters on the accuracy of estimation.", acknowledgement = ack-nhfb, keywords = "multidimensional file structure; multilevel grid files; physical database design; query optimization", } @Article{Kamel:1994:PBO, author = "Nabil Kamel and Ping Wu and Stanley Y. W. Su", title = "A Pattern-Based Object Calculus", journal = j-VLDB-J, volume = "3", number = "1", pages = "53--76", month = jan, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:28 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/k/Kamel:Nabil.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Su:Stanley_Y=_W=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/w/Wu:Ping.html", abstract = "Several object-oriented database management systems have been implemented without an accompanying theoretical foundation for constraint, query specification, and processing. The pattern-based object calculus presented in this article provides such a theoretical foundation for describing and processing object-oriented databases. We view an object-oriented database as a network of interrelated classes (i.e., the intension) and a collection of time-varying object association patterns (i.e., the extension). The object calculus is based on first-order logic. It provides the formalism for interpreting precisely and uniformly the semantics of queries and integrity constraints in object-oriented databases. The power of the object calculus is shown in four aspects. First, associations among objects are expressed explicitly in an object-oriented database. Second, the `nonassociation' operator is included in the object calculus. Third, set-oriented operations can be performed on both homogeneous and heterogeneous object association patterns. Fourth, our approach does not assume a specific form of database schema. A proposed formalism is also applied to the design of high-level object-oriented query and constraint languages.", acknowledgement = ack-nhfb, keywords = "association patterns; Object-oriented databases; query expressions; semantic constraints", } @Article{Sciore:1994:VCM, author = "Edward Sciore", title = "Versioning and Configuration Management in an Object-Oriented Data Model", journal = j-VLDB-J, volume = "3", number = "1", pages = "77--106", month = jan, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:28 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Sciore:Edward.html", abstract = "Many database applications require the storage and manipulation of different versions of data objects. To satisfy the diverse needs of these applications, current database systems support versioning at a very low level. This article demonstrates that application-independent versioning can be supported at a significantly higher level. In particular, we extend the EXTRA data model and EXCESS query language so that configurations can be specified conceptually and non-procedurally. We also show how version sets can be viewed multidimensionally, thereby allowing configurations to be expressed at a higher level of abstraction. The resulting model integrates and generalizes ideas in CAD systems, CASE systems, and temporal databases.", acknowledgement = ack-nhfb, keywords = "EXTRA/EXCESS data models; generic and specific references; query language; semantically based configuration specifications", } @Article{Ramamohanarao:1994:IDD, author = "Kotagiri Ramamohanarao and James Harland", title = "An introduction to deductive database languages and systems", journal = j-VLDB-J, volume = "3", number = "2", pages = "107--122", month = apr, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:29 MDT 2008", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Ramamohanarao:1994:SIP, author = "Kotagiri Ramamohanarao and James Harland", title = "Special Issue on Prototypes of Deductive Database Systems: An Introduction to Deductive Database Languages and Systems", journal = j-VLDB-J, volume = "3", number = "2", pages = "107--122", month = apr, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Wed Sep 27 08:46:01 MDT 2000", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/h/Harland:James.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/r/Ramamohanarao:Kotagiri.html", acknowledgement = ack-nhfb, } @Article{Derr:1994:GND, author = "Marcia A. Derr and Shinichi Morishita and Geoffrey Phipps", title = "The Glue-Nail Deductive Database System: Design, Implementation, and Evaluation", journal = j-VLDB-J, volume = "3", number = "2", pages = "123--160", month = apr, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:29 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/d/Derr:Marcia_A=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/m/Morishita:Shinichi.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/p/Phipps:Geoffrey.html", abstract = "We describe the design and implementation of the Glue-Nail deductive database system. Nail is a purely declarative query language; Glue is a procedural language used for non-query activities. The two languages combined are sufficient to write a complete application. Nail and Glue code are both compiled into the target language IGlue. The Nail compiler uses variants of the magic sets algorithm and supports well-founded models. The Glue compiler's static optimizer uses peephole techniques and data flow analysis to improve code. The IGlue interpreter features a run-time adaptive optimizer that reoptimizes queries and automatically selects indexes. We also describe the Glue-Nail benchmark suite, a set of applications developed to evaluate the Glue-Nail language and to measure the performance of the system.", acknowledgement = ack-nhfb, keywords = "language; performance; query optimization", } @Article{Ramakrishnan:1994:CDS, author = "Raghu Ramakrishnan and Divesh Srivastava and S. Sudarshan and Praveen Seshadri", title = "The {CORAL} Deductive System", journal = j-VLDB-J, volume = "3", number = "2", pages = "161--210", month = apr, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:29 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/r/Ramakrishnan:Raghu.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Seshadri:Praveen.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Srivastava:Divesh.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Sudarshan:S=.html", abstract = "CORAL is a deductive system that supports a rich declarative language, and an interface to C++, which allows for a combination of declarative and imperative programming. A CORAL declarative program can be organized as a collection of interacting modules. CORAL supports a wide range of evaluation strategies, and automatically chooses an efficient strategy for each module in the program. Users can guide query optimization by selecting from a wide range of control choices. The CORAL system provides imperative constructs to update, insert, and delete facts. Users can program in a combination of declarative CORAL and C++ extended with CORAL primitives. A high degree of extensibility is provided by allowing C++ programmers to use the class structure of C++ to enhance the CORAL implementation. CORAL provides support for main-memory data and, using the EXODUS storage manager, disk-resident data. We present a comprehensive view of the system from broad design goals, the language, and the architecture, to language interfaces and implementation details.", acknowledgement = ack-nhfb, keywords = "deductive database; logic programming system; query language", } @Article{Kiessling:1994:DSE, author = "Werner Kie{\ss}ling and Helmut Schmidt and Werner Strau{\ss} and Gerhard D{\"u}nzinger", title = "{DECLARE} and {SDS}: Early Efforts to Commercialize Deductive Database Technology", journal = j-VLDB-J, volume = "3", number = "2", pages = "211--243", month = apr, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:29 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/d/D=uuml=nzinger:Gerhard.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/k/Kie=szlig=ling:Werner.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Schmidt:Helmut.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Strau=szlig=:Werner.html", abstract = "The Smart Data System (SDS) and its declarative query language, Declarative Reasoning, represent the first large-scale effort to commercialize deductive database technology. SDS offers the functionality of deductive reasoning in a distributed, heterogeneous database environment. In this article we discuss several interesting aspects of the query compilation and optimization process. The emphasis is on the query execution plan data structure and its transformations by the optimizing rule compiler. Through detailed case studies we demonstrate that efficient and very compact runtime code can be generated. We also discuss our experiences gained from a large pilot application (the MVV-expert) and report on several issues of practical interest in engineering such a complex system, including the migration from Lisp to C. We argue that heuristic knowledge and control should be made an integral part of deductive databases.", acknowledgement = ack-nhfb, keywords = "declarative reasoning; distributed query processing; heuristic control; multi-databases; productization; query optimizer", } @Article{Vaghani:1994:ADD, author = "Jayen Vaghani and Kotagiri Ramamohanarao and David B. Kemp and Zoltan Somogyi and Peter J. Stuckey and Tim S. Leask and James Harland", title = "The {Aditi} Deductive Database System", journal = j-VLDB-J, volume = "3", number = "2", pages = "245--288", month = apr, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:29 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/h/Harland:James.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/k/Kemp:David_B=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/l/Leask:Tim_S=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/r/Ramamohanarao:Kotagiri.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Somogyi:Zoltan.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Stuckey:Peter_J=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/v/Vaghani:Jayen.html", abstract = "Deductive databases generalize relational databases by providing support for recursive views and non-atomic data. Aditi is a deductive system based on the client-server model; it is inherently multi-user and capable of exploiting parallelism on shared-memory multiprocessors. The back-end uses relational technology for efficiency in the management of disk-based data and uses optimization algorithms especially developed for the bottom-up evaluation of logical queries involving recursion. The front-end interacts with the user in a logical language that has more expressive power than relational query languages. We present the structure of Aditi, discuss its components in some detail, and present performance figures.", acknowledgement = ack-nhfb, keywords = "implementation; logic; multi-user; parallelism; relational database", } @Article{Anonymous:1994:SIP, author = "Anonymous", title = "Special issue on prototypes of deductive database systems", journal = j-VLDB-J, volume = "3", number = "2", pages = "??--??", month = apr, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:29 MDT 2008", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Lee:1994:EIV, author = "Byung Suk Lee and Gio Wiederhold", title = "Efficiently Instantiating View-Objects From Remote Relational Databases", journal = j-VLDB-J, volume = "3", number = "3", pages = "289--323", month = jul, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:30 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/l/Lee:Byung_Suk.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/w/Wiederhold:Gio.html", abstract = "View-objects are complex objects that are instantiated by delivering a query to a database and converting the query result into a nested structure. In relational databases, query results are conventionally retrieved as a single flat relation, which contains duplicate subtuples in its composite tuples. These duplicate subtuples increase the amount of data to be handled and thus degrade performance. In this article, we describe two new methods that retrieve a query result in structures other than a single flat relation. One method retrieves a set of relation fragments, and the other retrieves a single-nested relation. We first describe their algorithms and cost models, and then present the cost comparison results in a client-server architecture with a relational main memory database residing on a server.", acknowledgement = ack-nhfb, keywords = "client server; complex object; nested relation; query optimization; relation fragments", } @Article{Barbara-Milla:1994:DPT, author = "Daniel Barbar{\'a}-Mill{\'a} and Hector Garcia-Molina", title = "The demarcation protocol: a technique for maintaining constraints in distributed database systems", journal = j-VLDB-J, volume = "3", number = "3", pages = "325--353", month = jul, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:30 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Traditional protocols for distributed database management have a high message overhead; restrain or lock access to resources during protocol execution; and may become impractical for some scenarios like real-time systems and very large distributed databases. In this article, we present the demarcation protocol; it overcomes these problems by using explicit consistency constraints as the correctness criteria. The method establishes safe limits as `lines drawn in the sand' for updates, and makes it possible to change these limits dynamically, enforcing the constraints at all times. We show how this technique can be applied to linear arithmetic, existential, key, and approximate copy constraints.", acknowledgement = ack-nhfb, keywords = "consistency constraints; serializability; transaction limits", } @Article{Barbara:1994:DPT, author = "Daniel Barbar{\'a} and Hector Garcia-Molina", title = "The Demarcation Protocol: {A} Technique for Maintaining Constraints in Distributed Database Systems", journal = j-VLDB-J, volume = "3", number = "3", pages = "325--353", month = jul, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Wed Sep 27 08:46:01 MDT 2000", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/b/Barbar=aacute=:Daniel.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/g/Garcia=Molina:Hector.html", acknowledgement = ack-nhfb, } @Article{Bertino:1994:ICO, author = "Elisa Bertino", title = "Index Configuration in Object-Oriented Databases", journal = j-VLDB-J, volume = "3", number = "3", pages = "355--399", month = jul, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:30 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/b/Bertino:Elisa.html", abstract = "In relational databases, an attribute of a relation can have only a single primitive value, making it cumbersome to model complex objects. The object-oriented paradigm removes this difficulty by introducing the notion of nested objects, which allows the value of an object attribute to be another object or a set of other objects. This means that a class consists of a set of attributes, and the values of the attributes are objects that belong to other classes; that is, the definition of a class forms a hierarchy of classes. All attributes of the nested classes are nested attributes of the root of the hierarchy. A branch of such hierarchy is called a {\em path}. In this article, we address the problem of index configuration for a given path. We first summarize some basic concepts, and introduce the concept of index configuration for a path. Then we present cost formulas to evaluate the costs of the various configurations. Finally, we present the algorithm that determines the optimal configuration, and show its correctness.", acknowledgement = ack-nhfb, keywords = "index selection; physical database design; query optimization", } @Article{Guting:1994:ISD, author = "Ralf Hartmut G{\"u}ting", title = "An introduction to spatial database systems", journal = j-VLDB-J, volume = "3", number = "4", pages = "357--399", month = oct, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We propose a definition of a spatial database system as a database system that offers spatial data types in its data model and query language, and supports spatial data types in its implementation, providing at least spatial indexing and spatial join methods. Spatial database systems offer the underlying database technology for geographic information systems and other applications. We survey data modeling, querying, data structures and algorithms, and system architecture for such systems. The emphasis is on describing known technology in a coherent manner, rather than listing open problems.", acknowledgement = ack-nhfb, } @Article{Guting:1994:SIS, author = "Ralf Hartmut G{\"u}ting", title = "Special Issue on Spatial Database Systems: An Introduction to Spatial Database Systems", journal = j-VLDB-J, volume = "3", number = "4", pages = "357--399", month = oct, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Wed Sep 27 08:46:01 MDT 2000", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/g/G=uuml=ting:Ralf_Hartmut.html", acknowledgement = ack-nhfb, } @Article{Baumann:1994:MMD, author = "Peter Baumann", title = "Management of Multidimensional Discrete Data", journal = j-VLDB-J, volume = "3", number = "4", pages = "401--444", month = oct, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:31 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/b/Baumann:Peter.html", abstract = "Spatial database management involves two main categories of data: vector and raster data. The former has received a lot of in-depth investigation; the latter still lacks a sound framework. Current DBMSs either regard raster data as pure byte sequences where the DBMS has no knowledge about the underlying semantics, or they do not complement array structures with storage mechanisms suitable for huge arrays, or they are designed as specialized systems with sophisticated imaging functionality, but no general database capabilities (e.g., a query language). Many types of array data will require database support in the future, notably 2-D images, audio data and general signal-time series (1-D), animations (3-D), static or time-variant voxel fields (3-D and 4-D), and the ISO/IEC PIKS (Programmer's Imaging Kernel System) BasicImage type (5-D). In this article, we propose a comprehensive support of {\em multidimensional discrete data\/} (MDD) in databases, including operations on arrays of arbitrary size over arbitrary data types. A set of requirements is developed, a small set of language constructs is proposed (based on a formal algebraic semantics), and a novel MDD architecture is outlined to provide the basis for efficient MDD query evaluation.", acknowledgement = ack-nhfb, keywords = "image database systems; multimedia database systems; spatial index; tiling", } @Article{Chu:1994:SMA, author = "Wesley W. Chu and Ion Tim Ieong and Ricky K. Taira", title = "A Semantic Modeling Approach for Image Retrieval by Content", journal = j-VLDB-J, volume = "3", number = "4", pages = "445--477", month = oct, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:31 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/c/Chu:Wesley_W=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/i/Ieong:Ion_Tim.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/t/Taira:Ricky_K=.html", abstract = "We introduce a semantic data model to capture the hierarchical, spatial, temporal, and evolutionary semantics of images in pictorial databases. This model mimics the user's conceptual view of the image content, providing the framework and guidelines for preprocessing to extract image features. Based on the model constructs, a spatial evolutionary query language (SEQL), which provides direct image object manipulation capabilities, is presented. With semantic information captured in the model, spatial evolutionary queries are answered efficiently. Using an object-oriented platform, a prototype medical-image management system was implemented at UCLA to demonstrate the feasibility of the proposed approach.", acknowledgement = ack-nhfb, keywords = "image; medical; multimedia databases; spatial query processing; temporal evolutionary query processing", } @Article{Papadias:1994:QRS, author = "Dimitris Papadias and Timos K. Sellis", title = "Qualitative Representation of Spatial Knowledge in Two-Dimensional Space", journal = j-VLDB-J, volume = "3", number = "4", pages = "479--516", month = oct, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:31 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/p/Papadias:Dimitris.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Sellis:Timos_K=.html", abstract = "Various relation-based systems, concerned with the qualitative representation and processing of spatial knowledge, have been developed in numerous application domains. In this article, we identify the common concepts underlying qualitative spatial knowledge representation, we compare the representational properties of the different systems, and we outline the computational tasks involved in relation-based spatial information processing. We also describe {\em symbolic spatial indexes}, relation-based structures that combine several ideas in spatial knowledge representation. A symbolic spatial index is an array that preserves only a set of spatial relations among distinct objects in an image, called the modeling space; the index array discards information, such as shape and size of objects, and irrelevant spatial relations. The construction of a symbolic spatial index from an input image can be thought of as a transformation that keeps only a set of representative points needed to define the relations of the modeling space. By keeping the relative arrangements of the representative points in symbolic spatial indexes and discarding all other points, we maintain enough information to answer queries regarding the spatial relations of the modeling space without the need to access the initial image or an object database. Symbolic spatial indexes can be used to solve problems involving route planning, composition of spatial relations, and update operations.", acknowledgement = ack-nhfb, keywords = "qualitative spatial information processing; representation of direction and topological relations; spatial data models; spatial query languages", } @Article{Lin:1994:TTI, author = "King Ip Lin and H. V. Jagadish and Christos Faloutsos", title = "The {TV}-Tree: An Index Structure for High-Dimensional Data", journal = j-VLDB-J, volume = "3", number = "4", pages = "517--542", month = oct, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:31 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb3.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/f/Faloutsos:Christos.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/j/Jagadish:H=_V=.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/l/Lin:King=Ip.html", abstract = "We propose a file structure to index high-dimensionality data, which are typically points in some feature space. The idea is to use only a few of the features, using additional features only when the additional discriminatory power is absolutely necessary. We present in detail the design of our tree structure and the associated algorithms that handle such `varying length' feature vectors. Finally, we report simulation results, comparing the proposed structure with the $R*$-tree, which is one of the most successful methods for low-dimensionality spaces. The results illustrate the superiority of our method, which saves up to 80\% in disk accesses.", acknowledgement = ack-nhfb, keywords = "query by content; similarity retrieval; spatial index", } @Article{Anonymous:1994:SIS, author = "Anonymous", title = "Special issue on spatial database systems", journal = j-VLDB-J, volume = "3", number = "4", pages = "??--??", month = oct, year = "1994", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:31 MDT 2008", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Constantopoulos:1995:SIB, author = "Panos Constantopoulos and Matthias Jarke and John Mylopoulos and Yannis Vassiliou", title = "The Software Information Base: {A} Server for Reuse", journal = j-VLDB-J, volume = "4", number = "1", pages = "1--43", month = jan, year = "1995", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:32 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb4.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/c/Constantopoulos:Panos.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/j/Jarke:Matthias.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/m/Mylopoulos:John.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/v/Vassiliou:Yannis.html", abstract = "We present an experimental software repository system that provides organization, storage, management, and access facilities for reusable software components. The system, intended as part of an applications development environment, supports the representation of information about requirements, designs and implementations of software, and offers facilities for visual presentation of the software objects. This article details the features and architecture of the repository system, the technical challenges and the choices made for the system development along with a usage scenario that illustrates its functionality. The system has been developed and evaluated within the context of the ITHACA project, a technology integration/software engineering project sponsored by the European Communities through the ESPRIT program, aimed at developing an integrated reuse-centered application development and support environment based on object-oriented techniques.", acknowledgement = ack-nhfb, keywords = "conceptual modeling; information storage and retrieval; object-oriented databases; reuse; software engineering", } @Article{Clifton:1995:HDQ, author = "Chris Clifton and Hector Garcia-Molina and David Bloom", title = "{HyperFile}: {A} Data and Query Model for Documents", journal = j-VLDB-J, volume = "4", number = "1", pages = "45--86", month = jan, year = "1995", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:32 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb4.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/b/Bloom:David.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/c/Clifton:Chris.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/g/Garcia=Molina:Hector.html", abstract = "Non-quantitative information such as documents and pictures pose interesting new problems in the database world. Traditional data models and query languages do not provide appropriate support for this information. Such data are typically stored in file systems, which do not provide the security, integrity, or query features of database management systems. The hypertext model has emerged as a good interface to this information; however, {\em finding\/} information using hypertext browsing does not scale well. We developed a query interface that serves as an extension of the browsing model of hypertext systems. These queries minimize the repeated user interactions required to locate data in a standard hypertext system. HyperFile is a prototype data server interface. In this article, we describe HyperFile, including a number of issues such as query generation, query processing, and indexing.", acknowledgement = ack-nhfb, keywords = "hypertext; indexing; user interface", } @Article{Agrawal:1995:OSL, author = "Divyakant Agrawal and Amr El Abbadi and Richard Jeffers and Lijing Lin", title = "Ordered Shared Locks for Real-Time Databases", journal = j-VLDB-J, volume = "4", number = "1", pages = "87--126", month = jan, year = "1995", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:32 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb4.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/a/Abbadi:Amr_El.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/a/Agrawal:Divyakant.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/j/Jeffers:Richard.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/l/Lin:Lijing.html", abstract = "We propose locking protocols for real-time databases. Our approach has two main motivations: First, locking protocols are widely accepted and used in most database systems. Second, in real-time databases it has been shown that the blocking behavior of transactions in locking protocols results in performance degradation. We use a new relationship between locks called ordered sharing to eliminate blocking that arises in the traditional locking protocols. Ordered sharing eliminates blocking of read and write operations but may result in delayed termination. Since timeliness and not response time is the crucial factor in real-time databases, our protocols exploit this delay to allow transactions to execute within the slacks of delayed transactions. We compare the performance of the proposed protocols with the two-phase locking protocol for real-time databases. Our experiments indicate that the proposed protocols significantly reduce the percentage of missed deadlines in the system for a variety of workloads.", acknowledgement = ack-nhfb, keywords = "concurrency control; time-critical scheduling; transaction management", } @Article{Dan:1995:CDA, author = "Asit Dan and Philip S. Yu and Jen Yao Chung", title = "Characterization of Database Access Pattern for Analytic Prediction of Buffer Hit Probability", journal = j-VLDB-J, volume = "4", number = "1", pages = "127--154", month = jan, year = "1995", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:32 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb4.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/c/Chung:Jen=Yao.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/d/Dan:Asit.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/y/Yu:Philip_S=.html", abstract = "The analytic prediction of buffer hit probability, based on the characterization of database accesses from real reference traces, is extremely useful for workload management and system capacity planning. The knowledge can be helpful for proper allocation of buffer space to various database relations, as well as for the management of buffer space for a mixed transaction and query environment. Access characterization can also be used to predict the buffer invalidation effect in a multi-node environment which, in turn, can influence transaction routing strategies. However, it is a challenge to characterize the database access pattern of a real workload reference trace in a simple manner that can easily be used to compute buffer hit probability. In this article, we use a characterization method that distinguishes three types of access patterns from a trace: (1) locality within a transaction, (2) random accesses by transactions, and (3) sequential accesses by long queries. We then propose a concise way to characterize the access skew across randomly accessed pages by logically grouping the large number of data pages into a small number of partitions such that the frequency of accessing each page within a partition can be treated as equal. Based on this approach, we present a recursive binary partitioning algorithm that can infer the access skew characterization from the buffer hit probabilities for a subset of the buffer sizes. We validate the buffer hit predictions for single and multiple node systems using production database traces. We further show that the proposed approach can predict the buffer hit probability of a composite workload from those of its component files.", acknowledgement = ack-nhfb, keywords = "access skew; analytic prediction; database access characterization; reference trace; sequential access; workload management", } @Article{Peckham:1995:DME, author = "Joan Peckham and Bonnie MacKellar and Michael Doherty", title = "Data Model for Extensible Support of Explicit Relationships in Design Databases", journal = j-VLDB-J, volume = "4", number = "2", pages = "157--191", month = apr, year = "1995", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:33 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb4.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/d/Doherty:Michael.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/m/MacKellar:Bonnie.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/p/Peckham:Joan.html", abstract = "We describe the conceptual model of SORAC, a data modeling system developed at the University of Rhode Island. SORAC supports both semantic objects and relationships, and provides a tool for modeling databases needed for complex design domains. SORAC's set of built-in semantic relationships permits the schema designer to specify enforcement rules that maintain constraints on the object and relationship types. SORAC then automatically generates C++ code to maintain the specified enforcement rules, producing a schema that is compatible with Ontos. This facilitates the task of the schema designer, who no longer has to ensure that all methods on object classes correctly maintain necessary constraints. In addition, explicit specification of enforcement rules permits automated analysis of enforcement propagations. We compare the interpretations of relationships within the semantic and object-oriented models as an introduction to the mixed model that SORAC supports. Next, the set of built-in SORAC relationship types is presented in terms of the enforcement rules permitted on each relationship type. We then use the modeling requirements of an architectural design support system, called ArchObjects, to demonstrate the capabilities of SORAC. The implementation of the current SORAC prototype is also briefly discussed.", acknowledgement = ack-nhfb, keywords = "computer-aided architectural design; database constraints; relationship semantics; semantic and object-oriented data modeling", xxpages = "157--192", } @Article{Teniente:1995:UKB, author = "Ernest Teniente and Antoni Oliv{\'e}", title = "Updating Knowledge Bases While Maintaining Their Consistency", journal = j-VLDB-J, volume = "4", number = "2", pages = "193--241", month = apr, year = "1995", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:33 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb4.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/o/Oliv=eacute=:Antoni.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/t/Teniente:Ernest.html", abstract = "When updating a knowledge base, several problems may arise. One of the most important problems is that of integrity constraints satisfaction. The classic approach to this problem has been to develop methods for {\em checking\/} whether a given update violates an integrity constraint. An alternative approach consists of trying to repair integrity constraints violations by performing additional updates that {\em maintain\/} knowledge base consistency. Another major problem in knowledge base updating is that of {\em view updating}, which determines how an update request should be translated into an update of the underlying base facts. We propose a new method for updating knowledge bases while maintaining their consistency. Our method can be used for both integrity constraints maintenance and view updating. It can also be combined with any integrity checking method for view updating and integrity checking. The kind of updates handled by our method are: updates of base facts, view updates, updates of deductive rules, and updates of integrity constraints. Our method is based on events and transition rules, which explicitly define the insertions and deletions induced by a knowledge base update. Using these rules, an extension of the SLDNF procedure allows us to obtain all possible minimal ways of updating a knowledge base without violating any integrity constraint.", acknowledgement = ack-nhfb, keywords = "integrity checking; integrity maintenance; view updating", } @Article{Guting:1995:RBS, author = "Ralf Hartmut G{\"u}ting and Markus Schneider", title = "Realm-Based Spatial Data Types: The {ROSE} Algebra", journal = j-VLDB-J, volume = "4", number = "2", pages = "243--286", month = apr, year = "1995", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:33 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb4.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/g/G=uuml=ting:Ralf_Hartmut.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/s/Schneider:Markus.html", abstract = "Spatial data types or algebras for database systems should (1) be fully general, that is, closed under set operations, (2) have formally defined semantics, (3) be defined in terms of finite representations available in computers, (4) offer facilities to enforce geometric consistency of related spatial objects, and (5) be independent of a particular DBMS data model, but cooperate with any. We present an algebra that uses {\em realms\/} as geometric domains underlying spatial data types. A realm, as a general database concept, is a finite, dynamic, user-defined structure underlying one or more system data types. Problems of numerical robustness and topological correctness are solved within and below the realm layer so that spatial algebras defined above a realm have very nice algebraic properties. Realms also interact with a DMBS to enforce geometric consistency on object creation or update. The ROSE algebra is defined on top of realms and offers general types to represent point, line, and region features, together with a comprehensive set of operations. It is described within a polymorphic type system and interacts with a DMBS data model and query language through an abstract {\em object model interface.} An example integration of ROSE into the object-oriented data model $O^2$ and its query language is presented.", acknowledgement = ack-nhfb, keywords = "finite resolution; geometric consistency; numerical robustness; object model interface; realm; topological correctness", } @Article{Templeton:1995:IDC, author = "Marjorie Templeton and Herbert Henley and Edward Maros and Darrel J. Van Buer", title = "{InterViso}: Dealing With the Complexity of Federated Database Access", journal = j-VLDB-J, volume = "4", number = "2", pages = "287--317", month = apr, year = "1995", CODEN = "VLDBFR", ISSN = "1066-8888 (print), 0949-877X (electronic)", bibdate = "Mon Jun 23 10:50:33 MDT 2008", bibsource = "http://ftp.informatik.rwth-aachen.de/dblp/db/journals/vldb/vldb4.html; http://portal.acm.org/", note = "Electronic edition.", URL = "http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/b/Buer:Darrel_J=_Van.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/h/Henley:Herbert.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/m/Maros:Edward.html; http://ftp.informatik.rwth-aachen.de/dblp/db/indices/a-tree/t/Templeton:Marjorie.html", abstract = "Connectivity products are finally available to provide the `highways' between computers containing data. IBM has provided strong validation of the concept with their `Information Warehouse.' DBMS vendors are providing gateways into their products, and SQL is being retrofitted on many older DBMSs to make it easier to access data from standard 4GL products and application development systems. The next step needed for data integration is to provide (1) a common data dictionary with a conceptual schema across the data to mask the many differences that occur when databases are developed independently and (2) a server that can access and integrate the databases using information from the data dictionary. In this article, we discuss InterViso, one of the first commercial federated database products. InterViso is based on Mermaid, which was developed at SDC and Unisys (Templeton et al., 1987b). It provides a value added layer above connectivity products to handle views across databases, schema translation, and transaction management.", acknowledgement = ack-nhfb, keywords = "data warehouse; database integration; federated database", xxpages = "287--318", } @Article{Atkinson:1995:SIP, author = "Malcolm P. Atkinson and Ronald Morrison", title = "Special Issue on Persistent Object Systems: Orthogonally Persistent Object Systems", journal = j-VLDB-J, volume = "4", number = "3", pages = "319--401", month = jul, year = "1995", CODEN = "VLDBFR", ISSN = "1066-8888 (pr