Fan Zhang, Junwei Cao, et al.
IEEE TETC
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.
Fan Zhang, Junwei Cao, et al.
IEEE TETC
Reena Elangovan, Shubham Jain, et al.
ACM TODAES
Raymond Wu, Jie Lu
ITA Conference 2007
B.K. Boguraev, Mary S. Neff
HICSS 2000