×
Revesz, Peter Z.

The evaluation and the computational complexity of datalog queries of Boolean constraint databases. (English) Zbl 0923.68046

Int. J. Algebra Comput. 8, No. 5, 553-573 (1998).
In the database framework of Kanellakis et al.it was argued that constraint query languages should meet the closed-form requirement, that is, they should take as input constraint databases and give as output constraint databases that use the same type of constraints. This paper shows that the closed-form requirement can be met for Datalog queries with Boolean equality constraints with double exponential time-complete data complexity, for Datalog queries with precedence and monotone inequality constraints in triple exponential-time data complexity. A closed-form evaluation is also shown for (Stratified) Datalog queries with equality and inequality constraints in atomless Boolean algebras in triple exponential-time data complexity.
Reviewer: P.Z.Revesz (Lincoln)

MSC:

68P15 Database theory
68P20 Information storage and retrieval of data
06E99 Boolean algebras (Boolean rings)
68T30 Knowledge representation

Keywords:

boolean algebras; computational complexity; constraint databases; Datalog; stratified Datalog

Software:

Datalog
Cite Review PDF
Full Text: DOI

References:

[1] DOI: 10.1016/S0747-7171(87)80065-2 · Zbl 0641.68148 · doi:10.1016/S0747-7171(87)80065-2
[2] DOI: 10.1016/0022-0000(82)90012-5 · Zbl 0511.68073 · doi:10.1016/0022-0000(82)90012-5
[3] Helm R., J. Comput. Syst. Sci. 5 pp 197–
[4] Jaffar J., J. Logic Programming 1 pp 503–
[5] DOI: 10.1006/jcss.1995.1051 · doi:10.1006/jcss.1995.1051
[6] DOI: 10.1016/0304-3975(80)90048-1 · Zbl 0428.03036 · doi:10.1016/0304-3975(80)90048-1
[7] DOI: 10.1016/0304-3975(95)00209-X · Zbl 0872.68017 · doi:10.1016/0304-3975(95)00209-X
[8] DOI: 10.1016/S0747-7171(89)80013-6 · Zbl 0682.68093 · doi:10.1016/S0747-7171(89)80013-6
[9] Revesz P. Z., Springer-Verlag LNCS 893 pp 425– (1995)
[10] Revesz P. Z., Springer-Verlag LNCS 1358 pp 209– (1998)
[11] DOI: 10.1090/S0002-9904-1949-09359-X · doi:10.1090/S0002-9904-1949-09359-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.