A stochastic programming approach for range query retrieval problems

One of the important issues in range query (RQ) retrieval problems is to determine the key's resolution for multi-attribute records. Conventional models need to be improved because of their potential degeneracy, less-than-desired computability and possible inconsistency with the partial match query (PMQ) models. This paper presents a new RQ model to overcome these drawbacks and introduces a new methodology, stochastic programming (SP), to conduct the optimization process. The model is established by using a monotone-increasing function to characterize range sizes. Three SP approaches - the wait-and-see (WS), here-and-now (HN) and scenario tracking (ST) methods - are integrated into this RQ model. Analytical expressions of the optimal solution are derived. It seems that HN has advantage over WS because the latter usually involves complicated multiple summations or integrals. For the ST method, a nonlinear programming software package is designed. Results of numerical experiments are presented that optimized a 10-dimensional RQ model and tracked both middle-size [100] and large-size (1,000) scenarios.

1 Introduction

In modern database systems, a file is a collection of records and each record has a number of attributes. A subset of the attributes acts as a key for each record. The primary key is the key that uniquely distinguishes a record from all others, while all the remainings are the secondary keys. Each attribute in a key is called a field. A query is a specification of values for zero or more fields of a record. In a partial match query (PMQ), one of the fileds is specified in a record while the other is not. In a range query (RQ), the ranges of some fields are specified. Typical approaches for solving PMQs and RQs include B-trees ([39], [44]), inverted files [9], and multiattribute hashing [41]. Our study focuses on applying multiattribute hashing to the RQ problems.