Since a query language is used as a handy tool to obtain information from a database, users want more user-friendly and fault-tolerant query interfaces. When a query search condition does not match with the underlying database, users would rather receive approximate answers than null information by relaxing the condition. They also prefer a less rigid querying structure, one which allows for vagueness in composing queries, and want the system to understand the intent behind a query. This paper presents a data abstraction approach to facilitate the development of such a fault-tolerant and intelligent query processing system. It specifically proposes a knowledge abstraction database that adopts a multilevel knowledge representation scheme called the knowledge abstraction hierarchy. Furthermore, the knowledge abstraction database extracts semantic data relationships from the underlying database and supports query relaxation using query generalization and specialization steps. Thus, ii: can broaden the search scope of original queries to retrieve neighborhood information and help users to pose conceptually abstract queries. Specifically, four types of vague queries are discussed, including approximate selection, approximate join, conceptual selection and conceptual join. (C) 2000 Elsevier Science B.V. All rights reserved.