On the consecutive retrieval property for generalized binary queries (Q799135)

A sequence of records with the consecutive retrieval property (CRP; cf. also the review above) for a given query set is called a CR-sequence. Let \(V_ n\) be the set of all n-component binary vectors which correspond to binary records, where n is the number of attributes, and let \(Q_ n\) be a query set \(\{S_ 1,...,S_ n,\bar S_ 1,...,\bar S_ n\},\) where \(S_ i\) is the query specifying the presence of the ith attribute and \(\bar S_ i\) is the query specifying its absence. This paper shows that the length \(L_ n\) of a CR-sequence of vectors of \(V_ n\) for the query set \(Q_ n\) satisfies the inequality \(L_ n\geq ((2/3)n-(1/36))2^ n- (2/9)(-1)^ n\) and gives an algorithm to construct a CR-sequence which attains the equality.