Nearness and cooperative query answering
Matthew Merzbacher · University of California at Los Angeles eBooks · 1993
A cooperative query answering (CQA) system behaves like a conventional data-base system when queries can be answered normally, and tries to find an approximate answer when the original query condition cannot be matched exactly. One approach to locating approximate answers efficiently is to employ abstraction hierarchies. Using these hierarchies has several shortcomings, which are overcome by adding a measure of semantic nearness to the them. The measure indicates the semantic proximity between the values in the hierarchies. Thus, the focus of this research, the attribute abstraction hierarchy with nearness (AAH), is introduced. Two novel methods for the automatic construction and maintenance of attribute abstraction hierarchies are presented. Pattern-Based Knowledge Inference (PKI) is a technique for the construction of an initial abstraction hierarchy for each attribute based on patterns implicit in the current database instance. Dynamic Nearness (DN), improves the hierarchy by altering it based on query access patterns. The two methods can combine to form a new hierarchy with greater semantic utility. The generated hierarchies conform to a set of desirable properties and are well-suited for use in other applications requiring similar knowledge structures. User, domain and query contexts are applied to restrict search in the hierarchy and efficiently locate approximate query answers across several attributes. The approximate answers to the query are ordered based on relative nearness to the exact answer. Control structures added to CoBase, a working cooperative database, show how these context mechanisms work. For a relation with t tuples, the time complexity of PKI is $O(t\sp3)$ and the space complexity is linear. A simple extension improves time complexity to O(t log t), while retaining linear space complexity. Dynamic Nearness has linear time complexity, but space complexity is $O(t\sp2)$. Again, a simple extension retains the linear time complexity while improving the space complexity to linear as well. Both extensions achieve their improvements by selectively discarding less important knowledge. This streamlining of the knowledge base improves complexity at the expense of some loss of detail. Experimental results from an operational database used to plan transportation of forces and their support cargo demonstrate the utility and viability of PKI and DN. These results also demonstrate the improvement in computational complexity afforded by the extensions to both algorithms and show a dramatic improvement in time and space complexity with minimal loss of detail.