A structured approach for cooperative query answering

This paper proposes the use of a type abstraction hierarchy as a framework for deriving cooperative query answers. The type abstraction hierarchy integrates the abstraction view with the subsumption (is-a) and composition (part-of) views of a type hierarchy. Such a framework provides multilevel object representation, which is an important aspect of cooperative query answering. The concept of pattern that specifies one or more conditions on an object is also proposed. Patterns have smaller granularity than types, and thus provide more specific semantic information. Cooperative query answering consists of query relaxation, generalization, specialization, and association on patterns. Query relaxation can be explicitly specified by the user or implicitly performed by the system. The implicit and explicit relaxations can also be combined and performed interactively by both the system and the user. CSQL, an extension of SQL for cooperative query answering, is also proposed. Preliminary experimental results reveal that the proposed type abstraction hierarchy provides an organized structure representing concepts at different knowledge levels in various domains, and provides a systematic and efficient method for cooperative query answering     

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.     

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.     

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.     

大数据上函数查询解答的复杂度分析

函数查询是大数据应用中重要的操作,查询解答问题一直是数据库理论中的核心问题。为了分析大数据上函数查询解答问题的复杂度,首先,使用映射归约方法将函数查询语言归约到已知的可判定语言,证明了函数查询解答问题的可计算性;其次,使用一阶语言描述函数查询,并分析了一阶语言的复杂度;在此基础上,使用NC-factor归约方法将函数查询类归约到已知的\mathrm{\Pi }{\mathrm{{\rm T}}}_Q-complete类中。证明函数查询解答问题经过PTIME（多项式时间）预处理后,可以在NC（并行多项式-对数）时间内求解。通过以上证明可以推出,函数查询解答问题在大数据上是可处理的。     

Top-k typicality queries and efficient query answering methods on large databases

Finding typical instances is an effective approach to understand and analyze large data sets. In this paper, we apply the idea of typicality analysis from psychology and cognitive science to database query answering, and study the novel problem of answering top-k typicality queries. We model typicality in large data sets systematically. Three types of top-k typicality queries are formulated. To answer questions like “Who are the top-k most typical NBA players?”, the measure of simple typicality is developed. To answer questions like “Who are the top-k most typical guards distinguishing guards from other players?”, the notion of discriminative typicality is proposed. Moreover, to answer questions like “Who are the best k typical guards in whole representing different types of guards?”, the notion of representative typicality is used. Computing the exact answer to a top-k typicality query requires quadratic time which is often too costly for online query answering on large databases. We develop a series of approximation methods for various situations: (1) the randomized tournament algorithm has linear complexity though it does not provide a theoretical guarantee on the quality of the answers; (2) the direct local typicality approximation using VP-trees provides an approximation quality guarantee; (3) a local typicality tree data structure can be exploited to index a large set of objects. Then, typicality queries can be answered efficiently with quality guarantees by a tournament method based on a Local Typicality Tree. An extensive performance study using two real data sets and a series of synthetic data sets clearly shows that top-k typicality queries are meaningful and our methods are practical.     

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.     

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.     

基于图的不一致容忍语义下的查询应答方法

本体在演变的过程中常出现不一致性问题,这将导致经典的推理模式失效. 不一致容忍语义能有效地解决推理失效的问题,但各类不一致容忍语义或者需要耗费大量计算,或者丢弃了本体中有效的信息.为此,一种针对IAR-语义和ICAR-语义的变种被用以解决上述的缺陷.新定义的IPAR-语义能够避免计算整个ABox关于TBox的封闭,在减少计算量的同时尽可能地保留了本体中的信息.在IPAR-语义下实现了基于图的查询应答方法,新方法将本体和查询以不同的规则构建成图,避免了传统重写导致的查询冗余的问题.最后,通过实验对比新的查询应答方法与ICAR-语义下的查询应答方法,实验结果表明：基于图的一致性查询方法执行效率要优于ICAR-语义下的查询方法;在本体规模不断增加的情况下,新方法具有更好的稳定性.     

视图确定性问题及其研究进展

基于视图的查询回答问题在数据管理方面有广泛的应用。为了形式化地描述一组视图V是否含有足够的信息来回答用户提出的一个查询Q,研究人员近期提出了“视图确定性”的概念。介绍了视图确定性相关的研究问题,对比其与查询重写之间的关系,分析出问题的主要研究维度,总结已有的研究成果并指出存在的问题。同时,对未来的研究趋势进行了展望。     

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.     

基于语义计算的公交移动问答系统

为解决外来旅客公交问询困难的问题,本文利用模式匹配、编辑距离计算、语义计算、自动问答等技术,实现了基于自然语言问答的公交移动问答系统。本文在抽象公交节点的基础上引入站点概念词,对站点关键词进行扩展、消除问询歧义,把公交线路抽象成线路节点网络模型,引入查询日志记录快表辅助问答,借助手机短消息业务实现了双向向传输。实验结果表明,该系统达到了预期效果。     

基于图匹配网络的可解释知识图谱复杂问答方法

知识图谱问答是人工智能领域的研究热点之一.在该任务中,自然语言问句结构与知识图谱结构之间的语义匹配是一个具有挑战的研究问题.现有工作主要利用深度学习技术对自然语言问句进行序列化编码,然后与知识图谱子图计算语义匹配,这样做法未充分利用复杂问句的结构信息,方法也缺乏可解释性.针对此问题,提出一种基于图匹配网络的知识图谱复杂问答方法TTQA.首先,通过语法分析方法,构建一个与知识图谱无关的未定查询图.然后,依据未定查询图和给定的知识图谱,构建一个与知识图谱相关的已定查询图,在其中,提出一种图匹配网络GMN,通过结合预训练语言模型和图神经网络技术,再利用注意力机制学习查询结构的上下文表示,从而得到更加丰富的结构匹配表示,用于已定查询图预测.在2个复杂问答数据集LC-QuAD 1.0和ComplexWebQuestions 1.1进行实验,结果表明：TTQA超过了现有方法.同时,通过消融实验验证了GMN的有效性.此外,TTQA生成的未定结构图和已定查询图增强了问答系统可解释性.     

On querying simple conceptual graphs with negation

We consider basic conceptual graphs, namely simple conceptual graphs (SGs), which are equivalent to the existential conjunctive positive fragment of first-order logic. The fundamental problem, deduction, is performed by a graph homomorphism called projection. The existence of a projection from a SG Q to a SG G means that the knowledge represented by Q is deducible from the knowledge represented by G. In this framework, a knowledge base is composed of SGs representing facts and a query is itself a SG. We focus on the issue of querying SGs, which highlights another fundamental problem, namely query answering. Each projection from a query to a fact defines an answer to the query, with an answer being itself a SG. The query answering problem asks for all answers to a query.

This paper introduces atomic negation into this framework. Several understandings of negation are explored, which are all of interest in real world applications. In particular, we focus on situations where, in the context of incomplete knowledge, classical negation is not satisfactory because deduction can be proven but there is no answer to the query. We show that intuitionistic deduction captures the notion of an answer and can be solved by projection checking. Algorithms are provided for all studied problems. They are all based on projection. They can thus be combined to deal with several kinds of negation simultaneously. Relationships with problems on conjunctive queries in databases are recalled and extended. Finally, we point out that this discussion can be put in the context of semantic web databases.     

基于本体的查询系统研究

该文对查询系统做了深入的研究,提出了一种基于本体的智能查询系统的形式化模型,并且对系统的具体运行过程进行了详细的分析。该模型充分考虑了用户查询的语义信息,并且引入了本体环境和用户查询环境来对系统进行建模。将用来对数据库的语义信息进行描述的本体层引入到异构的、分布式的数据库系统中,在方便用户进行查询的同时增加查询结果的相关性和用户满意度。同时,系统能够及时地反映数据库信息的动态变化。     

答疑系统问题的Z语言规约

分析了目前答疑系统存在的不足之一,即缺少标准框架,从而很难实现答疑系统之间资源的共享.因此提出了使用形式化方法来构建统一的答疑系统,利用形式化语言Z对答疑系统的主要模块进行需求规格说明.同时用Z语言描述了答疑系统的主要操作模式,包括关键词的提取、问题的检索和知识库的更新等操作.     

OWL-QL—a language for deductive query answering on the Semantic Web

This paper discusses the issues involved in designing a query language for the Semantic Web and presents the OWL query language (OWL-QL) as a candidate standard language and protocol for query–answering dialogues among Semantic Web computational agents using knowledge represented in the W3Cs ontology web language (OWL). OWL-QL is a formal language and precisely specifies the semantic relationships among a query, a query answer, and the knowledge base(s) used to produce the answer. Unlike standard database and Web query languages, OWL-QL supports query–answering dialogues in which the answering agent may use automated reasoning methods to derive answers to queries, as well as dialogues in which the knowledge to be used in answering a query may be in multiple knowledge bases on the Semantic Web, and/or where those knowledge bases are not specified by the querying agent. In this setting, the set of answers to a query may be of unpredictable size and may require an unpredictable amount of time to compute.     

基于语义相似度的Web数据库不精确查询方法

为了解决普通用户对于Web数据库的不精确查询问题,提出了一种基于语义相似度的Web数据库不精确查询方法。对于一个给定查询,该方法首先在查询历史中找出一个(或若干)与其相似度高于给定放松阈值的查询,然后从数据库中找出与这些查询相匹配的元组作为当前查询的不精确查询的结果,最后将这些查询结果按其对初始查询的满足程度进行排序。实验结果表明,提出的不同查询之间的语义相似度评估方法性能稳定、评估结果合理,不精确查询方法具有较高的查全率和排序准确性。