Intelligent query answering by knowledge discovery techniques

Knowledge discovery facilitates querying database knowledge and intelligent query answering in database systems. We investigate the application of discovered knowledge, concept hierarchies, and knowledge discovery tools for intelligent query answering in database systems. A knowledge-rich data model is constructed to incorporate discovered knowledge and knowledge discovery tools. Queries are classified into data queries and knowledge queries. Both types of queries can be answered directly by simple retrieval or intelligently by analyzing the intent of query and providing generalized, neighborhood or associated information using stored or discovered knowledge. Techniques have been developed for intelligent query answering using discovered knowledge and/or knowledge discovery tools, which includes generalization, data summarization, concept clustering, rule discovery, query rewriting, deduction, lazy evaluation, application of multiple-layered databases, etc. Our study shows that knowledge discovery substantially broadens the spectrum of intelligent query answering and may have deep implications on query answering in data- and knowledge-base systems     

Fuzzy orderings in flexible query answering systems

This paper describes the benefits of using fuzzy orderings in flexible query answering systems. We provide a brief overview of those results from the theory of fuzzy orderings that are necessary to couple fuzzy orderings with flexible querying in a meaningful synergistic way. As one case study, we discuss a simple and pragmatic variant of a flexible query answering system – the so-called Vague query system (VQS). The integration of fuzzy orderings into that system is provided in full detail along with examples.This work was supported by the K_plus Competence Center Program which is funded by the Austrian Government, the Province of Upper Austria, and the Chamber of Commerce of Upper Austria.     

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

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

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.     

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.     

一种基于领域知识的XML数据模糊查询

为了解决普通用户对XML数据的模糊查询问题,提出了一种基于领域知识的XML数据模糊查询方法.以模糊集理论为基础,首先介绍了XML数据模糊查询的构成形式;然后提出了将领域知识和模糊集的隶属函数相结合的方法实现XML数据的模糊查询条件转换,转换过程考虑了查询谓词的重要程度和用户偏好;最后按结果元素对模糊查询的满足程度对模糊查询结果进行排序.该方法无需改变传统的XML查询语言和XDBMS就能够实现模糊查询,从而提高了用户与系统之间的交互能力.实验结果表明,提出的模糊查询方法具有较高的查全率和准确率.     

Probabilistic query answering over inconsistent databases

This paper presents a framework for querying inconsistent databases in the presence of functional dependencies. Most of the works dealing with the problem of extracting reliable information from inconsistent databases are based on the notion of repair, a minimal set of tuple insertions and deletions which leads the database to a consistent state (called repaired database), and the notion of consistent query answer, a query answer that can be obtained from every repaired database. In this work, both the notion of repair and query answer differ from the original ones. In the presence of functional dependencies, tuple deletions are the only operations that are performed in order to restore the consistency of an inconsistent database. However, deleting a tuple to remove an integrity violation potentially eliminates useful information in that tuple. In order to cope with this problem, we adopt a notion of repair, based on tuple updates, which allows us to better preserve information in the source database. A drawback of the notion of consistent query answer is that it does not allow us to discriminate among non-consistent answers, namely answers which can be obtained from a non-empty proper subset of the repaired databases. To obtain more informative query answers, we propose the notion of probabilistic query answer, that is query answers are tuples associated with probabilities. This new semantics of query answering over inconsistent databases allows us to give a measure of uncertainty to query answers. We show that the problem of computing probabilistic query answers is FP ^#P -complete. We also propose a technique for computing probabilistic answers to arbitrary relational algebra queries.     

Approximating query answering on RDF databases

Database users may be frustrated by no answers returned when they pose a query on the database. In this paper, we study the problem of relaxing queries on RDF databases in order to acquire approximate answers. We address two problems in efficient query relaxation. First, to ensure the quality of answers, we compute the similarities between relaxed queries with regard to the user query and use them to score the potential relevant answers. Second, for obtaining top-k answers, we develop two algorithms. One is based on the best-first strategy and relaxed queries are executed in the ranking order. The batch based algorithm executes the relaxed queries as a batch and avoids unnecessary execution cost. At last, we implement and experimentally evaluate our approaches.     

Data exchange: semantics and query answering

Data exchange is the problem of taking data structured under a source schema and creating an instance of a target schema that reflects the source data as accurately as possible. In this paper, we address foundational and algorithmic issues related to the semantics of data exchange and to the query answering problem in the context of data exchange. These issues arise because, given a source instance, there may be many target instances that satisfy the constraints of the data exchange problem.We give an algebraic specification that selects, among all solutions to the data exchange problem, a special class of solutions that we call universal. We show that a universal solution has no more and no less data than required for data exchange and that it represents the entire space of possible solutions. We then identify fairly general, yet practical, conditions that guarantee the existence of a universal solution and yield algorithms to compute a canonical universal solution efficiently. We adopt the notion of the “certain answers” in indefinite databases for the semantics for query answering in data exchange. We investigate the computational complexity of computing the certain answers in this context and also address other algorithmic issues that arise in data exchange. In particular, we study the problem of computing the certain answers of target queries by simply evaluating them on a canonical universal solution, and we explore the boundary of what queries can and cannot be answered this way, in a data exchange setting.     

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.     

Taxonomy-based relaxation of query answering in relational databases

Traditional information search in which queries are posed against a known and rigid schema over a structured database is shifting toward a Web scenario in which exposed schemas are vague or absent and data come from heterogeneous sources. In this framework, query answering cannot be precise and needs to be relaxed, with the goal of matching user requests with accessible data. In this paper, we propose a logical model and a class of abstract query languages as a foundation for querying relational data sets with vague schemas. Our approach relies on the availability of taxonomies, that is, simple classifications of terms arranged in a hierarchical structure. The model is a natural extension of the relational model in which data domains are organized in hierarchies, according to different levels of generalization between terms. We first propose a conservative extension of the relational algebra for this model in which special operators allow the specification of relaxed queries over vaguely structured information. We also study equivalence and rewriting properties of the algebra that can be used for query optimization. We then illustrate a logic-based query language that can provide a basis for expressing relaxed queries in a declarative way. We finally investigate the expressive power of the proposed query languages and the independence of the taxonomy in this context.     

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     

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

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

Ontological query answering under expressive Entity-Relationship schemata

The Entity-Relationship (ER) model is a fundamental tool for database design, recently extended and employed in knowledge representation and reasoning due to its expressiveness and comprehensibility. We address the problem of answering conjunctive queries under constraints representing schemata expressed in an extended version of the Entity-Relationship model. This extended model, called ER⁺, comprises is-a constraints among entities and relationships, plus functional and mandatory participation constraints. In particular, it allows for arbitrary permutations of the roles in is-a among relationships. A key notion that ensures high tractability in ER⁺ schemata is separability, i.e., the absence of interaction between the functional participation constraints and the other constructs of ER⁺. We provide a precise syntactic characterization of separable ER⁺ schemata by means of a necessary and sufficient condition. We present a complete complexity analysis of the conjunctive query answering problem under separable ER⁺ schemata, and also under several sublanguages of ER⁺. We show that the addition of so-called negative constraints does not increase the complexity of query answering. With such constraints, our model properly generalizes the most widely adopted tractable ontology languages, including those in the DL-Lite family.     

Matching dependencies: semantics and query answering

Matching dependencies (MDs) are used to declaratively specify the identification (or matching) of certain attribute values in pairs of database tuples when some similarity conditions on other values are satisfied. Their enforcement can be seen as a natural generalization of entity resolution. In what we call the pure case of MD enforcement, an arbitrary value from the underlying data domain can be used for the value in common that is used for a matching. However, the overall number of changes of attribute values is expected to be kept to a minimum. We investigate this case in terms of semantics and the properties of data cleaning through the enforcement of MDs. We characterize the intended clean instances, and also the clean answers to queries, as those that are invariant under the cleaning process. The complexity of computing clean instances and clean query answering is investigated. Tractable and intractable cases depending on the MDs are identified and characterized.     

Approximate schemas,source-consistency and query answering

We use the Edit distance with Moves on words and trees and say that two regular (tree) languages are ε-close if every word (tree) of one language is ε-close to the other. A transducer model is introduced to compare tree languages (schemas) with different alphabets and attributes. Using the statistical embedding of Fischer et al. (Proceedings of 21st IEEE Symposium on Logic in Computer Science, pp. 421–430, 2006), we show that Source-Consistency and Approximate Query Answering are testable on words and trees, i.e. can be approximately decided within ε by only looking at a constant fraction of the input.

Prioritized repairing and consistent query answering in relational databases

A consistent query answer in an inconsistent database is an answer obtained in every (minimal) repair. The repairs are obtained by resolving all conflicts in all possible ways. Often, however, the user is able to provide a preference on how conflicts should be resolved. We investigate here the framework of preferred consistent query answers, in which user preferences are used to narrow down the set of repairs to a set of preferred repairs. We axiomatize desirable properties of preferred repairs. We present three different families of preferred repairs and study their mutual relationships. Finally, we investigate the complexity of preferred repairing and computing preferred consistent query answers.