%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "1.18",
%%% date = "24 June 2008",
%%% time = "06:34:26 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 = "02511 16915 93446 935161",
%%% 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.18, 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 ( 42)
%%% 1997 ( 22) 2003 ( 23)
%%%
%%% Article: 392
%%%
%%% Total entries: 392
%%%
%%% 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