The theory of functional and subset dependencies over relational expressions

A formal system for reasoning about functional dependencies (FDs) and subset dependencies (SDs) defined over relational expressions is described. An FD e:X → Y indicates that Y is functionally dependent on X in the relation denoted by expression e; an SD e ? f indicates that the relation denoted by e is a subset of that denoted by f. The system is shown to be sound and complete by resorting to the analytic tableaux method. Applications of the system include the problem of determining if a constraint of a subschema is implied by the constraints of the base schema and the development of database design methodologies similar to normalization.     

On optimizing the evaluation of a set of expressions

A branch- and-bound type algorithm is developed to optimize the evaluation of a set of expressions. The algorithm proceeds in a depth-first manner and achieves an optimal solution. The algorithm is applied to optimize the evaluation of sets of relational expressions. Analogies to the heuristic information associated with theA* algorithm are investigated. Examples are presented illustrating the use of the algorithm. Pragmatics associated with the algorithm and its application to Boolean optimization are also discussed.Research supported by the National Science Foundation under grant number NSF MCS 79-19418 and by the National Aeronautics and Space Administration under grant number NGR 21-002-270-9.     

New Techniques for Data Reduction in a Database System for Knowledge Discovery Applications

Databases store large amounts of information about consumer transactions and other kinds of transactions. This information can be used to deduce rules about consumer behavior, and the rules can in turn be used to determine company policies, for instance with regards to production, marketing and in several other areas. Since databases typically store millions of records, and each record could have up to 100 or more attributes, as an initial step it is necessary to reduce the size of the database by eliminating attributes that do not influence the decision at all or do so very minimally. In this paper we present techniques that can be employed effectively for exact and approximate reduction in a database system. These techniques can be implemented efficiently in a database system using SQL (structured query language) commands. We tested their performance on a real data set and validated them. The results showed that the classification performance actually improved with a reduced set of attributes as compared to the case when all the attributes were present. We also discuss how our techniques differ from statistical methods and other data reduction methods such as rough sets.     

Fast Compositional Queries in a Relational Grid Information Service

A Grid Information service (GIS) stores information about the resources of a distributed computing environment and answers questions about it. We have developed RGIS, a GIS system that, unlike previous efforts, is based on the relational data model. RGIS users can write SQL queries that search for complex compositions of resources that meet collective requirements. Executing these queries can be very expensive, however. In response, we have introduced three query techniques, nondeterminism, scoping, and approximation, that allow the user (and RGIS) to trade off between the query’s running time and the number of results. Herein we describe RGIS, our query techniques, and their implementation. Our evaluation shows that a meaningful tradeoff between query time and results returned is achievable, and that the tradeoff can be used to keep query time largely independent of query complexity. RGIS uses our techniques to bound query execution time. This strongly supports our general case for GIS systems based on the relational data model and RDBMSes. Effort sponsored by the National Science Foundation under Grants ANI-0093221, ACI-0112891, ANI-0301108, EIA-0130869, and EIA-0224449. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF).     

Strong equivalence of relational expressions under dependencies

We propose two-well founded orderings on multisets that extend the Dershowitz-Manna ordering. Unlike the Dershowitz-Manna ordering, ours do not have a natural monotonicity property. This lack of monotonicity suggests using monotonicity to provide a new characterization of the Dershowitz-Manna ordering. Section 5 proposes an efficient and correct implementation of that ordering.     

On evaluating boolean expressions

An evaluation algorithm for Boolean expressions is efficient if it recognizes when particular conditions cannot affect the value of the result. Of special interest are efficient algorithms which do not expect the conditions to be evaluated in the order in which they appear in the expression. This is important for selective retrieval from a large data base, when the evaluation (retrieval) order depends on the data organization and not on the order in which the qualifiers appear in the query. Another aspect of data retrieval is that we may repeatedly change part (but not all) of the values of the variables, and wish to re-evaluate part of the expression. Algorithms are given for representing and efficiently evaluating Boolean expressions both for the sequential and random cases; for the latter, an algorithm for partial re-initialization is also given.     

Representation of highly-complex knowledge in a database

This paper presents a unified framework for representing highly-complex knowledge in a database as a new paradigm for handling large and complex information in an easy and efficient manner. The framework provides a database with the capabilities to support next generation databases for decision support systems through the use of derivation rules, temporal information, knowledge from multiple sources with different measures of quality and epistemic knowledge. The model integrates concepts from both thedatabase and theartificial intelligence disciplines.     

Recognising facial expressions in video sequences

We introduce a system that processes a sequence of images of a front-facing human face and recognises a set of facial expressions. We use an efficient appearance-based face tracker to locate the face in the image sequence and estimate the deformation of its non-rigid components. The tracker works in real time. It is robust to strong illumination changes and factors out changes in appearance caused by illumination from changes due to face deformation. We adopt a model-based approach for facial expression recognition. In our model, an image of a face is represented by a point in a deformation space. The variability of the classes of images associated with facial expressions is represented by a set of samples which model a low-dimensional manifold in the space of deformations. We introduce a probabilistic procedure based on a nearest-neighbour approach to combine the information provided by the incoming image sequence with the prior information stored in the expression manifold to compute a posterior probability associated with a facial expression. In the experiments conducted we show that this system is able to work in an unconstrained environment with strong changes in illumination and face location. It achieves an 89% recognition rate in a set of 333 sequences from the Cohn–Kanade database.     

Duration-constrained regular expressions

This paper investigates the logic-automata-connection for Duration Calculus. It has been frequently observed that Duration Calculus with linear duration terms comes close to being a logic of linear hybrid automata. We attempt to make this relation precise by constructing Kleene-connection between duration-constrained regular expressions and a subclass of linear hybrid automata called loop-reset automata in which any variable tested in a loop is reset in the same loop. The formalism of duration-constrained regular expressions is an extension of regular expressions with duration constraints, which are essentially formulas of Duration Calculus without negation, yet extended by a Kleene-star operator. In this paper, we show that this formalism is equivalent in expressive power to loop-reset automata by providing a translation procedure from expressions to automata and vice verse.Received June 1999Accepted in revised form September 2003 by M. R. Hansen and C. B. Jones     

Object-Oriented Databases with Relational DBMSs

The expediency of the use of object-oriented models of data as datalogical models in designing databases is shown, and methods of integration of relational and object-oriented models are considered. A relational scheme for storage of attributes and relations of object-oriented models is proposed.     

On the expressive power of the relational algebra with partially ordered domains

Assuming data domains are partially ordered, we define the partially ordered relational algebra (PORA) by allowing the ordering predicate ? to be used in formulae of the selection operator σ. We apply Paredaens and Bancilhon's Theorem to examine the expressiveness of the PORA, and show that the PORA expresses exactly the set of all possible relations which are invariant under order-preserving automorphisms of databases. The extension is consistent with the two important extreme cases of unordered and linearly ordered domains. We also investigate the three hierarchies of: (1) computable queries, (2) query languages and (3) partially ordered domains, and show that there is a one-to-one correspondence between them.     

A Model for Query Decomposition and Answer Construction in Heterogeneous Distributed Database Systems

The problem of retrieving information from a collection of heterogeneous distributed databases has attracted a number of solutions. However, the task of integrating established database systems is complicated not only by the differences between the database systems themselves, but also by the differences in structure and semantics of the information contained within them. The problem is exacerbated when one needs to provide access to such a system for naive end-users.This paper is concerned with a Knowledge-Based Systems approach to solving this problem for clearly bounded situations, in which both the domain and the types of query are constrained. At the user interface, dialogue is conducted in terms of concepts with which the user is familiar, and these are then mapped into appropriate database queries. To achieve this a model for query decomposition and answer construction has been used. This model is based around the development of an Intensional Structure containing information necessary for the recapture of semantic information lost in the query decomposition process and required in the answer construction process. The model has been successfully implemented in combination with an embedded KBS, within a five-layer representation model.     

Pattern expressions and pattern automata

We define the pattern expressions as an extension of both regular expressions and patterns. We prove several properties of the new family of languages, similar to those of extended regex languages [Câmpeanu et al., Int. J. Found. Comput. Sci. 14 (6) (2003) 1007-1018]. We also define an automata system that recognizes these languages. Differences between regex and pattern expressions are also discussed.     

C++ lambda expressions and closures

A style of programming that uses higher-order functions has become common in C++, following the introduction of the Standard Template Library (STL) into the standard library. In addition to their utility as arguments to STL algorithms, function parameters are useful as callbacks on GUI events, defining tasks to be executed in a thread, and so forth. C++’s mechanisms for defining functions or function objects are, however, rather verbose, and they often force the function’s definition to be placed far from its use. As a result, C++ frustrates programmers in taking full advantage of its own standard libraries. The effective use of modern C++ libraries calls for a concise mechanism for defining small one-off functions in the language, a need that can be fulfilled with lambda expressions.This paper describes a design and implementation of language support for lambda expressions in C++. C++’s compilation model, where activation records are maintained in a stack, and the lack of automatic object lifetime management make safe lambda functions and closures challenging: if a closure outlives its scope of definition, references stored in a closure dangle. Our design is careful to balance between conciseness of syntax and explicit annotations to guarantee safety. The presented design is included in the draft specification of the forthcoming major revision of the ISO C++ standard, dubbed C++0x. In rewriting typical C++ programs to take advantage of lambda functions, we observed clear benefits, such as reduced code size and improved clarity.     

Context-Aware Fuzzy Databases

The development of mechanisms to ease human machine interaction is an issue about which there is increasing interest within both the software world in general, and database systems in particular. A way to tackle this problem is to try to approach the natural way of user expression. The Fuzzy Sets Theory and its application to build Fuzzy Databases constitute a consolidated advance in the literature. Another way is to adapt the interaction of the system to the context where it is running. In this sense, this paper presents an approach to build a model of Fuzzy Databases that dynamically adapts to user context. In order to do this, we have studied the management of the context in Fuzzy Database applications and we propose an architecture for the development of intelligent, flexible and customized context-aware database systems. We also present a proof of concept implementation to be used with SQL:99 standard in Oracle ORDBMS. Finally, through a real application in the medical area, we demonstrate the feasibility of the proposal.     

Deciding determinism of caterpillar expressions

Caterpillar expressions have been introduced by Brüggemann-Klein and Wood for applications in markup languages. Caterpillar expressions provide a convenient formalism for specifying the operation of tree-walking automata on unranked trees. Here we give a formal definition of determinism of caterpillar expressions that is based on the language of instruction sequences defined by the expression. We show that determinism of caterpillar expressions can be decided in polynomial time.     

Rubis: an extended relational system managing events Part I: specification

Dynamic aspects of information systems are taken into account in a lot of conceptual models. However, the dynamic concepts of these models have rarely been fully implemented in database management systems (DBMSs).Rubis is an extended relational DBMS which supports an extended relational schema (including event and operation concepts) and automatic control of the dynamic aspects of applications, i.e. event recognition, operation triggering and time handling.The first part of the paper contains a short presentation of the basic concepts and the specification language used for the extended schema. The second part focuses on the internal mechanisms: the temporal processor, which manages the temporal aspects of specifications and recognizes temporal events; and the event processor which manages events treatment and synchronization. These two mechanisms permit an automatic execution of the extended schema and so provide rapid prototyping capabilities. This last part will be covered in the December issue of this journal.     

Designing deductive databases

We consider the problem of designing schemas for deductive databases. The design problem is to construct a database schema that supports, at minimal expected cost, a given set of database transactions. Our results include a formal definition of both a deductive database schema and a schema transformation. A schema transformation is used in the design process to transform one schema into another, with the goal of reducing the expected database costs. Our design methodology defines the concept of a schema transformation within the context of the clause-based deductive database model. The IDB of the schema that results from the design process includes clauses sufficient for a theorem prover to map queries stated against the original schema into queries against the (more cost effective) resulting schema. This allows users to interact exclusively with the initial schema, while the schema that results from the design process specifies the actual structure of the implemented database. In other words, the initial schema serves as the logical schema for the database, and the result of the design process serves as its physical schema.