The goal of this chapter is to study the complexity of queries expressible in FO. We start with the general definition of different ways of measuring the complexity of a logic over finite structures: these are data, expression, and combined complexity. We then connect FO with Boolean circuits and establish some bounds on the data complexity. We also consider the issue of uniformity for a circuit model, and study it via logical definability. We then move to the combined complexity of FO, and show that it is much higher than the data complexity. Finally, we investigate an important subclass of FO queries — conjunctive queries — which play a central role in database theory.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
- Complexity of First-Order Logic
Prof. Leonid Libkin
- Springer Berlin Heidelberg
ec4u, Neuer Inhalt/© ITandMEDIA