Neighborhood and associative query answering

Cooperative query answering extends the classical notion of query answering to provide neighborhood and associated information. Neighborhood query answering relaxes the query and its answer via abstract representations. To integrate the abstraction view with the subsumption (is-a) and composition (part-of) views of type hierarchy, the notion of type abstraction hierarchy is introduced. To evaluate and control query relaxation, a nearness measure mechanism is provided. Associative query answering provides information conceptually related to, but not explicitly asked by the query. As object association is context sensitive, a DB-Pattern-KB framework is developed that couples domain-specific knowledge and participating objects in localized problem domains via virtual database patterns. Associative query answering can then be accomplished through tracing the behavior dependencies among cooperating objects in those problem domains. Such a framework allows related databases and knowledge bases to be linked dynamically in various contexts yet be maintained relatively independent of each other. The proposed approach has been implemented in the cooperative database system tested, CoBase, at UCLA. Our experience reveals that the proposed techniques are effective for cooperative query answering.This research is supported by DARPA contract N00174-91-C-0107.     

Providing ranked cooperative query answers using the metricized knowledge abstraction hierarchy

Cooperative query answering supports query relaxation and provides approximate answers as well as exact answers. To facilitate the query relaxation, a knowledge representation framework has been widely adopted, which accommodates semantic relationships or distance metrics to represent similarities among data values. In this paper, we propose a metricized knowledge abstraction hierarchy (MKAH) that supports multi-level data abstraction hierarchy and distance metric among data values. We show that the abstraction hierarchy is useful in representing the semantic relationship, and the abstraction hierarchy can provide data values with different scope according to their abstraction levels. The distance metric expresses the semantic similarity among data values with quantitative measure, and thus it enables query results to be ranked. To verify the practicality and effectiveness of the MKAH, we have implemented a prototype system in the area of career job search. Through various experiments, we show that the MKAH provides rich semantic representation and high quality distance measure. Furthermore, the experiments confirm that the domain adopting the MKAH can be compatible with other numeric domains, and that is advantageous in building up large scaled systems.     

CoBase: A scalable and extensible cooperative information system

A new generation of information systems that integrates knowledge base technology with database systems is presented for providing cooperative (approximate, conceptual, and associative) query answering. Based on the database schema and application characteristics, data are organized into Type Abstraction Hierarchies (TAHs). The higher levels of the hierarchy provide a more abstract data representation than the lower levels. Generalization (moving up in the hierarchy), specialization (moving down the hierarchy), and association (moving between hierarchies) are the three key operations in deriving cooperative query answers for the user. Based on the context, the TAHs can be constructed automatically from databases. An intelligent dictionary/directory in the system lists the location and characteristics (e.g., context and user type) of the TAHs. CoBase also has a relaxation manager to provide control for query relaxations. In addition, an explanation system is included to describe the relaxation and association processes and to provide the quality of the relaxed answers. CoBase uses a mediator architecture to provide scalability and extensibility. Each cooperative module, such as relaxation, association, explanation, and TAH management, is implemented as a mediator. Further, an intelligent directory mediator is provided to direct mediator requests to the appropriate service mediators. Mediators communicate with each other via KQML. The GUI includes a map server which allows users to specify queries graphically and incrementally on the map, greatly improving querying capabilities. CoBase has been demonstrated to answer imprecise queries for transportation and logistic planning applications. Currently, we are applying the CoBase methodology to match medical image (X-ray, MRI) features and approximate matching of emitter signals in electronic warfare applications.This work supported by ARPA contract F30602-94-C-0207.     

LACO: A location-aware cooperative query system for securely personalized services

Location-aware computing technology becomes promising for pervasive personalization services which run anytime, anywhere, and on any device. These services should be based on contextual queries that are provided in a fast and flexible manner. To do so, cooperative query answering may be useful to support query relaxation and to provide both approximate matches as well as exact matches. To facilitate query relaxation, a knowledge representation framework has been widely adopted which accommodates semantic relationships or distance metrics to represent similarities among data values. However, research shows few legacy cooperative query mechanisms that consider location-awareness. Hence, the purpose of this paper is to propose a securely personalized location-aware cooperative query that supports conceptual distance metric among data values, while considering privacy concerns around user context awareness. To show the feasibility of the methodology proposed in this paper, we have implemented a prototype system, LACO, in the area of site search in an actual large-scale shopping mall.     

Relaxation as a platform for cooperative answering

Responses to queries posed by a user of a database do not always contain the information desired. Database answers to a query, although they may be logically correct, can sometimes be misleading. Research in the area of cooperative answering for databases and deductive databases seeks to rectify these problems. We introduce a cooperative method calledrelaxation for expanding deductive database and logic programming queries. The relaxation method expands the scope of a query by relaxing the constraints implicit in the query. This allows the database to return answers related to the original query as well as the literal answers themselves. These additional answers may be of interest to the user. In section 1 we introduce the problem and method. In Section 2 we give some background on the research done in cooperative answering. Section 3 discusses the relaxation method, a potential control strategy, and uses. Section 4 looks at a semantic counterpart to this notion. In Section 5 we explore some of the control and efficiency issues. We enumerate open issues in Section 6, and conclude in Section 7.     

一种应用于Deep Web数据集成系统中的查询松弛策略

针对Deep Web环境中存在的失败查询,提出了一种有效的查询松弛策略.所有Deep Web资源按查询接口属性分组,组成全局数据源关系图(DRG);针对特定查询将DRG转换为对应该查询请求的数据源关系图;利用该DRG,按照特定的规则进行查询松弛和执行处理.针对查询松弛导致的部分结果可能与用户查询请求的相似度较低的问题,提出先通过Skyline方法对结果进行筛选,然后再根据各个结果实例与用户查询的相似度进行Top-k排序,最后将最接近用户要求的结果集返回给用户.通过实验验证了提出的查询松弛策略的有效性.     

A knowledge-based system for generating informative responses to indirect database queries

The objective of this study is to develop a knowledge-base framework for generatingcooperative answers to indirect queries. Anindirect query can be considered as a nonstandard database query in which a user did not specify explicitly the information request. In a cooperative query answering system, a user's indirect query should be answered with an informative response, either anaffirmative response or anegative response, which is generated on the basis of the inference of the user's information request and the reformulation of the users' indirect query.This paper presents methods for inferring users' intended actions, determining users' information requirements, and for automatically reformulating indirect queries into direct queries. The inference process is carried out on the basis of a user model, calluser action model, as well as the query context. Two kinds ofinformative responses, i.e.affirmative responses andnegative responses can be generated by arule-based approach.     

A knowledge-based approach for retrieving images by content

A knowledge based approach is introduced for retrieving images by content. It supports the answering of conceptual image queries involving similar-to predicates, spatial semantic operators, and references to conceptual terms. Interested objects in the images are represented by contours segmented from images. Image content such as shapes and spatial relationships are derived from object contours according to domain specific image knowledge. A three layered model is proposed for integrating image representations, extracted image features, and image semantics. With such a model, images can be retrieved based on the features and content specified in the queries. The knowledge based query processing is based on a query relaxation technique. The image features are classified by an automatic clustering algorithm and represented by Type Abstraction Hierarchies (TAHs) for knowledge based query processing. Since the features selected for TAH generation are based on context and user profile, and the TAHs can be generated automatically by a clustering algorithm from the feature database, our proposed image retrieval approach is scalable and context sensitive. The performance of the proposed knowledge based query processing is also discussed     

A Semantic Cache Framework for Secure XML Queries

Secure XML query answering to protect data privacy and semantic cache to speed up XML query answering are two hot spots in current research areas of XML database systems. While both issues are explored respectively in depth,they have not been studied together,that is,the problem of semantic cache for secure XML query answering has not been addressed yet. In this paper,we present an interesting joint of these two aspects and propose an efficient framework of semantic cache for secure XML query answering,which can improve the performance of XML database systems under secure circumstances. Our framework combines access control,user privilege management over XML data and the state-of-the-art semantic XML query cache techniques,to ensure that data are presented only to authorized users in an efficient way. To the best of our knowledge,the approach we propose here is among the first beneficial efforts in a novel perspective of combining caching and security for XML database to improve system performance. The efficiency of our framework is verified by comprehensive experiments.     

Cooperative Query Answering with Generalized Quantifiers

The use of Generalized Quantifiers in query languages was introduced independently in (Hsu and Parker, 1995; Gyssens et al., 1995). In both cases it is argued that GQs make query languages more able to handle complex queries in a declarative way and provide a syntax more similar to natural language. In this paper we argue that query languages with Generalized Quantifiers can be used to produce cooperative question answering (Gaasterland et al., 1992). We introduce the Query Language with Generalized Quantifiers QLGQ and review related work in cooperative query answering, focusing on research that has direct connections with the results of this paper. Then we show how to use Generalized Quantifiers in dealing with false presuppositions, constructing justifications, and query relaxation. For each technique, we give examples that suggest that Generalized Quantifiers are better suited to the application of the technique than traditional approaches.     

A holistic and principled approach for the empty-answer problem

We propose a principled optimization-based interactive query relaxation framework for queries that return no answers. Given an initial query that returns an empty-answer set, our framework dynamically computes and suggests alternative queries with fewer conditions than those the user has initially requested, in order to help the user arrive at a query with a non-empty-answer, or at a query for which no matter how many additional conditions are ignored, the answer will still be empty. Our proposed approach for suggesting query relaxations is driven by a novel probabilistic framework based on optimizing a wide variety of application-dependent objective functions. We describe optimal and approximate solutions of different optimization problems using the framework. Moreover, we discuss two important extensions to the base framework: the specification of a minimum size on the number of results returned by a relaxed query and the possibility of proposing multiple conditions at the same time. We analyze the proposed solutions, experimentally verify their efficiency and effectiveness, and illustrate their advantages over the existing approaches.     

领域问答系统中的文本错误自动发现方法

文本自动校对是自然语言处理的一个挑战性的研究课题,也是一个难题。该文对中文的错误类型和原因进行分析,提出了一种基于领域问答系统用户问题日志的错别字自动发现方法。该方法首先对语料进行分词,然后对分词的结果中出现的散串进行合并,对分词中的多字词和合并的串进行相似词串聚类,对相似词串的上下文语境进行统计分析,从中自动获取错别字对。实验表明,该系统获得71.32%的召回率,82.6%的准确率。     

AQUA: A Closed-Domain Question Answering System

This article describes AQUA, an experimental question answering system. AQUA combines Natural Language processing (NLP), Ontologies, Logic, and Information Retrieval technologies in a uniform framework. AQUA makes intensive use of an ontology in several parts of the question answering system. The ontology is used in the refinement of the initial query, the reasoning process and in the novel similarity algorithm. The similarity algorithm is a key feature of AQUA. It is used to find similarities between relations/concepts in the translated query and relations/concepts in the ontological structures. The similarities detected then allow the interchange of concepts or relations in a logic formula corresponding to the user query.     

An overview of cooperative answering

Databases and information systems are often hard to use because they do not explicitly attempt to cooperate with their users. Direct answers to database and knowledge base queries may not always be the best answers. Instead, an answer with extra or alternative information may be more useful and less misleading to a user. This paper surveys foundational work that has been done toward endowing intelligent information systems with the ability to exhibit cooperative behavior. Grice's maxims of cooperative conversation, which provided a starting point for the field of cooperative answering, are presented along with relevant work in natural language dialogue systems, database query answering systems, and logic programming and deductive databases. The paper gives a detailed account of cooperative techniques that have been developed for considering users' beliefs and expectations, presuppositions, and misconceptions. Also, work in intensional answering and generalizing queries and answers is covered. Finally, the Cooperative Answering System at Maryland, which is intended to be a general, portable platform for supporting a wide spectrum of cooperative answering techniques, is described.     

Knowledge-based image retrieval with spatial and temporalconstructs

A knowledge-based approach to retrieve medical images by feature and content with spatial and temporal constructs is developed. Selected objects of interest in an image are segmented and contours are generated. Features and content are extracted and stored in a database. Knowledge about image features can be expressed as a type abstraction hierarchy (TAH), the high-level nodes of which represent the most general concepts. Traversing TAH nodes allows approximate matching by feature and content if an exact match is not available. TAHs can be generated automatically by clustering algorithms based on feature values in the databases and hence are scalable to large collections of image features. Since TAHs are generated based on user classes and applications, they are context- and user-sensitive. A knowledge-based semantic image model is proposed to represent the various aspects of an image object's characteristics. The model provides a mechanism for accessing and processing spatial, evolutionary and temporal queries. A knowledge-based spatial temporal query language (KSTL) has been developed that extends ODMG's OQL and supports approximate matching of features and content, conceptual terms and temporal logic predicates. Further, a visual query language has been developed that accepts point-click-and-drag visual iconic input on the screen that is then translated into KSTL. User models are introduced to provide default parameter values for specifying query conditions. We have implemented the KMeD (Knowledge-based Medical Database) system using these concepts     

基于模式集成语义的查询处理

在采用面向对象模型作为公共数据模型的多数据库系统中，基于模式集成语义的查询处理不仅要实现针对集成模式查询到针对输出模式查询的转换，而且要从语义上尽可能减少回答用户查询所需数据，保证对象引用的正确性.为了达到这个目标,提出了一些新的概念及基于模式集成语义的查询处理规则和路径表达式的查询处理方法.     

Foundations of secure deductive databases

We develop a formal logical foundation for secure deductive databases. This logical foundation is based on an extended logic involving several modal operators. We develop two models of interaction between the user and the database called “yes-no” dialogs, and “yes-no-don't know” dialogs. Both dialog frameworks allow the database to lie to the user. We develop an algorithm for answering queries using yes-no dialogs and prove that secure query processing using yes-no dialogs is NP-complete. Consequently, the degree of computational intractability of query processing with yes-no dialogs is no worse than for ordinary databases. Furthermore, the algorithm is maximally cooperative to user in the sense that lying is resorted to only when absolutely necessary. For Horn databases, we show that secure query processing can be achieved in linear time-hence, this is no more intractable than the situation in ordinary databases. Finally, we identify necessary and sufficient conditions for the database to be able to preserve security. Similar results are also obtained for yes-no-don't know dialogs     

知识库系统KBASE＋的数据模型,语言及实现

本文讨论具有面向对象特征的知识库系统ＫＢＡＳＥ＋的数据模型，语言及实现，ＫＢＡＳＥ＋的数据模型可以方便地支持对象标识，类层次，多继承等面向对象概念。描述性查询语言ＫＢＬ是扩充的ＤＡＴＡＬＯＧ。本文重构了ＫＢＬ语义理论框架，提出了解决属性继承和实例继承的方案，说明了ＫＢＬ程序可以转换成语义等价的ＤＡＴＡＬＯＧ程序。     

The partial sequenced route query with traveling rules in road networks

In modern geographic information systems, route search represents an important class of queries. In route search related applications, users may want to define a number of traveling rules (traveling preferences) when they plan their trips. However, these traveling rules are not considered in most existing techniques. In this paper, we propose a novel spatial query type, the multi-rule partial sequenced route (MRPSR) query, which enables efficient trip planning with user defined traveling rules. The MRPSR query provides a unified framework that subsumes the well-known trip planning query (TPQ) and the optimal sequenced route (OSR) query. The difficulty in answering MRPSR queries lies in how to integrate multiple choices of points-of-interest (POI) with traveling rules when searching for satisfying routes. We prove that MRPSR query is NP-hard and then provide three algorithms by mapping traveling rules to an activity on vertex network. Afterwards, we extend all the proposed algorithms to road networks. By utilizing both real and synthetic POI datasets, we investigate the performance of our algorithms. The results of extensive simulations show that our algorithms are able to answer MRPSR queries effectively and efficiently with underlying road networks. Compared to the Light Optimal Route Discoverer (LORD) based brute-force solution, the response time of our algorithms is significantly reduced while the distances of the computed routes are only slightly longer than the shortest route.