In the last few years the amount of available spatial data has increased both in volume and in heterogeneity, so that dealing with this huge amount of information has become an interesting new research challenge. In particular, spatial data are usually represented through a vector model upon which several spatial relations have been defined. Such relations represent the basic tools for querying and manipulating spatial data and their robust evaluation in a distributed heterogeneous environment is an important issue to consider for allowing the effective usage of these data. Among all possible spatial relations, this paper considers the topological ones, since they are generally provided by all existing systems and represent the building blocks for the implementation of other spatial relations. The conditions and the operations needed to make a dataset robust w.r.t. topological interpretations strictly depends on the adopted evaluation model. This paper considers an environment where two different evaluation models for topological relations exist, one in which equality is based on the identity of geometric primitives, and the other one where a tolerance in equality evaluation is introduced. Given such premises, the paper proposes a set of rules for guaranteeing the robustness in both models, and discusses the applicability of available algorithms of the Snap Rounding family, in order to preserve robustness in case of perturbations.

Topological relationships between geometric objects are important in several spatial applications, like spatial query evaluation, spatial integrity constraints checking, and spatial reasoning. Although the conceptual aspects of topological relationships between geometric objects embedded in the Euclidean space have been extensively studied, the problems arising when topological relationships are evaluated on real data have been much less explored. In particular, robustness problems arise in the evaluation of topological relationships between geometric objects implemented as vectors in a discrete space. A lack of robustness is characterized by the fact that different systems can produce different evaluations of topological relationships on the same data, and it is caused by the fact that coordinates are represented as finite numbers. The goal of this paper is to formally analyze some rules for increasing the robustness of a topological relationship evaluation and to give some examples w.r.t. a specific topological relationship.

The spatial data community recognizes the need for procedures that automatically validate spatial integrity constraints defined at conceptual level. This validation becomes particularly important in an open and distributed environment, like a Spatial Data Infrastructure (SDI), where the level of integration and interoperability is very high. However, the current gap between the conceptual design of a spatial database and its implementation into a GIS system makes the definition of spatial constraints useful only for documentation purposes and not for automatic validation. The GeoUML modeling language provides a set of predefined OCL templates for expressing the most common spatial constraints. In this paper, we deal with the validation problem by proposing a methodology for automatically translating the OCL constraints of GeoUML into SQL spatial queries, thus obtaining a platform independent general validation tool.

The authors describe how the characteristics of an object-oriented data model, such as object identity, complex object structure, methods, and class hierarchies, have an impact on the design of a query language. They also point out major differences with respect to relational query languages. The discussion is supported through the definition of OOPC, a formal object-oriented query language based on predicate calculus, which incorporates in a consistent formal notation most features of existing object-oriented query languages.>

This paper describes a new algorithm for performing joins in the absence of access paths.This algorithm is shown to perform better than the Merging Scan algorithm, which can be considered the paradigm of join algorithms.Finally this algorithm is compared with another recent sub-soti-merge algorithm.

The semantics of SQL queries is formally defined by stating a set of rules that determine a syntax-driven translation of an SQL query to a formal model. The target model, called Extended Three Valued Predicate Calculus (E3VPC), is largely based on a set of well-known mathematical concepts. The rules which allow the transformation of a general E3VPC expression to a Canonical Form, which can be manipulated using traditional, two-valued predicate calculus are also given; in this way, problems like equivalence analysis of SQL queries are completely solved. Finally, the fact that reasoning about the equivalence of SQL queries using two-valued predicate calculus, without taking care of the real SQL semantics can lead to errors is shown, and the reasons for this are analyzed.

A query language should both rely safely on formal logic and suggest, with its syntax, the correct interpretation. This paper shows that a syntactic construct of SQL, which allows the expression of queries involving universal quantification of tuple-variables, does not satisfy the above requirement and suggests how the construct could be modified in order to avoid wrong interpretations.

A major requirement of a Distributed DataBase Management System (DDBMS) is to enable users to write queries as though the database were not distributed (distribution transparency). The DDBMS transforms the user's queries into execution strategies, that is, sequences of operations on the various nodes of the network and of transmissions between them. An execution strategy on a distributed database is correct if it returns the same result as if the query were applied to a nondistributed database. This paper analyzes the correctness problem for query execution strategies. A formal model, called Multirelational Algebra, is used as a unifying framework for this purpose. The problem of proving the correctness of execution strategies is reduced to the problem of proving the equivalence of two expressions of Multirelational Algebra. A set of theorems on equivalence is given in order to facilitate this task. The proposed approach can be used also for the generation of correct execution strategies, because it defines the rules which allow the transformation of a correct strategy into an equivalent one. This paper does not deal with the problem of evaluating equivalent strategies, and therefore is not in itself a proposal for a query optimizer for distributed databases. However, it constitutes a theoretical foundation for the design of such optimizers.

In this paper the problem of horizontally partitioning data on a set of resources is considered.The main optimization parameter is the number of accesses performed by the application programs to different portions of data. The concepts which are required for the determination of relevant portions of data are defined and a methodology for determining the access parameters is proposed.The formulation of the general partitioning problem in 3 specific application environments is shown: distributed database design, file partitioning on a primary and a secondary memory and data distribution on different devices.It is shown that the analytical models of these specific applications use the parameters of the general formulation.

A model is developed for allocating the operations which are required by a transaction on a distributed database. The model considers the possibility of performing each operation distributedly, i.e., as a set of partial operations performed on different nodes. The criterion of optimality is the minimization of transmission costs. The model is formulated as a linear integer zero-one program. An example is given which shows the use of the model and the advantages of distributed operations.

The problem of designing global applications in a Distributed Database is considered, and a multilevel model is developed in order to evaluate different access strategies. File manipulation operations are considered with respect to their possibility of distributed execution and their transmission requirements are defined. The need of an analysis of data is shown in order to quantitatively evaluate costs and delays of transmission operations.

The purpose of this paper is to analyze the problem of mapping between different levels of a data base.A data Base is viewed as an Abstract Object upon which it is possible to operate with a given set of operations, the result of which depends both on the "type" of the object and on its state.Following this approach and utilizing some algebraic formalism we analyze the mappings between external views of a data base and the conceptual view of the data base itself. The main result is a requirement on the consistency between the process of deriving an external view from the conceptual view and the translation of external (user) operations into conceptual operations.It is also shown that this requirement is not sufficient to characterize the "interference" arising from a shared use of a Data Base.Informal and formal examples illustrating these concepts are given.