Yao Qi, Raja Das, et al.
ISSTA 2009
We investigate the complexity of query processing in the logical data model (LDM). We use two measures: data complexity, which is complexity with respect to the size of the data, and expression complexity, which is complexity with respect to the size of the expressions denoting the queries. Our investigation shows that while the operations of product and union are essentially first-order operations, the power set operation is inherently a higher-order operation and is exponentially expensive. We define a hierarchy of queries based on the depth of nesting of power set operations and show that this hierarchy corresponds to a natural hierarchy of Turing machines that run in multiply exponential time. © 1993.
Yao Qi, Raja Das, et al.
ISSTA 2009
N.K. Ratha, A.K. Jain, et al.
Workshop CAMP 2000
Lerong Cheng, Jinjun Xiong, et al.
ASP-DAC 2008
John M. Boyer, Charles F. Wiecha
DocEng 2009