Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
Using boolean circuits for the parallel computation of queries
Keywords:
Computation Theory, Relational Databases, Boolean Circuits, Query Computability, Parallel ComputationAbstract
We present partial results of a research project in which we use boolean circuits as a parallel computation model for the expression of queries to relational databases. For that purpose, we use the well-known equivalence between First Order Logic (FO) and a class of restricted families of boolean circuits. First, we translate a given query, expressed through a FO formula, into a uniform family of boolean circuits. Then we analyse the depth of the boolean circuits, in order to optimize parallel time. For this sake, we work on the expression tree of the formula, looking for its transformation into an equivalent family of boolean circuits of minimum depth.
Downloads
Download data is not yet available.
References
[1] Abiteboul,S; Hull and Vianu, V.; “Foundations of Databases”. Addison-Wesley Publishing Company, 1995.
[2] Abiteboul,S; Vianu, V.; “Generic Computation and Its Complexity”, STOC 1991.
[3] Balcázar, J.L;Díaz, J; Gabarró, J; “Structural Complexity I”. Springer- Verlag, 1988.
[4] Balcázar, J.L;Díaz, J; Gabarró, J; “Structural Complexity II”. Springer- Verlag, 1990.
[5] Barroso, L.J., Gagliardi, E.O., Molina, G.M.., Quiroga, J.A., and Turull, J.M. “An Interpreter for the Complete Language QL” CACIC’97, La Plata, Argentina (in Spanish).
[6] Barroso, L.J., Molina, G.M.. and Quiroga, J.A. “Implementing an interpreter for QL Language”. Undergraduate Thesis in Computer Science, UNSL, 1997. Advisors: Turull, J.M. and Gagliardi, E.O. (in Spanish).
[7] Chandra, A.K.; Harel, D. “Computable Queries for Relational Data Bases”. Journal of Computer and System Sciences 21, 156-178. 1980.
[8] Codd, E.F.; “A relational model of data for a large shared databanks”. Com of ACM 13/6):377-387,1970.
[9] Denenberg, L.; Gurevich, Y; Shelah, S.; “Definability by Constant-Depth Polinomial- Size Circuits”, Information and Control 70, 2/3 (reprint), 1986.
[10] Ebbinghaus, H; Flum, J.; “Finite Model Theory”, Springer-Verlag, 1995.
[11] Ebbinghaus, H; Flum, J.;Thomas, W.; “Mathematical Logic”, Springer-Verlag, 1984.
[12] Gagliardi, E.O.; Grosso, A.L; Pereyra, S.R., Piffaretti, P. and Turull J.M., “Computability of Queries to Relational Databases through Boolean Circuits”, CACIC’99, Tandil, Argentina. (in Spanish)
[13] Grosso, A.L., Maldocena, P.D. and Reyes, N.S. and Turull, J.M.“ Implementation of an Interpreter for First Order Logic with Fixpoint” CACIC’00, Ushuaia, Argentina (in Spanish).
[14] Grosso, A.L., Maldocena, P.D. and Reyes, N.S. and Turull, J.M. “An interpreter of databases queries expressed by means of first order logic with transitive closure” CACIC’00, Ushuaia, Argentina (in Spanish).
[15] Hamilton, A.G.; “Logic for mathematicians”, Paraninfo, 1981 (in Spanish).
[16] Maldocena, P.D. Reyes, N.S. “ Implementation of an Interpreter for First Order Logic with Transitive Closure” Undergraduate Thesis in Computer Science, UNSL, 1999. Advisors: Turull, J.M. and Grosso, A.L. (in Spanish).
[17] Pereyra,S. and Piffaretti,P. “Computation of queries using boolean circuits”. Undergraduate Thesis in Computer Science, UNSL, 1998. Advisors: Turull, J.M., Gagliardi, E.O. and Grosso, A.L. (in Spanish)
[18] Turull Torres, J.M. “L-rigid Databases and the Expressibility of Incomplete Relational Languages”. Sc.D thesis, UNSL, 1996. (in Spanish)
[19] Ullman, Jeffrey D. “Principles of Database and Knowledge Base Systems”. Computers Science Press, 1988.
[20] Vollmer, Heribert, “Introduction to Circuit Complexity, a uniform approach”. Springer Verlag, 1999.
[2] Abiteboul,S; Vianu, V.; “Generic Computation and Its Complexity”, STOC 1991.
[3] Balcázar, J.L;Díaz, J; Gabarró, J; “Structural Complexity I”. Springer- Verlag, 1988.
[4] Balcázar, J.L;Díaz, J; Gabarró, J; “Structural Complexity II”. Springer- Verlag, 1990.
[5] Barroso, L.J., Gagliardi, E.O., Molina, G.M.., Quiroga, J.A., and Turull, J.M. “An Interpreter for the Complete Language QL” CACIC’97, La Plata, Argentina (in Spanish).
[6] Barroso, L.J., Molina, G.M.. and Quiroga, J.A. “Implementing an interpreter for QL Language”. Undergraduate Thesis in Computer Science, UNSL, 1997. Advisors: Turull, J.M. and Gagliardi, E.O. (in Spanish).
[7] Chandra, A.K.; Harel, D. “Computable Queries for Relational Data Bases”. Journal of Computer and System Sciences 21, 156-178. 1980.
[8] Codd, E.F.; “A relational model of data for a large shared databanks”. Com of ACM 13/6):377-387,1970.
[9] Denenberg, L.; Gurevich, Y; Shelah, S.; “Definability by Constant-Depth Polinomial- Size Circuits”, Information and Control 70, 2/3 (reprint), 1986.
[10] Ebbinghaus, H; Flum, J.; “Finite Model Theory”, Springer-Verlag, 1995.
[11] Ebbinghaus, H; Flum, J.;Thomas, W.; “Mathematical Logic”, Springer-Verlag, 1984.
[12] Gagliardi, E.O.; Grosso, A.L; Pereyra, S.R., Piffaretti, P. and Turull J.M., “Computability of Queries to Relational Databases through Boolean Circuits”, CACIC’99, Tandil, Argentina. (in Spanish)
[13] Grosso, A.L., Maldocena, P.D. and Reyes, N.S. and Turull, J.M.“ Implementation of an Interpreter for First Order Logic with Fixpoint” CACIC’00, Ushuaia, Argentina (in Spanish).
[14] Grosso, A.L., Maldocena, P.D. and Reyes, N.S. and Turull, J.M. “An interpreter of databases queries expressed by means of first order logic with transitive closure” CACIC’00, Ushuaia, Argentina (in Spanish).
[15] Hamilton, A.G.; “Logic for mathematicians”, Paraninfo, 1981 (in Spanish).
[16] Maldocena, P.D. Reyes, N.S. “ Implementation of an Interpreter for First Order Logic with Transitive Closure” Undergraduate Thesis in Computer Science, UNSL, 1999. Advisors: Turull, J.M. and Grosso, A.L. (in Spanish).
[17] Pereyra,S. and Piffaretti,P. “Computation of queries using boolean circuits”. Undergraduate Thesis in Computer Science, UNSL, 1998. Advisors: Turull, J.M., Gagliardi, E.O. and Grosso, A.L. (in Spanish)
[18] Turull Torres, J.M. “L-rigid Databases and the Expressibility of Incomplete Relational Languages”. Sc.D thesis, UNSL, 1996. (in Spanish)
[19] Ullman, Jeffrey D. “Principles of Database and Knowledge Base Systems”. Computers Science Press, 1988.
[20] Vollmer, Heribert, “Introduction to Circuit Complexity, a uniform approach”. Springer Verlag, 1999.
Downloads
Published
2001-10-01
How to Cite
Gagliardi, E. O., Herrera, N. E., Reyes, N. S., & Turull Torres, J. M. (2001). Using boolean circuits for the parallel computation of queries. Journal of Computer Science and Technology, 1(05), 13 p. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/982
Issue
Section
Original Articles
