TQuery: a context-sensitive temporal query language.

Users of electronic medical databases request pertinent information by recasting their clinical questions into a formal database query language. Because the query language is the user's only access to the data, the query language must be powerful enough to enable users to express their data requirements. However, a competing need is for the query language to be restrictive enough so that queries can have unambiguous semantics and the query processor can generate correct answers. We describe a query language, called TQuery , that was designed specifically to formulate database queries that are dependent on temporal and contextual relationships. TQuery specifications express contextual constraints without the need to explicitly reference calendar dates. TQuery is the database query language used to retrieve patient data from an object-oriented electronic patient medical-record system called the temporal network (TNET). TNET and TQuery were developed to support the real-time temporal reasoning and representation needs of a LISP workstation-based medical expert system.     

Querying imprecise data in moving object environments

In moving object environments, it is infeasible for the database tracking the movement of objects to store the exact locations of objects at all times. Typically, the location of an object is known with certainty only at the time of the update. The uncertainty in its location increases until the next update. In this environment, it is possible for queries to produce incorrect results based upon old data. However, if the degree of uncertainty is controlled, then the error of the answers to queries can be reduced. More generally, query answers can be augmented with probabilistic estimates of the validity of the answer. We study the execution of probabilistic range and nearest-neighbor queries. The imprecision in answers to queries is an inherent property of these applications due to uncertainty in data, unlike the techniques for approximate nearest-neighbor processing that trade accuracy for performance. Algorithms for computing these queries are presented for a generic object movement model and detailed solutions are discussed for two common models of uncertainty in moving object databases. We study the performance of these queries through extensive simulations.     

Multiple similarity queries: a basic DBMS operation for mining inmetric databases

Metric databases are databases where a metric distance function is defined for pairs of database objects. In such databases, similarity queries in the form of range queries or k-nearest-neighbor queries are the most important query types. In traditional query processing, single queries are issued independently by different users. In many data mining applications, however, the database is typically explored by iteratively asking similarity queries for answers of previous similarity queries. We introduce a generic scheme for such data mining algorithms and we investigate two orthogonal approaches, reducing I/O cost as well as CPU cost, to speed-up the processing of multiple similarity queries. The proposed techniques apply to any type of similarity query and to an implementation based on an index or using a sequential scan. Parallelization yields an additional impressive speed-up. An extensive performance evaluation confirms the efficiency of our approach     

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.     

Qualitative and quantitative temporal constraints and relationaldatabases: theory, architecture, and applications

Many different applications in different areas need to deal with both: databases, in order to take into account large amounts of structured data; and quantitative and qualitative temporal constraints about such data. We propose an approach that extends: temporal databases and artificial intelligence temporal reasoning techniques and integrate them in order to face such a need. Regarding temporal reasoning, we consider some results that we proved recently about efficient query answering in the Simple Temporal Problem framework and we extend them in order to deal with partitioned sets of constraints and to support relational database operations. Regarding databases, we extend the relational model in order to consider also qualitative and quantitative temporal constraints both in the data (data expressiveness) and in the queries (query expressiveness). We then propose a modular architecture integrating a relational database with a temporal reasoner. We also consider classes of applications that fit into our approach and consider patient management in a hospital as an example     

Spatiotemporal aggregate computation: a survey

Spatiotemporal databases are becoming increasingly more common. Typically, applications modeling spatiotemporal objects need to process vast amounts of data. In such cases, generating aggregate information from the data set is more useful than individually analyzing every entry. In this paper, we study the most relevant techniques for the evaluation of aggregate queries on spatial, temporal, and spatiotemporal data. We also present a model that reduces the evaluation of aggregate queries to the problem of selecting qualifying tuples and the grouping of these tuples into collections on which an aggregate function is to be applied. This model gives us a framework that allows us to analyze and compare the different existing techniques for the evaluation of aggregate queries. At the same time, it allows us to identify opportunities for research on types of aggregate queries that have not been studied.     

An infrastructure for smart hospitals

In healthcare facilities most of the daily activities require strict coordination between clinicians, who often operate under heavy workloads and minimal workforce conditions in environments filled with increasingly complex technology. Ubiquitous Computing applications constitute a suitable solution for both reducing medical costs and improving patient safety by better supporting clinical processes. In this study we introduce an intelligent infrastructure for smart hospitals which implements basic services to optimize medical staff/patient interactions and grants ubiquitous and transparent access to clinical data stored in standard clinical databases. This infrastructure relies on the integration of Radio Frequency IDentification (RFID) and photosensor technologies to identify, locate and track clinicians and patients equipped with mobile devices and wearable RFID tags.     

Database Repairs and Analytic Tableaux

In this article, we characterize in terms of analytic tableaux the repairs of inconsistent relational databases, that is databases that do not satisfy a given set of integrity constraints. For this purpose we provide closing and opening criteria for branches in tableaux that are built for database instances and their integrity constraints. We use the tableaux based characterization as a basis for consistent query answering, that is for retrieving from the database answers to queries that are consistent with respect to the integrity constraints.     

Data mining on temporal data: a visual approach and its clinical application to hemodialysis

The quantity and complexity of data acquired, time-stamped and stored in clinical databases by automated medical devices is rapidly and continuously increasing. As a result, it becomes more and more important to provide clinicians with easy-to-use interactive tools to analyze huge amounts of this data. This paper proposes an approach for visual data mining on temporal data and applies it to a real medical problem, i.e. the management of hemodialysis. The approach is based on the integration of 3D and 2D information visualization techniques and offers a set of interactive functionalities that will be described in detail in the paper. We will also discuss how the system has been evaluated with end users and how the evaluation led to changes in system design.     

Intelligent selection and retrieval of multiple time-oriented records

Time-oriented domains with large volumes of time-stamped information, such as medicine, security information and finance, require useful, intuitive intelligent tools to process large amounts of time-oriented multiple-subject data from multiple sources. We designed and developed a new architecture, the VISualizatIon of Time-Oriented RecordS (VISITORS) system, which combines intelligent temporal analysis and information visualization techniques. The VISITORS system includes tools for intelligent selection, visualization, exploration, and analysis of raw time-oriented data and of derived (abstracted) concepts for multiple subject records. To derive meaningful interpretations from raw time-oriented data (known as temporal abstractions), we use the knowledge-based temporal-abstraction method. A major task in the VISITORS system is the selection of the appropriate subset of the subject population on which to focus during the analysis. Underlying the VISITORS population-selection module is our ontology-based temporal-aggregation (OBTAIN) expression-specification language which we introduce in this study. The OBTAIN language was implemented by a graphical expression-specification module integrated within the VISITORS system. The module enables construction of three types of expressions supported by the language: Select Subjects, Select Time Intervals, and Get Subjects Data. These expressions retrieve a list of subjects, a list of relevant time intervals, and a list of time-oriented subjects’ data sets, respectively. In particular, the OBTAIN language enables population-specification, through the Select Subjects expression, by using an expressive set of time and value constraints. We describe the syntax and semantics of the OBTAIN language and of the expression-specification module. The OBTAIN expressions constructed by the expression-specification module, are computed by a temporal abstraction mediation framework that we have previously developed. To evaluate the expression-specification module, five clinicians and five medical informaticians defined ten expressions, using the expression-specification module, on a database of more than 1,000 oncology patients. After a brief training session, both user groups were able in a short time (mean = 3.3 ± 0.53 min) to construct ten complex expressions using the expression-specification module, with high accuracy (mean = 95.3 ± 4.5 on a predefined scale of 0 to 100). When grouped by time and value constraint subtypes, five groups of expressions emerged. Only one of the five groups (expressions using time-range constraints), led to a significantly lower accuracy of constructed expressions. The five groups of expressions could be clustered into four homogenous groups, ordered by increasing construction time of the expressions. A system usability scale questionnaire filled by the users demonstrated the expression-specification module to be usable (mean score for the overall group = 68), but the clinicians’ usability assessment (60.0) was significantly lower than that of the medical informaticians (76.1).     

Superviews: Virtual Integration of Multiple Databases

An important advantage of a database system is that it provides each application with a custom view of the data. The issue addressed in this paper is how to provide such custom views to applications that access multiple databases. The paper describes a formal method that generates such superviews, in an interactive process of schema editing operations. A mapping of the superview into the individual databases is derived from the editing process, and is stored together with the superview as a virtual database. When this database is interrogated, the mapping is used to decompose each query into a set of queries against the individual databases, and recompose the answers to form an answer to the original query. As this process is transparent to the user, virtual databases may be regarded as a more general type of databases. A prototype database system, that allows users to construct virtual databases and interrogate them, has been developed.     

Efficient Approximate Query Processing in Peer-to-Peer Networks

Peer-to-peer (P2P) databases are becoming prevalent on the Internet for distribution and sharing of documents, applications, and other digital media. The problem of answering large-scale ad hoc analysis queries, for example, aggregation queries, on these databases poses unique challenges. Exact solutions can be time consuming and difficult to implement, given the distributed and dynamic nature of P2P databases. In this paper, we present novel sampling-based techniques for approximate answering of ad hoc aggregation queries in such databases. Computing a high-quality random sample of the database efficiently in the P2P environment is complicated due to several factors: the data is distributed (usually in uneven quantities) across many peers, within each peer, the data is often highly correlated, and, moreover, even collecting a random sample of the peers is difficult to accomplish. To counter these problems, we have developed an adaptive two-phase sampling approach based on random walks of the P2P graph, as well as block-level sampling techniques. We present extensive experimental evaluations to demonstrate the feasibility of our proposed solution.     

Communication between agents with heterogeneous perceptual capabilities

In real world applications robots and software agents often have to be equipped with higher level cognitive functions that enable them to reason, act and perceive in changing, incompletely known and unpredictable environments. One of the major tasks in such circumstances is to fuse information from various data sources. There are many levels of information fusion, ranging from the fusing of low level sensor signals to the fusing of high level, complex knowledge structures. In a dynamically changing environment even a single agent may have varying abilities to perceive its environment which are dependent on particular conditions. The situation becomes even more complex when different agents have different perceptual capabilities and need to communicate with each other.In this paper, we propose a framework that provides agents with the ability to fuse both low and high level approximate knowledge in the context of dynamically changing environments while taking account of heterogeneous and contextually limited perceptual capabilities.To model limitations on an agent’s perceptual capabilities we introduce the idea of partial tolerance spaces. We assume that each agent has one or more approximate databases where approximate relations are represented using lower and upper approximations on sets. Approximate relations are generalizations of rough sets.It is shown how sensory and other limitations can be taken into account when constructing and querying approximate databases for each respective agent. Complex relations inherit the approximativeness of primitive relations used in their definitions. Agents then query these databases and receive answers through the filters of their perceptual limitations as represented by (partial) tolerance spaces and approximate queries. The techniques used are all tractable.     

ImageMap: an image indexing method based on spatial similarity

We introduce ImageMap, as a method for indexing and similarity searching in image databases (IDBs). ImageMap answers "queries by example" involving any number of objects or regions and taking into account their interrelationships. We adopt the most general image content representation, that is, Attributed Relational Graphs (ARGs), in conjunction with the well-accepted ARG editing distance on ARGs. We tested ImageMap on real and realistic medical images. Our method not only provides for visualization of the data set, clustering and data mining, but it also achieves up to 1,000-fold speed-up in search over sequential scanning, with zero or very few false dismissals.     

Efficient fuzzy ranking queries in uncertain databases

Recently, uncertain data have received dramatic attention along with technical advances on geographical tracking, sensor network and RFID etc. Also, ranking queries over uncertain data has become a research focus of uncertain data management. With dramatically growing applications of fuzzy set theory, lots of queries involving fuzzy conditions appear nowadays. These fuzzy conditions are widely applied for querying over uncertain data. For instance, in the weather monitoring system, weather data are inherent uncertainty due to some measurement errors. Weather data depicting heavy rain are desired, where ??heavy?? is ambiguous in the fuzzy query. However, fuzzy queries cannot ensure returning expected results from uncertain databases. In this paper, we study a novel kind of ranking queries, Fuzzy Ranking queries (FRanking queries) which extend the traditional notion of ranking queries. FRanking queries are able to handle fuzzy queries submitted by users and return k results which are the most likely to satisfy fuzzy queries in uncertain databases. Due to fuzzy query conditions, the ranks of tuples cannot be evaluated by existing ranking functions. We propose Fuzzy Ranking Function to calculate tuples?? ranks in uncertain databases for both attribute-level and tuple-level uncertainty models. Our ranking function take both the uncertainty and fuzzy semantics into account. FRanking queries are formally defined based on Fuzzy Ranking Function. In the processing of answering FRanking queries, we present a pruning method which safely prunes unnecessary tuples to reduce the search space. To further improve the efficiency, we design an efficient algorithm, namely Incremental Membership Algorithm (IMA) which efficiently answers FRanking queries by evaluating the ranks of incremental tuples under each threshold for the fuzzy set. We demonstrate the effectiveness and efficiency of our methods through the theoretical analysis and experiments with synthetic and real datasets.     

A data model and query language for spatio-temporal decision support

In recent years, applications aimed at exploring and analyzing spatial data have emerged, powered by the increasing need of software that integrates Geographic Information Systems (GIS) and On-Line Analytical Processing (OLAP). These applications have been called SOLAP (Spatial OLAP). In previous work, the authors have introduced Piet, a system based on a formal data model that integrates in a single framework GIS, OLAP (On-Line Analytical Processing), and Moving Object data. Real-world problems are inherently spatio-temporal. Thus, in this paper we present a data model that extends Piet, allowing tracking the history of spatial data in the GIS layers. We present a formal study of the two typical ways of introducing time into Piet: timestamping the thematic layers in the GIS, and timestamping the spatial objects in each layer. We denote these strategies snapshot-based and timestamp-based representations, respectively, following well-known terminology borrowed from temporal databases. We present and discuss the formal model for both alternatives. Based on the timestamp-based representation, we introduce a formal First-Order spatio-temporal query language, which we denote L_t,\mathcal{L}_t, able to express spatio-temporal queries over GIS, OLAP, and trajectory data. Finally, we discuss implementation issues, the update operators that must be supported by the model, and sketch a temporal extension to Piet-QL, the SQL-like query language that supports Piet.     

An architecture for electronic field guides

People who classify and identify things based on their observable or deducible properties (called “characters” by biologists) can benefit from databases and keys that assist them in naming a specimen. This paper discusses our approach to generating an identification tool based on the field guide concept. Our software accepts character lists either expressed as XML (which biologists rarely provide knowingly—although most databases can now export in XML) or via ODBC connections to the data author’s relational database. The software then produces an Electronic Field Guide (EFG) implemented as a collection of Java servlets. The resulting guide answers queries made locally to a backend, or to Internet data sources via http, and returns XML. If, however, the query client requires HTML (e.g., if the EFG is responding to a human-centric browser interface that we or the remote application provides), or if some specialized XML is required, then the EFG forwards the XML to a servlet that applies an XSLT transformation to provide the look and feel that the client application requires. We compare our approach to the architecture of other taxon identification tools. Finally, we discuss how we combine this service with other biodiversity data services on the web to make integrated applications.     

Evaluation of probabilistic queries over imprecise data in constantly-evolving environments

Sensors are often employed to monitor continuously changing entities like locations of moving objects and temperature. The sensor readings are reported to a database system, and are subsequently used to answer queries. Due to continuous changes in these values and limited resources (e.g., network bandwidth and battery power), the database may not be able to keep track of the actual values of the entities. Queries that use these old values may produce incorrect answers. However, if the degree of uncertainty between the actual data value and the database value is limited, one can place more confidence in the answers to the queries. More generally, query answers can be augmented with probabilistic guarantees of the validity of the answers. In this paper, we study probabilistic query evaluation based on uncertain data. A classification of queries is made based upon the nature of the result set. For each class, we develop algorithms for computing probabilistic answers, and provide efficient indexing and numeric solutions. We address the important issue of measuring the quality of the answers to these queries, and provide algorithms for efficiently pulling data from relevant sensors or moving objects in order to improve the quality of the executing queries. Extensive experiments are performed to examine the effectiveness of several data update policies.     

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.     

Semantic caching of Web queries

Abstract. In meta-searchers accessing distributed Web-based information repositories, performance is a major issue. Efficient query processing requires an appropriate caching mechanism. Unfortunately, standard page-based as well as tuple-based caching mechanisms designed for conventional databases are not efficient on the Web, where keyword-based querying is often the only way to retrieve data. In this work, we study the problem of semantic caching of Web queries and develop a caching mechanism for conjunctive Web queries based on signature files. Our algorithms cope with both relations of semantic containment and intersection between a query and the corresponding cache items. We also develop the cache replacement strategy to treat situations when cached items differ in size and contribution when providing partial query answers. We report results of experiments and show how the caching mechanism is realized in the Knowledge Broker system. Received June 15, 1999 / Accepted December 24, 1999