Let G = (V, E, omega) be a simple digraph, in which all edge weights are nonnegative real numbers. Let G' be obtained from G by an application of a set of edge weight updates to G. Let sisinV and let Tsand Ts' be Shortest Path Trees (SPTs) rooted at s in G and G', respectively. The Dynamic Shortest Path (DSP) problem is to compute Ts' from Ts. Existing work on this problem focuses on either a single edge weight change or multiple edge weight changes in which some of them are incorrect or are not optimized. We correct and extend a few state-of-the-art dynamic SPT algorithms to handle multiple edge weight updates. We prove that these algorithms are correct. Dynamic algorithms may not outperform static algorithms all the time. To evaluate the proposed dynamic algorithms, we compare them with the well-known static Dijkstra algorithm. Extensive experiments are conducted with both real-life and artificial data sets. The experimental results suggest the most appropriate algorithms to be used under different circumstances.

We investigate the problem of how to evaluate, fast and efficiently, classes of optimal route queries on a massive graph in a unified framework. To evaluate a route query effectively, a large network is partitioned into a collection of fragments, and distances of some optimal routes in the network are pre-computed. Under such a setting, we find a unified algorithm that can evaluate classes of optimal route queries. The classes that can be processed efficiently are called constraint preserving (CP) which include, among others, shortest path, forbidden edges, forbidden nodes and α-autonomy optimal route query classes. We prove the correctness of the unified algorithm. We then turn our attention to the optimization of the proposed algorithm. Several pruning and optimization techniques are derived that minimize the search time and I/O accesses. We show empirically that these techniques are effective. The proposed optimal route query evaluation algorithm, with all these techniques incorporated, is compared with a main-memory and a disk-based brute-force CP algorithms. We show experimentally that the proposed unified algorithm outperforms the brute-force algorithms, both in term of CPU time and I/O cost, by a wide margin.

A class of commonly asked queries in a spatial database is known as buffer queries. An example of such a query is to "find house-power line pairs that are within 50 meters of each other." A buffer query involves two spatial data sets and a distance d. The answer to this query are pairs of objects, one from each input set, that are within distance d of each other. Given nonpoint spatial objects, evaluation of buffer queries could be a costly operation, even when the numbers of objects in the input data sets are relatively small. This paper addresses the problem of how to evaluate this class of queries efficiently. A fundamental problem with buffer query evaluation is to find an efficient algorithm for solving the minimum distance (miniDist) problem for lines and regions. An efficient minDist algorithm, which only requires a subsequence of segments from each object to be examined, is derived. Finding a fast minDist algorithm is the first step in evaluating a buffer query efficiently. It is observed that many, and sometimes even most, candidates can be proven in the answer without resorting to the relatively expensive minDist operation. A candidate is first evaluated with a least expensive technique-called O-object filtering. If it fails, a more costly operation, called 1-object filtering, is applied. Finally, if both filterings fail, the most expensive minDist algorithm is invoked. To show the effectiveness of the these techniques, they are incorporated into the well-known tree join algorithm and tested with real-life as well as artificial data sets. Extensive experiments show that the proposed algorithm outperforms existing techniques by a wide margin in both execution time as well as IO accesses. More importantly, the performance gain improves drastically with the increase of distance values.

Consider a geographic information system (GIS) which is set up as a Web server that allows users to query the database with a Web browser. As the query result may be huge and the network delay could be significant, we investigate the fundamental problem of how to deliver the query result efficiently over the network . In a conventional client-server database system, the commonly used application programming interface (API) is the so-called iterator-based interface in which a client queries the server with an ISQL statement and the result, which is called a result or active set, is generated. To retrieve the query result, multiple calls are made to the server and objects in the result set are retrieved sequentially. To enhance system performance, objects in a result set can also be retrieved in bulk by storing them in an array. In the Web environment, a database server is commonly implemented with a distributed object technology such as Java or CORBA. As network delay could be significant and the client memory spaces are limited and varying, neither multiple calls nor bulk-retrieval is a viable solution to this problem. We propose a technique by caching and piping the result set through a socket connection without forfeiting the iterator-based interface. We show that the proposed method is superior in delivering a query result in a LAN and in the Web environment. We then investigate how to retrieve and display geometric data in a map efficiently in a network environment.

In the optimization of queries in an object-oriented database (OODB) system, a natural first step is to use the typing constraints imposed by the schema to transform a query into an equivalent one that logically accesses a minimal set of objects. We study a class of queries for OODBs called conjunctive queries. Variables in a conjunctive query range over heterogeneous sets of objects. Consequently, a conjunctive query is equivalent to a union of conjunctive queries of a special kind, called terminal conjunctive queries. Testing containment is a necessary step in solving the equivalence and minimization problems. We first characterize the containment and minimization conditions for the class of terminal conjunctive queries. We then characterize containment for the class of all conjunctive queries and derive an optimization algorithm for this class. The equivalent optimal query produced is expressed as a union of terminal conjunctive queries, which has the property that the number of variables as well as their search spaces are minimal among all unions of terminal conjunctive queries. Finally, we investigate the complexity of the containment problem. We show that it is complete in $\Pi^{p}_{2}$.

The fundamental problem that arises when a ground atom in a disjunctive database is assumed false is discussed. There are basically two different approaches for inferring negative information for disjunctive databases: J. Minker's (1982) generalized closed world assumption (GCWA) and K.A. Ross and R.W. Topor's (1988) disjunctive database rule (DDR). It is argued that neither approach is satisfactory. A database semantics called PWS is proposed. It is shown that for propositional databases with no negative clauses, the problem of determining if a negative ground literal is inferred under the GCWA is co-NP-hard, while the same problem can be solved efficiently under the DDR and PWS. However, in the general case, the problem becomes co-NP-complete for the DDR and PWS. Relationships among GCWA, DDR, and PWS are highlighted. In general, disjunctive clauses are interpreted inclusively under the DDR and unpredictably under the GCWA.>

With the availability of high-level declarative query languages in an object-oriented database system (OODB), the burden of choosing an efficient execution plan for a query is transferred from the user to the database system. A natural first step is to use the typing constraints imposed by the schema to transform a query into an equivalent one that logically accesses a minimal set of objects. We propose a class of queries called conjunctive queries for OODB's. A conjunctive query can be expressed as an equivalent union of queries in a special form called terminal conjunctive queries. We first characterize the containment, and hence equivalence, conditions for the class of terminal conjunctive queries. We then study a subclass of conjunctive queries called positive conjunctive queries. We characterize the containment and equivalence conditions, as well as derive an algorithm for finding an exact minimization for the class of positive conjunctive queries. The equivalent minimized query is expressed as a union of terminal positive conjunctive queries with the property that the variable search space is minimal among all the unions of postivie conjunctive queries.

A generahzatlon of Sagiv-independent database schemes, called (key-equivalent) independence-reducible schemes, is defined, and it is shown that it 1s highly desirable with respect to query answering and constraint enforcement.By showing that they are bounded and algebraic-maintamable the desirabdlties are proven.The class of independence-reducible schemes M exactly the class of schemes obtained from decomposing relation schemes in a Sagwmdependent scheme in a dependency preserving manner.Todemonstrate theclass ofschemes identified is rather general.itisprovedthatlt contains all prewously known classes of dependency preserving BCNF database schemes with similar properties.An efficient algorlthm is found which recognizes exactly this class of database schemes.Independence-reducible database schemes contain a class of constant-time-maintamable database schemes.A condition is found which characterizes this class of schemes and the condition can be tested efficiently.Throughout, it is assumed that a cover of the functional dependencies is embedded m a database scheme in the form of key dependencies.

The maintenance problem (for database states) ofa database scheme Rwithrespect toa set of functional dependencies Fisthefollowing decision problem.Letrbea consistent state of Rwith respect to F and assume we insert a tuple t into rP~r.Is r U {t}a consistent state of R with respect to F? R is said to be constant-time-maintainable with respect to F if there is an algorithm that solves the maintenance problem of R with respect to F in time independent of the state size.A characterization of constant-time-maintainability for the class of BCNF database schemes is given.Inefficient algorithm that tests this characterization is shown, as well as an algorithm for solving the maintenance problem in time independent of the state size.It is also shown that total projections of the representative instance can be computed via unions of projections of sequential extension joins.Throughout we assume that database schemes are dependency preserving and BCNF, and that functional dependencies are given intheform of key dependencies.

A theory is proposed for designing database schemes that are free of update anomalies. Unlike previous approaches, insertion and deletion anomalies are investigated in the context of a relation scheme, while replacement anomalies are studied in the context of a database scheme. Two simple models are developed for analyzing when a relation scheme is free of insertion and deletion anomalies. Techniques are also proposed for obtaining desirable decompositions that are free of insertion and deletion anomalies. A class of database schemes that is free of replacement anomalies is also proposed. This class of schemes is highly desirable with respect to constraint enforcement when attribute values of some tuple are being changed. By making different assumptions on the modifiable attributes, several important classes of database schemes that are free of replacement anomalies are characterized. Throughout, we assume update operations are performed on relation schemes at the conceptual level.

Simple chase join expressions are relational algebra expressions, involving only projection and join operators, defined on the basis of the functional dependencies associated with the database scheme. They are meaningful in the weak instance model, because for certain classes of schemes, including independent schemes, the total projections of the representative instance can be computed by means of unions of simple chase join expressions. We show how unions of simple chase join expressions can be optimized efficiently, without constructing and chasing the corresponding tableaux. We also present efficient algorithms for testing containment and equivalence, and for optimizing individual simple chase join expressions.

A class of cover embedding database schemes, called independence-reducible, is proposed and is proven to be bounded and algebraic-maintainable, and therefore is highly desirable with respect to query answering and constraint enforcement. This class of schemes is shown to properly contain a superset of all previously known classes of cover embedding BCNF database schemes which are bounded (and constant-time-maintainable). An efficient algorithm is found which recognizes exactly this class of database schemes. Independence-reducible database schemes properly contain a class of constant-time-maintainable database schemes and a condition which characterizes this class of schemes is found, this condition can be tested efficiently. Throughout, it is assumed that a cover of the functional dependencies is embedded in the database scheme in the form of key dependencies.

The maintenance problem (for database states) of a database scheme R with respect to a set of functional dependencies F is the following decision problem. Let r be a consistent state of R with respect to F and assume we insert a tuple t into rp ε r. Is r ∪ {t} a consistent state of R with respect to F? R is said to be constant-time-maintainable with respect to F if there is an algorithm that solves the maintenance problem of R with respect to F in time independent of the state size.

Under the weak instance model, to determine if a class of database schemes is bounded with respect to dependencies is fundamental for the analysis of the behavior of the class of database schemes with respect to query processing and updates. However, proving that a class of database schemes is bounded with respect to dependencies seems to be very difficult even for restricted cases. To resolve this problem, we need to develop techniques for characterizing bounded database schemes

It has been observed that, for some database schemes, users may have difficulties retrieving correct information, even for simple queries. The problem occurs when some implicit “piece” of information, defined on some subset of a relation scheme, is not explicitly represented in the database state. In this situation, users may be required to know how the state and the constraints interact before they can retrieve the information correctly. In this paper, the formal notion of embedded-completeness is proposed, and it is shown that schemes with this property avoid the problem described above. A polynomial-time algorithm is given to test whether a database scheme is independent and embedded-complete. Under the assumption of independence, it is shown that embedded-complete schemes allow efficient computation of optimal relational algebra expressions equivalent to the X -total projection, for any set of attributes X .

We propose and investigate the notion of separability to capture the design goal of independently updatable decompositions. We characterize separable schemes in the important case when the only constraints given are a set of functional dependencies and the join dependency $\bowtie {\bf R}$. This characterization is also applicable to cover embedding database schemes when a set of functional dependencies is given as constraint. As evidence in favor of separability as a natural concept of independence, we show that it is equivalent to a specialization of the abstract independent mappings defined by Bancilhon and Spyratos. Our characterization yields a polynomial-time algorithm for testing separability in these cases.

In this paper, we present an Ο(n log n) algorithm for finding the minimum Euclidean visible vertex distance between two nonintersecting simple polygons, where n is the number of vertices in a polygon. The algorithm is based on applying a divide and conquer method to two preprocessed facing boundaries of the polygons. We also derive an Ο(n log n) algorithm for finding a minimum sequence of separating line segments between two nonintersecting polygons.

We propose a class of database schemes called connection-trap-lree schemes that allows users to retrieve sound and complete information easily and efficiently from the database.We argue that with this class of database schemes, the connection trap problem can be avoided.We present 'some fundamental properties of this class of schemes.We then characterize the class 01 independent and connection-trapfree schemes when an embedded cover of functional dependencies is assumed.

Article Free Access Share on Efficient query answering in the representative instance approach Authors: Paolo Atzeni View Profile , Edward P. F. Chan View Profile Authors Info & Claims PODS '85: Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1985 Pages 181–188https://doi.org/10.1145/325405.325429Published:25 March 1985Publication History 19citation68DownloadsMetricsTotal Citations19Total Downloads68Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The representative instance has been proposed as a query answering device in systems using the Universal Relation Interface. One approach is to use the total projections of the representative instance to generate the answer for a query. Associated with this approach is the problem of how to generate the total projections of the representative instance efficiently. We propose a generalization of extension joins, called chase join expressions, as a means to compute the total projections when functional dependencies are given as constraints. In particular, we identify an important subclass of chase join expressions called simple chase join expressions and show that the total projections with respect to a set of functional dependencies can be computed by unions of simple chase join expressions when an independent scheme is assumed. We also find a simple and efficient algorithm that minimizes the number of join operations in a union of simple chase join expressions.

We propose and investigate the notion of separability to capture the design goal of independently updatable decompositions. As evidence in favor of separability as a natural concept of independence, we show that it is equivalent to a specialization of the abstract independent mappings defined by Bancilhon and SpyraLos. We then enaracterize separable schemes in the important case when the only constraints given are a set of functional dependencies and the join dependency for the database scheme. This characterization is also applicable to dependency preserving database schemes when a set of functional dependencies is given as constraint. Our characterization yields a polynomial-time algorithm for testing separability in these cases.