An XML-Based Approach to Publishing and Querying the History of Databases

There is much current interest in publishing and viewing databases as XML documents. The general benefits of this approach follow from the popularity of XML and the tool set available for visualizing and processing information encoded in this universal standard. In this paper, we explore the additional and unique benefits achieved by this approach on temporal database applications. We show that XML with XQuery can provide surprisingly effective solutions to the problem of supporting historical queries on past content of database relations and their evolution. Indeed, using XML, the histories of database relations can be naturally represented by temporally grouped data models. Thus, we identify mappings from relations to XML that are most conducive to modeling and querying database histories, and show that temporal queries that would be difficult to express in SQL can be easily expressed in standard XQuery. This approach is very general, insofar as it can be used to store the version history of arbitrary documents and, for relational databases, it also supports queries on the evolution of their schema. Then, we turn to the problem of supporting efficiently the storage and the querying of relational table histories. We present an experimental study of the pros and cons of using native XML databases, versus using traditional databases, where the XML-represented histories are supported as views on the historical tables.     

Modulo Constraints and the Complexity of Typechecking XML Views

The typechecking problem for transformations of relational data into tree data is the following: given a relational-to-XML transformation P, and an XML type d, decide whether for every database instance the result of the transformation P on satisfies d. TreeQL programs with projection-free conjunctive queries (see Alon et al. in ACM Trans. Comput. Log. 4(3):315–354, 2003) are considered as transformations and DTDs with arbitrary regular expressions as XML types. A non-elementary upper bound for the typechecking problem was already given by Alon et al. (ACM Trans. Comput. Log. 4(3):315–354, 2003) (although in a more general setting, where equality and negation in projection-free conjunctive queries and additional universal integrity constraints are allowed). In this paper we show that the typechecking problem is coNEXPTIME-complete. As an intermediate step we consider the following problem, which can be formulated independently of XML notions. Given a set of triples of the form (φ,k,j), where φ is a projection-free conjunctive query and k,j are natural numbers, decide whether there exists a database such that, for each triple (φ,k,j) in the set, there exists a natural number α, such that there are exactly k+j*α tuples satisfying the query φ in . Our main technical contribution consists of a NEXPTIME algorithm for the last problem. Partially supported by Polish Ministry of Science and Higher Education research project N206 022 31/3660, 2006/2009. This paper is an extended version of 20, where the coNEXPTIME upper bound was shown.     

Indexing spatiotemporal archives

Spatiotemporal objects – that is, objects that evolve over time – appear in many applications. Due to the nature of such applications, storing the evolution of objects through time in order to answer historical queries (queries that refer to past states of the evolution) requires a very large specialized database, what is termed in this article a spatiotemporal archive. Efficient processing of historical queries on spatiotemporal archives requires equally sophisticated indexing schemes. Typical spatiotemporal indexing techniques represent the objects using minimum bounding regions (MBR) extended with a temporal dimension, which are then indexed using traditional multidimensional index structures. However, rough MBR approximations introduce excessive overlap between index nodes, which deteriorates query performance. This article introduces a robust indexing scheme for answering spatiotemporal queries more efficiently. A number of algorithms and heuristics are elaborated that can be used to preprocess a spatiotemporal archive in order to produce finer object approximations, which, in combination with a multiversion index structure, will greatly improve query performance in comparison to the straightforward approaches. The proposed techniques introduce a query efficiency vs. space tradeoff that can help tune a structure according to available resources. Empirical observations for estimating the necessary amount of additional storage space required for improving query performance by a given factor are also provided. Moreover, heuristics for applying the proposed ideas in an online setting are discussed. Finally, a thorough experimental evaluation is conducted to show the merits of the proposed techniques. Edited by B. Seeger A short version of this article appeared as “Efficient indexing of spatiotemporal objects” in the Proceedings of Extending Database Technology 2002 [19]. This work was partially supported by NSF grants IIS-9907477, EIA-9983445, NSF IIS 9984729, NSF ITR 0220148, NSF IIS-0133825, NRDRP, and the U.S. Department of Defense.     

An efficient processing of a chain join with the minimum communication cost in distributed database systems

This paper investigates the optimization problem when executing a join in a distributed database environment. The minimization of the communication cost for sending data through links has been adopted as an optimization criterion. We explore in this paper the approach of judiciously using join operations as reducers in distributed query processing. In general, this problem is computationally intractable. A restriction of the execution of a join in a pre-defined combinatorial order leads to a possible solution in polynomial time. An algorithm for a chain query computation has been proposed in [21]. The time complexity of the algorithm isO(m ² n ²+m ³ n), wheren is the number of sites in the network, andm is the number of relations (fragments) involved in the join. In this paper, we firstly present a proof of the intuitively well understood fact—that the eigenorder of a chain join will be the best pre-defined combinatorial order to implement the algorithm in [21]. Secondly, we show a sufficient and necessary condition for a chain query with the eigenordering to be a simple query. For the process of the class of simple queries, we show a significant reduction of the time complexity fromO(m ² n ²+m ³ n) toO(mn+m ²). It is encouraging that, in practice, the most frequent queries belong to the category of simple queries. Editor: Peter Apers     

A meta-index for querying distributed moving object database servers

Distributed moving object database servers offer a feasible solution to the scalability problems of centralized database systems. In these potentially large-scale systems, querying about the time-varying location of specific moving objects can be particularly expensive in terms of running time. This work proposes a meta-index   based strategy that can significantly speed up the processing of these queries. The meta-index acts as an entry point for spatio-temporal queries and quickly drives the search process to the database servers that contain solutions. It also enables very fast approximated solutions to queries such as top-k$k$ and spatio-temporal range queries.     

Nonrecursive incremental evaluation of Datalog queries

We consider the problem of repeatedly evaluating the same (computationally expensive) query to a database that is being updated between successive query requests. In this situation, it should be possible to use the difference between successive database states and the answer to the query in one state to reduce the cost of evaluating the query in the next state. We use nonrecursive Datalog (which are unions of conjunctive queries) to compute the differences, and call this process incremental query evaluation using conjunctive queries. After formalizing the notion of incremental query evaluation using conjunctive queries, we give an algorithm that constructs, for each regular chain query (including transitive closure as a special case), a nonrecursive Datalog program to compute the difference between the answer after an update and the answer before the update. We then extend this result to weakly regular queries, which are regular chain programs augmented with conjunctive queries having the so-called Cartesian-closed increment property, and to the case of unbounded-set insertions where the sets are binary Cartesian products. Finally, we show that the class of conjunctive queries with the Cartesian-closed increment property is decidable.Parts of the results in this paper appeared as extended abstracts in theProceedings of the 1992 International Conference on Database Theory (LNCS 646, Springer-Verlag), and in theProceedings of the 1993 International Workshop on Database Programming Languages (Workshops in Computing, Springer-Verlag).Guozhu Dong gratefully acknowledges support of the Australian Research Council through research grants, and the Centre for Intelligen Decision Systems.Work by Jianwen Su was supported in part by NSF Grants IRI-9109520 and IRI-9117094.     

The nearest common ancestor in a dynamic tree

Summary We consider the problem of determining the nearest common ancestor of two given nodes x and y (denoted by nca(x, y)) in a dynamic arbitrary tree T. We present an implementation of T by a pointer machine which needs linear space, performs m arbitrary insertions and deletions in the initially empty tree T in time O(m) and a query about nca(x, y) can be answered on-line in time O(log(min{depth(x), depth(y))+(k,k))}, where the second factor is amortized over k queries, is a functional inverse of Ackermann's function and depth(x) the distance from node x to the root of T.     

Using differential technlques to efficiently support transaction time

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 cahced 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).     

Active learning for extended finite state machines

We present a black-box active learning algorithm for inferring extended finite state machines (EFSM)s by dynamic black-box analysis. EFSMs can be used to model both data flow and control behavior of software and hardware components. Different dialects of EFSMs are widely used in tools for model-based software development, verification, and testing. Our algorithm infers a class of EFSMs called register automata. Register automata have a finite control structure, extended with variables (registers), assignments, and guards. Our algorithm is parameterized on a particular theory, i.e., a set of operations and tests on the data domain that can be used in guards.Key to our learning technique is a novel learning model based on so-called tree queries. The learning algorithm uses tree queries to infer symbolic data constraints on parameters, e.g., sequence numbers, time stamps, identifiers, or even simple arithmetic. We describe sufficient conditions for the properties that the symbolic constraints provided by a tree query in general must have to be usable in our learning model. We also show that, under these conditions, our framework induces a generalization of the classical Nerode equivalence and canonical automata construction to the symbolic setting. We have evaluated our algorithm in a black-box scenario, where tree queries are realized through (black-box) testing. Our case studies include connection establishment in TCP and a priority queue from the Java Class Library.     

A Theoretical Analysis of Query Selection for Collaborative Filtering

We consider the problem of determining which of a set of experts has tastes most similar to a given user by asking the user questions about his likes and dislikes. We describe a simple algorithm for generating queries for a theoretical model of this problem. We show that the algorithm requires at most opt(F)(ln(|F|/opt(F)) + 1) + 1 queries to find the correct expert, where opt(F) is the optimal worst-case bound on the number of queries for learning arbitrary elements of the set of experts F. The algorithm runs in time polynomial in |F| and |X| (where X is the domain) and we prove that no polynomial-time algorithm can have a significantly better bound on the number of queries unless all problems in NP have n ^{O(log log n)} time algorithms. We also study a more general case where the user ratings come from a finite set Y and there is an integer-valued loss function on Y that is used to measure the distance between the ratings. Assuming that the loss function is a metric and that there is an expert within a distance from the user, we give a polynomial-time algorithm that is guaranteed to find such an expert after at most 2opt(F, ) ln + 2( + 1)(1 + deg(F, )) queries, where deg(F, ) is the largest number of experts in F that are within a distance 2 of any f F.     

The Quantum Black-Box Complexity of Majority

   Abstract. We describe a quantum black-box network computing the majority of N bits with zero-sided error ɛ using only

Partial Evaluation of Views

Many database applications and environments, such as mediation over heterogeneous database sources and data warehousing for decision support, lead to complex queries. Queries are often nested, defined over previously defined views, and may involve unions. There are good reasons why one might want to remove pieces (sub-queries or sub-views) from such queries: some sub-views of a query may be effectively cached from previous queries, or may be materialized views; some may be known to evaluate empty, by reasoning over the integrity constraints; and some may match protected queries, which for security cannot be evaluated for all users.In this paper, we present a new evaluation strategy with respect to queries defined over views, which we call tuple-tagging, that allows for an efficient removal of sub-views from the query. Other approaches to this are to rewrite the query so the sub-views to be removed are effectively gone, then to evaluate the rewritten query. With the tuple tagging evaluation, no rewrite of the original query is necessary.We describe formally a discounted query (a query with sub-views marked that are to be considered as removed), present the tuple tagging algorithm for evaluating discounted queries, provide an analysis of the algorithm's performance, and present some experimental results. These results strongly support the tuple-tagging algorithm both as an efficient means to effectively remove sub-views from a view query during evaluation, and as a viable optimization strategy for certain applications. The experiments also suggest that rewrite techniques for this may perform worse than the evaluation of the original query, and much worse than the tuple tagging approach.     

Structural Recursion as a Query Language on Lists and Ordered Trees

XML query languages need to provide some mechanism to inspect and manipulate nodes at all levels of an input tree. We investigate the expressive power provided in this regard by structural recursion. In particular, we show that the combination of vertical recursion down a tree combined with horizontal recursion across a list of trees gives rise to a robust class of transformations: it captures the class of all primitive recursive queries. Since queries are expected to be computable in at most polynomial time for all practical purposes, we next identify a restriction of structural recursion that captures the polynomial time queries. We also give corresponding results for list-based complex objects. S. Vansummeren is a postdoctoral Fellow of the Research Foundation—Flanders (FWO).     

A Hybrid Fragmentation Approach for Distributed Deductive Database Systems

Fragmentation of base relations in distributed database management systems increases the level of concurrency and therefore system throughput for query processing. Algorithms for horizontal and vertical fragmentation of relations in relational, object-oriented and deductive databases exist; however, hybrid fragmentation techniques based on variable bindings appearing in user queries and query-access-rule dependency are lacking for deductive database systems. In this paper, we propose a hybrid fragmentation approach for distributed deductive database systems. Our approach first considers the horizontal partition of base relations according to the bindings imposed on user queries, and then generates vertical fragments of the horizontally partitioned relations and clusters rules using affinity of attributes and access frequency of queries and rules. The proposed fragmentation technique facilitates the design of distributed deductive database systems. Received 4 August 1999 / Revised 30 March 2000 / Accepted in revised form 6 October 2000     

Query-by-Gaming: Interactive spatio-temporal querying and retrieval using gaming controller

Spatio-temporal querying and retrieval is a challenging task due to the lack of simple user interfaces for building queries despite the availability of powerful indexing structures and querying languages. In this paper, we propose Query-by-Gaming scheme for spatio-temporal querying that can benefit from gaming controller for building queries. By using Query-by-Gaming, we introduce our spatio-temporal querying and retrieval system named as GStar to interactively build subsequent spatio-temporal queries to determine if a state is directly reachable from current state and eventual spatio-temporal queries to know whether a spatial state is reachable from a current state. Queries are built using features of gaming controller by displaying the original video frames rather than on a graphical interface using a mouse or a keyboard. GStar has three main components: building the query, searching and retrieval of clips, and displaying query results. The queries are applied to an indexing structure called semantic sequence state graph (S³G) and results of the query are displayed dynamically to provide timely feedback to the user. Experimental results and user interface are provided for a tennis video database. Users define desired game state (player and ball position) using an interactive interface at multiple points in time and GStar automatically retrieves all rallies that contain both states. Finally, the user interface evaluation comparing gamepad-based interface and mouse interface for spatio-temporal querying has been studied.     

A data structure for arc insertion and regular path finding

Let be the language defined by some deterministick-state automaton with accepting statesF, and letG be a directed graph withn nodes andm labeled arcs. Thedynamic -path problem is to process efficiently and on-line two kinds of operations: (1) inserting arcs intoG, and (2) given two nodesu andv inG, finding a path fromu tov that is labeled by some word of , or reporting that none exists. We present a data structure that supports insertion and regular path existence queries inO(nk ²) amortized time andO(|F|) worst-case time, respectively. Deletions only (no insertions) can also be accommodated in directed acyclic graphs. Finding an -path between two nodes can be done inO(l+|F|) worst-case time, wherel is the length of the path returned. This is an improvement over theO(m) time required to answer queries in the static version of this problem, for each fixed infinite . We show how this data structure and the techniques used for building it are applicable to the area of knowledge base querying. In an amortized setting, we provide relative improvements ofO(m/n) to the time bounds for answering many one-sided recursive queries and even some two-sided recursive queries, such as the same generation query on acyclic graphs.An extended abstract of this paper was presented at the first annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, January 1990.Work partially completed while at Brown University. Work at Princeton partially supported by the NSF Center in Discrete Mathematics and Theoretical Computer Science (DIMACS).Work supported in part by NSF grant IRI-8617344, by an Alfred P. Sloan Foundation Fellowship, and by ONR grant N00014-83-K-0146, ARPA Order No. 4786.Work supported in part by an NSF Presidential Young Investigator Award with matching funds from IBM, by NSF research grant DCR-8403613, and by ONR grant N00014-83-K-0146, ARPA Order No. 4786.     

Tree-based partition querying: a methodology for computing medoids in large spatial datasets

Besides traditional domains (e.g., resource allocation, data mining applications), algorithms for medoid computation and related problems will play an important role in numerous emerging fields, such as location based services and sensor networks. Since the k-medoid problem is NP-hard, all existing work deals with approximate solutions on relatively small datasets. This paper aims at efficient methods for very large spatial databases, motivated by: (1) the high and ever increasing availability of spatial data, and (2) the need for novel query types and improved services. The proposed solutions exploit the intrinsic grouping properties of a data partition index in order to read only a small part of the dataset. Compared to previous approaches, we achieve results of comparable or better quality at a small fraction of the CPU and I/O costs (seconds as opposed to hours, and tens of node accesses instead of thousands). In addition, we study medoid-aggregate queries, where k is not known in advance, but we are asked to compute a medoid set that leads to an average distance close to a user-specified value. Similarly, medoid-optimization queries aim at minimizing both the number of medoids k and the average distance. We also consider the max version for the aforementioned problems, where the goal is to minimize the maximum (instead of the average) distance between any object and its closest medoid. Finally, we investigate bichromatic and weighted medoid versions for all query types, as well as, maximum capacity and dynamic medoids.     

An empirical performance comparison of some variations of thek-d Tree andBD tree

Database applications very often require a sophisticated class of storage structures in order to answer different types of queries efficiently. This often dictates that the file should be organized on multiple keys. Several storage structures have been proposed to satisfy these needs. Most of these are a generalization of the storage structures used for managing one-dimensional data. Thek-d tree is one such example and it is a natural generalization of the standard one-dimensional binary search tree. Recently, a new storage structure, called theBD tree, was proposed to manage multidimensional data. This structure has good dynamic characteristics. Several variations are possible on the basick-d tree structure. This paper studies the performance implications of three variations. Further, it provides an empirical performance comparison of thek-d tree andBD tree in database applications.     

An optimal parallel algorithm for planar cycle separators

We present an optimal parallel algorithm for computing a cycle separator of ann-vertex embedded planar undirected graph inO(logn) time onn/logn processors. As a consequence, we also obtain an improved parallel algorithm for constructing a depth-first search tree rooted at any given vertex in a connected planar undirected graph in O(log² n) time on n/logn processors. The best previous algorithms for computing depth-first search trees and cycle separators achieved the same time complexities, but withn processors. Our algorithms run on a parallel random access machine that permits concurrent reads and concurrent writes in its shared memory and allows an arbitrary processor to succeed in case of a write conflict.A preliminary version of this paper appeared as Improved Parallel Depth-First Search in Undirected Planar Graphs in theProceedings of the Third Workshop on Algorithms and Data Structures, 1993, pp. 407–420.Supported in part by NSF Grant CCR-9101385.