Abstract
To provide a dichotomy between those queries that can be made feasible on big data after appropriate preprocessing and those for which preprocessing does not help, Fan et al. developed the $\sqcap$-tractability theory. This theory provides a formal foundation for understanding the tractability of query classes in the context of big data. Along this line, we introduce a novel notion of $\sqcap'$-tractability in this paper. Inspired by some technologies used to deal big data, we place a restriction on preprocessing function, which limits the function to produce a relatively small database as output, at most polylog-size of the input database. At the same time, we bound the redundancy information when re-factorizing data and queries for preprocessing. These changes aim to make our theory more closely linked to practice. We set two complexity classes to denote the classes of Boolean queries that are $\sqcap'$-tractable themselves and that can be made $\sqcap'$-tractable, respectively. Based on a new factorization in our complexity classes, we investigate two reductions, which differ from whether allowing re-factorizing data and query parts. We verify the transitive and compatible properties of the reductions and analysis the complete problems and sizes of the complexity classes. We conclude that all PTIME classes of Boolean queries can be made $\sqcap'$-tractable, similar to that of the $\sqcap$-tractability theory. With a little surprise, we prove that the set of all $\sqcap'$-tractable queries is strictly smaller than that of all $\sqcap$-tractable queries, and thus the set of $\sqcap'$-tractable queries is properly contained in that of PTIME queries. In this way, we attain a new complexity class inside the complexity class of PTIME queries.
Introduction
In traditional computational complexity, a problem is considered tractable if it belongs to the class PTIME. However, in the era of Big Data, even linear-time algorithms ($O(n)$) can be prohibitively slow for real-time applications. To address this, researchers have turned to preprocessing: an offline phase that transforms the data into a format that allows for extremely fast (NC, or parallel polylogarithmic time) online querying.
While the previously established $\Pi$-tractability framework formalized this approach, it lacked a constraint on the size of the preprocessed output. If a summary of a petabyte-scale database remains massive, the subsequent "fast" query phase may still be impractical. This paper introduces $\Pi'$-tractability, which imposes a strict polylogarithmic size limit on the preprocessed output, creating a more realistic theoretical model for big data engineering.
Methodology and Theoretical Framework
The core of the proposed theory is the definition of $\Pi'$-tractability. A query class is $\Pi'$-tractable if it satisfies three criteria:
- PTIME Preprocessing: The data can be preprocessed in polynomial time.
- Polylog-size Output: The preprocessed output must be at most polylogarithmic in size ($O(\log^k n)$) relative to the original database size $n$.
- NC Querying: After preprocessing, the query can be answered in parallel polylogarithmic time.
To formalize these concepts, the authors define several key symbols and sets, as summarized in the table below.
A critical innovation is the use of Factorization with Constant Redundancy (cr-factorization), denoted as $\Upsilon$. This allows for splitting a problem into data and query components without introducing excessive redundancy that might artificially inflate complexity. The relationship between these components and the resulting tractability classes is illustrated in the following framework.
Key Insights and Results
The research demonstrates that the size constraint on preprocessed output is a fundamental complexity differentiator rather than a mere practical optimization.
A New Complexity Hierarchy
The authors prove that $\Pi'$-tractability defines a strictly smaller set of problems than the original $\Pi$-tractability. Specifically, they establish the hierarchy: $\Pi' T_Q^0 \subsetneq \Pi T_Q^0 \subsetneq P$. This indicates that while many PTIME problems can be preprocessed for fast querying, only a subset can be compressed into a polylogarithmic summary while maintaining that speed.
The BDS Counterexample
A notable finding is the status of the Breadth-Depth Search (BDS) problem. While BDS is $\Pi$-tractable, it is not $\Pi'$-tractable. The authors show that a polylog-sized summary is insufficient to capture the complete visit order of a graph required to answer arbitrary BDS queries, highlighting the trade-off between summary size and query capability.
Universality of PTIME
Despite the strictness of $\Pi' T_Q^0$, the authors show that any PTIME class of Boolean queries can be made $\Pi'$-tractable ($\Pi' T_Q$) if one is allowed to re-factor the definition of the data and query parts. This mirrors a key result from the original $\Pi$-tractability theory and suggests that the "hardness" of a problem often depends on how it is partitioned.
Conclusion and Future Work
By enforcing a polylogarithmic limit on preprocessed output, $\Pi'$-tractability provides a more rigorous and practically relevant foundation for Big Data theory. This work carves out a new complexity class within PTIME that reflects the constraints of modern data systems.
Future research directions include incorporating space complexity as a primary measure of feasibility, analyzing specific preprocessing techniques like lossy compression, and adapting the results to modern distributed computing models like MapReduce or Spark.
Summary updated