Network satisfaction problems (NSPs) for finite relation algebras are computational decision problems, studied intensively since the 1990s. The major open research challenge in this field is to understand which of these problems are solvable by polynomial-time algorithms. Since there are known examples of undecidable NSPs of finite relation algebras it is advisable to restrict the scope of such a classification attempt to well-behaved subclasses of relation algebras. The class of relation algebras with a normal representation is such a well-behaved subclass. Many well-known examples of relation algebras, such as the Point Algebra, RCC5, and Allen’s Interval Algebra admit a normal representation. The great advantage of finite relation algebras with normal representations is that their NSP is essentially the same as a constraint satisfaction problem (CSP). For a relational structure B the problem CSP(B) is the computational problem to decide whether a given finite relational structure C has a homomorphism to B. The study of CSPs has a long and rich history, culminating for the time being in the celebrated proofs of the Feder-Vardi dichotomy conjecture. Bulatov and Zhuk independently proved that for every finite structure B the problem CSP(B) is in P or NP-complete. Both proofs rely on the universal-algebraic approach, a powerful theory that connects algebraic properties of structures B with complexity results for the decision problems CSP(B). Our contributions to the field are divided into three parts. Firstly, we provide two algebraic criteria for NP-hardness of NSPs. Our second result is a complete classification of the complexity of NSPs for symmetric relation algebras with a flexible atom; these problems are in P or NP-complete. Our result is obtained via a decidable condition on the relation algebra which implies polynomial-time tractability of the NSP. As a third contribution we prove that for a large class of NSPs, non-hardness implies that the problems can even be solved by Datalog programs, unless P = NP. This result can be used to strengthen the dichotomy result for NSPs of symmetric relation algebras with a flexible atom: every such problem can be solved by a Datalog program or is NP-complete. Our proof relies equally on known results and new observations in the algebraic analysis of finite structures. The CSPs that emerge from NSPs are typically of the form CSP(B) for an infinite structure B and therefore do not fall into the scope of the dichotomy result for finite structures. In this thesis we study NSPs of finite relation algebras with normal representations by the universal algebraic methods which were developed for the study of finite and infinite-domain CSPs. We additionally make use of model theory and a Ramsey-type result of Nešetril and Rödl. Our contributions to the field are divided into three parts. Firstly, we provide two algebraic criteria for NP-hardness of NSPs. Our second result is a complete classification of the complexity of NSPs for symmetric relation algebras with a flexible atom; these problems are in P or NP-complete. Our result is obtained via a decidable condition on the relation algebra which implies polynomial-time tractability of the NSP. As a third contribution we prove that for a large class of NSPs the containment in P implies that the problems can even be solved by Datalog programs, unless P = NP. As a third contribution we prove that for a large class of NSPs, non-hardness implies that the problems can even be solved by Datalog programs, unless P = NP. This result can be used to strengthen the dichotomy result for NSPs of symmetric relation algebras with a flexible atom: every such problem can be solved by a Datalog program or is NP-complete. Our proof relies equally on known results and new observations in the algebraic analysis of finite structures.

A growing number of industries are turning to data warehousing applications such as forecasting and risk assessment to process large volumes of data. These data warehousing applications, which utilize queries comprised of a mix of arithmetic and relational algebra (RA) operators, currently run on systems that utilize commodity multi-core CPUs. If we acknowledge the data-intensive nature of these applications, general purpose graphics processing units (GPUs) with high throughput and memory bandwidth seem to be natural candidates to host these applications. However, since such relational queries exhibit irregular parallelism and data accesses, their efficient implementation on GPUs remains challenging. Thus, although tailored solutions for individual processors using their native programming environments have evolved, these solutions are not accessible to other processors. This thesis addresses this problem by providing a portable implementation of RA, mathematical, and related primitives required to implement and accelerate relational queries over large data sets in the form of the library. These primitives can run on any modern multi- and many-core architecture that supports OpenCL, thereby enhancing the performance potential of such architectures for warehousing applications. In essence, this thesis describes the implementation of primitives and the results of their performance evaluation on a range of platforms and concludes with insights, the identification of opportunities, and lessons learned. One of the major insights from our analysis is that for complex relational queries, the time taken to transfer data between host CPUs and discrete GPUs can render the performance of discrete and integrated GPUs comparable in spite of the higher computing power and memory bandwidth of discrete GPUs. Therefore, data movement optimization is the key to eff ectively harnessing the high performance of discrete GPUs; otherwise, cost eff ectiveness would encourage the use of integrated GPUs. Furthermore, portability also enables the complete utilization of all GPUs and CPUs in the system at run time by opportunistically using any type of available processor when a kernel is ready for execution.