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.     

Query answering via cooperative data inference

This paper proposes the use of accessible information (data/knowledge) to infer inaccessible data in a distributed database system. Inference rules are extracted from databases by means of knowledge discovery techniques. These rules can derive inaccessible data due to a site failure or network partition in a distributed system. Such query answering requires combining incomplete and partial information from multiple sources. The derived answer may be exact or approximate. Our inference process involves two phases to reason with reconstructed information. One phase involves using local rules to infer inaccessible data. A second phase involves merging information from different sites. We shall call such reasoning processes cooperative data inference. Since the derived answer may be incomplete, new algebraic tools are developed for supporting operations on incomplete information. A weak criterion called toleration is introduced for evaluating the inferred results. The conditions that assure the correctness of combining partial results, known as sound inference paths, are developed. A solution is presented for terminating an iterative reasoning process on derived data from multiple knowledge sources. The proposed approach has been implemented on a cooperative distributed database testbed, CoBase, at UCLA. The experimental results validate the feasibility of this proposed concept and can significantly improve the availability of distributed knowledge base/database systems.List of notation Mapping - --< Logical implication - = Symbolic equality - ==< Inference path - Satisfaction - Toleration - Undefined (does not exist) - Variable-null (may or may not exist) - ^* Subtuple relationship - ^* s-membership - s-containment - Open subtuple - Open s-membership - Open s-containment - _P Open base - P Program - I Interpretation - DIP Data inference program - t Tuples - R Relations - Ø Empty interpretation - Open s-union - Open s-interpretation - Set of mapping from the set of objects to the set of closed objects - W Set of attributes - _W Set of sound inference paths on the set of attributes W - Set of relational schemas in a DB that satisfy MVD - ⁺ Range closure of W wrt      

Likelog for flexible query answering

 Starting from unification based on similarity, a logic programming language, called LIKEness in LOGic (Likelog) is derived, thorougly relying on similarity. An operational semantics and a fix-point semantics of the language are defined, using an extension principle for fuzzy operators. The two approaches are proved to be related and a fuzzy extension of the least Herbrand model is given. One of the principal feature of such a logic programming language is to allow flexible query answering to deductive databases, which we show through an example. Moreover, we describe a system for web information retrieval through Likelog. I want to thank Ferrante Formato with whom I started and I continued this research and Prof. Giangiacomo Gerla for his great support and contribution given to this field.     

Study on consistent query answering in inconsistent databases

Consistent query answering is an approach to retrieving consistent answers over databases that might be inconsistent with respect to some given integrity constraints. The approach is based on a concept of repair. This paper surveys several recent researches on obtaining consistent information from inconsistent databases, such as the underlying semantic model, a number of approaches to computing consistent query answers and the computational complexity of this problem. Furthermore, the work outlines potential research directions in this area.     

基于协同数据库的数据迁移模型研究与实现

随着信息技术的发展和企业间协作的加强,企业的各种异构数据资源之间的协同也成为一个研究的热点。在将这些异构数据源进行协同的同时,不可避免地会出现数据的流动或迁移问题。提出在协同数据库的基础上实现数据迁移的一种模型,分析迁移模型的功能组成与实现,给出关于异构数据迁移的几个建议。建立该模型的意义在于减少协同数据库系统中数据库的数量和降低维护的成本。     

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.     

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

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

Techniques of integrating Datalog with PROLOG

Since extending DATALOG to a general-purpose programming language seems very difficult,many projects have embedded a DATALOG-based query laguage into a procedural host language,such as CORAL,Glue-Nail,etc.Although DATALOG can be consideed as function-free PROLOG,they are very different in many aspects.For instance,DATALOG is declarative while PROLOG isn‘t,DATALOG takes “a-set-at-a-time” mode of evaluation but PROLOG takes “a-tuple-at-a-time”one,DATALOG is only a query language whereas PROLOG is a general-purpose programming language.It is thought that integrating DATALOG with PROLOG may take their advantages.KBASEP is such a language.It uses KBASE as the query language and PROLOG as its procedural host language,where KBASE is a ne extemsion of DATALOG with negation and function.This paper introduces the integration techniques used in KBASE-P system.     

Answering Queries Addressed to Several Databases According to a Majority Merging Approach

The general context of this work is the problem of merging data provided by several sources which can be contradictory. Focusing on the case when the information sources do not contain any disjunction, this paper first defines a propositional modal logic for reasoning with data obtained by merging several information sources according to a majority approach. Then it defines a theorem prover to automatically deduce these merged data. Finally, it shows how to use this prover to implement a query evaluator which answers queries addressed to several databases. This evaluator is such that the answer to a query is the one that could be computed by a classical evaluator if the query was addressed to the merged databases. The databases we consider are made of an extensional part, i.e. a set of positive or negative ground literals, and an intensional part i.e. a set of first order function-free clauses. A restriction is imposed to these databases in order to avoid disjunctive data.     

A weighted string pattern matching-based passage ranking algorithm for video question answering

Video question answering aims to pinpoint answers in response to user’s specified questions. However, most question answering technologies involve in integrating rich specific external knowledge such as syntactic parsers, which are often unavailable for many languages. In this paper, we present a new string pattern matching-based passage ranking algorithm for extending traditional text Q/A toward videoQ/A. Users interact with our videoQ/A system through natural language questions whereas our system returns three sentence-length passages with corresponding video clips as answers. We collect 45 GB Discovery videos and 253 Chinese questions for evaluation. The experimental results showed that our method outperformed six top-performed ranking models. It is 7.39% better than the second best method (language model-based) in relatively MRR score and 6.12% in precision rate. Besides, we also show that the use of a trained Chinese word segmentation tool did decrease the overall videoQ/A performance where most ranking algorithms dropped at least 10% in relatively MRR, precision, and answer pattern recall rates.     

逻辑程序语言中的集合

本文首先讨论了引入集合的意义，然后建立了一种基于集合基贩归约演算，并且对集合项的存储和含集合符号的逻辑数据语言的计算进行了一些探讨。本文所介绍的方法通过规则编译时对存储衣序集的改写，使得对集合匹配通过一般函数的匹配算法就可以完成，提高了计算的效率。     

基于空值修复的数据库一致性查询方法*

完整性约束常用来定义数据库的数据语义,违反约束的数据库实例为不一致数据库,返回含有不一致结果的查询称为不一致查询。一致性查询目的在于不修改数据库实例而从不一致数据库获取满足约束的查询结果,已有方法因其支持的约束类型有限或计算复杂度高而影响其应用范围。提出了一种基于空值修复的数据库一致性查询方法,首先将原始完整性约束转换为与查询相关的统一约束,然后根据统一约束对原SQL查询进行查询重写,重写后的查询将不一致属性值当做空值来处理以获得满足完整性约束的结果。系统实现与实验证明,该方法在多种完整性约束类型与SQL     

Instance-sequence reasoning for video question answering

Video question answering (Video QA) involves a thorough understanding of video content and question language, as well as the grounding of the textual semantic to the visual content of videos. Thus, to answer the questions more accurately, not only the semantic entity should be associated with certain visual instance in video frames, but also the action or event in the question should be localized to a corresponding temporal slot. It turns out to be a more challenging task that requires the ability of conducting reasoning with correlations between instances along temporal frames. In this paper, we propose an instance-sequence reasoning network for video question answering with instance grounding and temporal localization. In our model, both visual instances and textual representations are firstly embedded into graph nodes, which benefits the integration of intra- and inter-modality. Then, we propose graph causal convolution (GCC) on graph-structured sequence with a large receptive field to capture more causal connections, which is vital for visual grounding and instance-sequence reasoning. Finally, we evaluate our model on TVQA+ dataset, which contains the groundtruth of instance grounding and temporal localization, three other Video QA datasets and three multimodal language processing datasets. Extensive experiments demonstrate the effectiveness and generalization of the proposed method. Specifically, our method outperforms the state-of-the-art methods on these benchmarks.     

A question answering system for project management applications

The usage of computer applications in the construction industry is increasing, as is the complexity of software applications and this makes it difficult for project personnel to maintain familiarity. Furthermore, the causes of practical problems, such as project delays and cost over-runs, are often not derivable from the output of most software. A question answering system provides a means for directly extracting knowledge from this output. This paper begins with an examination of issues involved in building such a system. An emerging industry standard, ifcXML, is adopted as the knowledge representation format, thereby reducing the effort that is necessary to build a knowledge base. We then explore the mechanisms that use information in the knowledge base for question understanding. A prototype system has been built and tested to illustrate usefulness for project management applications.     

An Efficient Evaluation Technique for Non-Stratified Programs by Transformation to Explicitly Locally Stratified Programs

We give a simple transformation from normal programs with no stratification (local, weak, modular, etc.) into a subclass of the locally stratified programs, called Explicitly Locally Stratified (ELS) programs, for which there are efficient evaluation techniques. One set of predicates are generated for the true tuples and a different set of predicate are generated for the true and undefined tuples. A similar transformation is given that incorporates a magic sets like transformation. Previous approaches to magic sets transformations of unstratified programs either restricted the class of sips used or generated a program that required special treatment of the magic sets predicates. Our transformation does not suffer from these flaws.     

A new industrial cooperative tele-maintenance platform

With the maturation of new telecommunication technologies, the industrial enterprises wants to integrate the advances to activate on site interventions of experts and then reduce the machines inactivity time. We propose a hardware and software solution allowing us to make a cooperative tele-maintenance: the maintenance staff can do the work remotely and also in collaboration with other experts (Cooperative Work). We emphasize network aspects (heterogeneity, dynamism) and cooperating members mobility for maintenance action achievement. The system we propose allows us to increase availability, mobility, yield and quality and to reduce the costs of equipment failures. In this paper, we show how computer innovative technologies and industrial maintenance techniques combination can offer new uses.     

An Overview of the Rule-Based Object Language

This paper presents an overview of a novel strongly typed deductive object database language, called Rule-based Object Language, which is being developed at the University of Regina. Rule-based Object Language is a uniform language for defining, querying, and manipulating a database, which integrates important features of deductive databases and object databases. It supports object identity, complex objects, classes, class hierarchies, multiple inheritance with overriding and blocking, and schema definition. It also supports structured values such as functor objects and sets, treating them as first class citizens and providing powerful mechanisms for representing both partial and complete information about sets. Important integrity constraints such as domain, referential, functional dependency, multi-valued dependency, and cardinality are built-in in a uniform framework. Rule-based Object Language directly supports non-first normal form relations and is an extension of the pure valued-oriented deductive languages such as Datalog and LDL (without grouping) and subsumes them as special cases. It supports schema, object, fact and rule queries in a uniform framework. It also supports schema, fact and rule updates.     

Panorama: A database system that annotates its answers to queries with their properties

When responding to queries, humans often volunteer additional information about their answers. Among other things, they may qualify the answer as to its reliability, and they may characterize it abstractly. This paper describes a relational database system that similarly annotates its answers with their properties. The process assumes that various assertions about properties of the data have been stored in the database (meta-information). These assertions are then used to infer properties of each answer provided by the system (meta-answers). Meta-answers are offered to users along with each answer issued, and help them to assess the value and meaning of the information that they receive. The advantages of the method described include: (1) It is extensible in that it allows users to determine the kinds of properties that the system will maintain and manipulate. (2) It has a built-in mechanism for determining the relevance of computed meta-information. (3) It is efficient: the number of operations required for meta-processing a given query can be expressed as a polynomial in the size of the meta-database. (4) It can be implemented externally with any commercial relational database system.     

Structure-sensitive semantic matching for aggregate question answering over knowledge base

Aggregate question answering essentially returns answers for given questions by obtaining query graphs with unique dependencies between values and corresponding objects. Word order dependency, as the key to uniquely identify dependency of the query graph, reflects the dependencies between the words in the question. However, due to the semantic gap caused by the expression difference between questions encoded with word vectors and query graphs represented with logical formal elements, it is not trivial to match the correct query graph for the question. Most existing approaches design more expressive query graphs for complex questions and rank them just by directly calculating their similarities, ignoring the semantic gap between them. In this paper, we propose a novel Structure-sensitive Semantic Matching(SSM) approach that learns aligned representations of dependencies in questions and query graphs to eliminate their gap. First, we propose a cross-structure matching module to bridge the gap between two modalities(i.e., textual question and query graph). Then, we propose an entropy-based gated AQG filter to remove the structural noise caused by the uncertainty of dependencies. Finally, we present a two-channel query graph representation that fuses the semantics of abstract structure and grounding content of the query graph explicitly. Experimental results show that SSM could learn aligned representations of questions and query graphs to eliminate the gaps between their dependencies, and improves up to 12% (F1 score) on aggregation questions of two benchmark datasets.