Uncertain deductive databases: A hybrid approach

Uncertainty in deductive databases and logic programming has been modeled using a variety of (numeric and non-numeric) formalisms in the past, including probabilistic, possibilistic, and fuzzy set-theoretic approaches, and many valued logic programming. In this paper, we consider a hybrid approach to the modeling of uncertainty in deductive databases. Our model, called deductive IST (DIST) is based on an extension of the Information Source Tracking (IST) model, recently proposed for relational databases. The DIST model permits uncertainty to be modeled and manipulated in essentially qualitative terms with an option to convert qualitative expressions of uncertainty into numeric form (e.g., probabilities). An uncertain deductive database is modeled as a Horn clause program in the DIST framework, where each fact and rule is annotated with an expression indicating the “sources” contributing to this information and their nature of contribution. (1) We show that positive DIST programs enjoy the least model/least fixpoint semantics analogous to classical logic programs. (2) We show that top-down (e.g., SLD-resolution) and bottom-up (e.g., magic sets rewriting followed by semi-naive evaluation) query processing strategies developed for datalog can be easily extended to DIST programs. (3) Results and techniques for handling negation as failure in classical logic programming can be easily extended to DIST. As an illustration of this, we show how stratified negation can be so extended. We next study the problem of query optimization in such databases and establish the following results. (4) We formulate query containment in qualitative as well as quantitative terms. Intuitively, our qualitative sense of containment would say a query Q₁ is contained in a query Q₂ provided for every input database D, for every tuple t, t ε Q₂(D) holds in every “situation” in which t ε Q₁(D) is true. The quantitative notion of containment would say Q₁ is contained in Q₂ provided on every input, the certainty associated with any tuple computed by Q₁ is no more than the certainty associated with the same tuple by Q₂ on the given input. We also prove that qualitative and quantitative notions of containment (both absolute and uniform versions) coincide. (5) We establish necessary and sufficient conditions for the qualitative containment of conjunctive queries. (6) We extend the well-known chase technique to develop a test for uniform containment and equivalence of positive DIST programs. (7) Finally, we prove that the complexity of testing containment of conjunctive DIST queries remains the same as in the classical case when number of information sources is regarded as a constant (so, it's NP-complete in the size of the queries). We also show that testing containment of conjunctive queries is co-NP-complete in the number of information sources.     

Identification of partial disjunction, parity, and threshold functions

Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify “efficiently” a Boolean function g out of F by asking for the value of g at chosen inputs, where “efficiency” is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries.     

Modelling topological spatial relations: Strategies for query processing

This paper investigates the processing of spatial queries with topological constraints, for which current database solutions are inappropriate. Topological relations, such as disjoint, meet, overlap, inside, and contains, have been well defined by the 9-intersection, a comprehensive model for binary topological relations. We focus on two types of queries: (1) “Which objects have a stated topological relation with a given spatial object?” and (2) “What is the topological relation between two given spatial objects?” Such queries are processed at two levels of detail. First, Minimum Bounding Rectangles are used as an approximation of the objects' geometry and as a means of identifying candidates that might satisfy the query. Next, the nine intersections that determine the topological relations between candidate pairs are calculated. We present algorithms for minimizing these computations. Considerable performance can be gained by exploiting the semantics of spatial relations. We also compare the approach for a naive cost model, which assumes that all relations have the same frequency of occurrence, with a refined cost model, which considers the probability of occurrence of the topological relations. The strategies presented here have three key benefits: (1) they are based on a well-defined formalism; (2) they are customizable; and (3) they can take into account important statistical information about the data.     

Negation as failure: Careful closure procedure

The aim of this paper is a modification of Minker's Generalized Closed World Assumption that would allow application of the “negation as failure rule” with respect to a set P of (not necessarily all) predicates of a database DB. A careful closure procedure is introduced which, when applied to a database DB, produces a new database DB*, that is used to answer queries about predicates from DB. It is shown that DB* is consistent iff DB is consistent. If P is the set of all predicates from DB and DB does not contain functional symbols, then DB* coincides with Minker's GCWA. The soundness and completeness of the careful closure procedure with respect to a minimal model style semantic is shown. As an inference engine associated with DB* we propose a query evaluation procedure QEP* which is a combination of a method of splitting an indefinite database DB into a disjunction of Horn databases and Clark's query evaluation procedure QEP. Soundness of QEP* with respect to DB* is shown for a broad class of databases.     

Similarity-based ranking and query processing in multimedia databases

Since media-based evaluation yields similarity values, results to a multimedia database query, Q(Y₁,…,Y_n), is defined as an ordered list S_Q of n-tuples of the form X₁,…,X_n. The query Q itself is composed of a set of fuzzy and crisp predicates, constants, variables, and conjunction, disjunction, and negation operators. Since many multimedia applications require partial matches, S_Q includes results which do not satisfy all predicates. Due to the ranking and partial match requirements, traditional query processing techniques do not apply to multimedia databases. In this paper, we first focus on the problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, providing the user with a meaningful final ranking”. More specifically, we study the problem of merging similarity values in queries with multiple fuzzy predicates. We describe the essential multimedia retrieval semantics, compare these with the known approaches, and propose a semantics which captures the requirements of multimedia retrieval problem. We then build on these results in answering the related problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, finding an efficient way to process the query.” We develop an algorithm to efficiently process queries with unordered fuzzy predicates (sub-queries). Although this algorithm can work with different fuzzy semantics, it benefits from the statistical properties of the semantics proposed in this paper. We also present experimental results for evaluating the proposed algorithm in terms of quality of results and search space reduction.     

Round-Eye: A system for tracking nearest surrounders in moving object environments

This paper presents “Round-Eye”, a system for tracking nearest surrounding objects (or nearest surrounders) in moving object environments. This system provides a platform for surveillance applications. The core part of this system is continuous nearest surrounder (NS) query that maintains views of the nearest objects at distinct angles from query points. This query differs from conventional spatial queries such as range queries and nearest neighbor queries as NS query considers both distance and angular aspects of objects with respect to a query point at the same time. In our system framework, a centralized server is dedicated (1) to collect location updates of both objects and queries, (2) to determine which NS queries are invalidated in presence of object/query location changes and corresponding result changes if any, and (3) to refresh the affected query answers. To enhance the system performance in terms of processing time and network bandwidth consumption, we propose various techniques, namely, safe region, partial query reevaluation, and incremental query result update. Through simulations, we evaluate our system with the proposed techniques over a wide range of settings.     

Applying simple theory of types to data bases

Whereas the logical apparatus used for formulation and solution of problems connected with the data base systems is mostly a 1st order logic, here a modified version (“T-system”) of Church's simple theory of types is used. It is shown that the T-system

1. (a) is a more adequate tool for analyzing natural language, which may be important when one builds up an abstract model of a fragment of reality and when one creates a suitable philosophy of data base systems;

2. (b) has greater expressive power than the 1st order systems, which enables, e.g. to distinguish between queries according to what is the structure of the required answer, and moreover, not to be restricted by the well-known limitations of the 1st order logics;

3. (c) is based on the notion of function as on the most fundamental notion, which makes it possible to deal more directly with functional dependencies and to exploit more universally the key importance of the attribute concept;

4. (d) by using the concept of construction offers a good tool for E-C mapping and for forming query languages that are more universal than the current ones.

The analysis of these properties of the T-system is accompanied by examples from the area of the data base systems theories; especially, a comparison with Codd's domain relational calculus and with Chen's and Pirotte's approaches is made. No problem of implementation is touched in this paper.     

An efficient workload-based data layout scheme for multidimensional data

Physical data layout is a crucial factor in the performance of queries and updates in large data warehouses. Data layout enhances and complements other performance features such as materialized views and dynamic caching of aggregated results. Prior work has identified that the multidimensional nature of large data warehouses imposes natural restrictions on the query workload. A method based on a “uniform” query class approach has been proposed for data clustering and shown to be optimal. However, we believe that realistic query workloads will exhibit data access skew. For instance, if time is a dimension in the data model, then more queries are likely to focus on the most recent time interval. The query class approach does not adequately model the possibility of multidimensional data access skew. We propose the affinity graph model for capturing workload characteristics in the presence of access skew and describe an efficient algorithm for physical data layout. Our proposed algorithm considers declustering and load balancing issues which are inherent to the multidisk data layout problem. We demonstrate the validity of this approach experimentally.     

Multi-perspective Navigation of Movies

Digital libraries of video are rapidly growing in size and availability through digital networks of computers. The explosion of digital unstructure information, such as video, traveling through the network raises the need for tools that allow video information structuring and “intelligent” access to sequences.In this paper we present a novel video database system, which has been expressly designed to support structured storage of movies. A semiotic formalization for movie logical organization is here introduced and exploited to derive the conceptual schema of an object-oriented movie database. This structure is expressly tailored to enable queries on film technical features and on semantic contents as well, thus allowing feature fusion and access from multiple perspectives. A novel visual interaction scheme is implemented that allows users to formulate queries as filtering operations, that enable focussing on the interesting part of information, while skipping the rest. Formalization of the operators of “perspective” and “filtering” is thereby supplied. Retrieval of stored sequences by iconic motion example is also implemented for accessing sequences by contents. Examples are supplied of interaction with the database and of expressive power of visual query language.     

Query processing over object views of relational data

This paper presents an approach to object view management for relational databases. Such a view mechanism makes it possible for users to transparently work with data in a relational database as if it was stored in an object-oriented (OO) database. A query against the object view is translated to one or several queries against the relational database. The results of these queries are then processed to form an answer to the initial query. The approach is not restricted to a ‘pure’ object view mechanism for the relational data, since the object view can also store its own data and methods. Therefore it must be possible to process queries that combine local data residing in the object view with data retrieved from the relational database. We discuss the key issues when object views of relational databases are developed, namely: how to map relational structures to sub-type/supertype hierarchies in the view, how to represent relational database access in OO query plans, how to provide the concept of object identity in the view, how to handle the fact that the extension of types in the view depends on the state of the relational database, and how to process and optimize queries against the object view. The results are based on experiences from a running prototype implementation. Edited by: M.T. ?zsu. Received April 12, 1995 / Accepted April 22, 1996     

Finding hidden independent sets in interval graphs

We design efficient competitive algorithms for discovering hidden information using few queries. Specifically, consider a game in a given set of intervals (and their implied interval graph G) in which our goal is to discover an (unknown) independent set X by making the fewest queries of the form “Is point p covered by an interval in X?” Our interest in this problem stems from two applications: experimental gene discovery with PCR technology and the game of Battleship (in a 1-dimensional setting). We provide adaptive algorithms for both the verification scenario (given an independent set, is it X?) and the discovery scenario (find X without any information). Under some assumptions, these algorithms use an asymptotically optimal number of queries in every instance.     

Semantic data modelling and visualisation using Noetica

Noetica is a tool for structuring knowledge about concepts and the relationships between them. It differs from typical information systems in that the knowledge it represents is abstract, highly connected, and includes meta-knowledge (knowledge about knowledge). Noetica represents knowledge using a strongly typed graph data model. By providing a rich type system it is possible to represent conceptual information using formalised structures. A class hierarchy provides a basic classification for all objects. This allows for a consistency of representation that is not often found in “free” semantic networks, and gives the ability to easily extend a knowledge model while retaining its semantics.

Visualisation and query tools are provided for this data model. Visualisation can be used to explore complete sets of link-classes, show paths while navigating through the database, or visualise the results of queries. Noetica supports goal-directed queries (a series of user-supplied goals that the system attempts to satisfy in sequence) and pathfinding queries (where the system finds relationships between objects in the database by following links).     

Automatically maintaining navigation sequences for querying semi-structured web sources

A substantial subset of Web data has an underlying structure. For instance, the pages obtained in response to a query executed through a Web search form are usually generated by a program that accesses structured data in a local database, and embeds them into an HTML template. For software programs to gain full benefit from these “semi-structured” Web sources, wrapper programs must be built to provide a “machine-readable” view over them. Since Web sources are autonomous, they may experience changes that invalidate the current wrapper, thus automatic maintenance is an important issue. Wrappers must perform two tasks: navigating through Web sites and extracting structured data from HTML pages. While several works have addressed the automatic maintenance of data extraction tasks, the problem of maintaining the navigation sequences remains unaddressed to the best of our knowledge. In this paper, we propose a set of novel techniques to fill this gap.     

ArchIS: an XML-based approach to transaction-time temporal database systems

Effective support for temporal applications by database systems represents an important technical objective that is difficult to achieve since it requires an integrated solution for several problems, including (i) expressive temporal representations and data models, (ii) powerful languages for temporal queries and snapshot queries, (iii) indexing, clustering and query optimization techniques for managing temporal information efficiently, and (iv) architectures that bring together the different pieces of enabling technology into a robust system. In this paper, we present the ArchIS system that achieves these objectives by supporting a temporally grouped data model on top of RDBMS. ArchIS’ architecture uses (a) XML to support temporally grouped (virtual) representations of the database history, (b) XQuery to express powerful temporal queries on such views, (c) temporal clustering and indexing techniques for managing the actual historical data in a relational database, and (d) SQL/XML for executing the queries on the XML views as equivalent queries on the relational database. The performance studies presented in the paper show that ArchIS is quite effective at storing and retrieving under complex query conditions the transaction-time history of relational databases, and can also assure excellent storage efficiency by providing compression as an option. This approach achieves full-functionality transaction-time databases without requiring temporal extensions in XML or database standards, and provides critical support to emerging application areas such as RFID.     

A new approach for fuzzy information retrieval based on weighted power-mean averaging operators

An information retrieval system can help users to retrieve documents relevant to the users’ queries. In recent years, some researchers used averaging operators (i.e., Infinite–One operators, Waller–Kraft operators, P-Norm operators and GMA operators) to handle “AND” and “OR” operations of users’ fuzzy queries for fuzzy information retrieval, but they still have some drawbacks, e.g., sometimes query results do not coincide with the intuition of the human being. In this paper, we present new averaging operators, called weighted power-mean averaging (WPMA) operators, based on the weighted power mean for dealing with fuzzy information retrieval to overcome the drawbacks of the existing methods. Furthermore, we also extend the proposed WPMA operators into the extended WPMA operators to handle weighted fuzzy queries for fuzzy information retrieval. The proposed WPMA operators are more flexible and more intelligent than the existing averaging operators to handle users’ fuzzy queries for fuzzy information retrieval.     

A heuristic index for selecting similar categories in multiple correspondence analysis applied to living donor kidney transplantation

This work introduces a heuristic index (the “tolerance distance”) to define the “closeness” of two variable categories in multiple correspondence analysis (MCA). This index is a weighted Euclidean distance where weightings are based on the “importance” of each MCA axis, and variable categories were considered to be associated when their distances were below the tolerance distance. This approach was applied to a renal transplantation data. The analysed variables were allograft survival and 13 of its putative predictors. A bootstrap-based stability analysis was employed for assessing result reliability. The method identified previously detected associations within the database, such as that between race of donors and recipients, and that between HLA match and Cyclosporine use. A hierarchical clustering algorithm was also applied to the same data, allowing for interpretations similar to those based on MCA. The defined tolerance distance could thus be used as an index of “closeness” in MCA, hence decreasing the subjectivity of interpreting MCA results.     

Formal models of Web queries

We present a new formal model of query and computation on the Web. We focus on two important aspects that distinguish the access to Web data from the access to a standard database system: the navigational nature of the access and the lack of concurrency control. We show that these two issues have significant effects on the computability of queries. To illustrate the ideas and how they can be used in practice for designing appropriate Web query languages, we consider a particular query language, the Web calculus, an abstraction and extension of the practical Web query language WebSQL.     

Parallel algorithms for certain matrix computations

The complexity of performing matrix computations, such as solving a linear system, inverting a nonsingular matrix or computing its rank, has received a lot of attention by both the theory and the scientific computing communities. In this paper we address some “nonclassical” matrix problems that find extensive applications, notably in control theory. More precisely, we study the matrix equations AX + XA^T = C and AX − XB = C, the “inverse” of the eigenvalue problem (called pole assignment), and the problem of testing whether the matrix [B AB … Aⁿ⁻¹ B] has full row rank. For these problems we show two kinds of PRAM algorithms: on one side very fast, i.e. polylog time, algorithms and on the other side almost linear time and processor efficient algorithms. In the latter case, the algorithms rely on basic matrix computations that can be performed efficiently also on realistic machine models.