Space-Filling Curves for Query Processing
- PDF / 9,929,878 Bytes
- 444 Pages / 547.087 x 737.008 pts Page_size
- 31 Downloads / 155 Views
Safety and Domain Independence R ODNEY T OPOR Griffith University, Nathan, QLD, Australia
Synonyms Finiteness
Definition The values in the relations of a relational database are elements of one or more underlying sets called domains. In practical applications, a domain may be infinite, e.g., the set of natural numbers. In this case, the value of a relational calculus query when applied to such a database may be infinite, e.g., {n j n 10}. A query Q is called finite if the value of Q when applied to any database is finite. Even when the database domains are finite, all that is normally known about them is that they are some finite superset of the values that occur in the database. In this case, the value of a relational calculus query may depend on such an unknown domain, e.g., {x j 8yR(x, y)}. A query Q is called domain independent if the value of Q when applied to any database is the same for any two domains containing the database values or, equivalently, if the value of Q when applied to a database contains only values that occur in the database. The term safe query has been used ambiguously in the literature. Often safe queries have been identified with finite queries. Sometimes safe queries have been members of a large, simple, decidable class of queries that are guaranteed to be finite, or, in other cases, domain independent. The use of word safe is preferred to denote a large, simple, decidable class of queries #
2009 Springer ScienceþBusiness Media, LLC
that are guaranteed to be domain independent and hence, normally finite. Obviously, it is desirable that queries be finite and domain independent. Unfortunately, the classes of finite queries and domain independent queries are undecidable, which leads to a search for decidable classes of queries that can represent all, or as many as possible, finite (resp., domain independent) queries.
Historical Background DiPaola [3] and independently Vardi [11] recognized the desirability that queries be domain independent and proved that the class of domain independent queries was undecidable. Many researchers then attempted to define decidable classes of queries that were guaranteed to be domain independent. This work was summarized by Topor [9], Kifer [6], Ullman [10], and Abiteboul et al. [1]. Many different names such as range-restricted, allowed, safe, with subtle differences, were used in these definitions. Ullman [10], Van Gelder and Topor [12], and Abiteboul et al. [1] gave algorithms for translating queries in these classes into relational algebra for efficient evaluation. Other researchers such as Escobar-Molano et al. [4], Hull and Su [5] and Suciu [8] attempted to define decidable classes of queries, safe queries, that were guaranteed to be finite in the presence of functions (e.g., arithmetic functions) over infinite domains (e.g., the natural numbers). Whether or not there is a decidable class of queries that can express every finite (resp., domain independent) query depends critically on the particular set of functions on the domains. Stolboushkin and
Data Loading...
