INCREMENTAL AND DECREMENTAL EVALUATION OF TRANSITIVE CLOSURE BY FIRST-ORDER QUERIES

被引：37

作者：

DONG, GZ ^{[1
]}

SU, JW ^{[1
]}

机构：

[1] UNIV CALIF SANTA BARBARA,DEPT COMP SCI,SANTA BARBARA,CA 93106

来源：

INFORMATION AND COMPUTATION | 1995年 / 120卷 / 01期

关键词：

D O I：

10.1006/inco.1995.1102

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the following problem. Suppose G is a graph and TCG its transitive closure. If G' is a new graph obtained from G by inserting or deleting an edge e, can the new transitive closure TCG, be defined in first-order logic using G, TCG and e? In this paper, we show that the answer is positive for (1) acyclic graphs (main result), (2) graphs where the vertices of the deleted edge are not in the same strongly connected component, and (3) graphs where there exists at most one path between each pair of vertices (0-1-path graphs). It is left open whether the new transitive closure is definable in first-order logic for all graphs. We also consider the first-order on-line computation of the dominator relation. (C) 1995 Academic Press, Inc.

引用

页码：101 / 106

页数：6

共 18 条

[1]

Aho A.V., Hopcroft J.E., Ullman J.D., The Design and Analysis of Computer Algorithms, (1974)

[2]

Aho A.V., Ullman J.D., Universality of data retrieval languages, in "Proceedings, ACM Symposium on Principles of Programming Languages, pp. 110-120, (1979)

[3]

Chandra A.K., Harel D., Computable queries for relational data bases, J. Comput. System Sci., 21, 2, pp. 156-178, (1980)

[4]

Chandra A.K., Harel D., Horn clauses and generalizations, J. Logic Programming, 1, 1, pp. 1-15, (1985)

[5]

Dong G., Su J., First-order incremental evaluation ofdatalog queries, Proceedings of the 4 Th International Workshop on Database Programming Languages, pp. 295-308, (1993)

[6]

Dong G., Su J., Increment boundedness and nonrecursive incremental evaluation of datalog queries, Proceedings of the 5 Th International Conference on Database Theory, (1995)

[7]

Dong G., Topor R., Incremental evaluation of datalog queries, in "Proceedings of the 4th International Conference on Database Theory,, Lecture Notes in Computer Science, 646, pp. 282-296, (1992)

[8]

Even S., Shiloach Y., An on-line edge-deletion problem, J. Assoc. Comput. Mach, 28, 1, pp. 1-4, (1981)

[9]

Ibaraki T., Katoh N., On-line computation of transitive closure of graphs, Inform. Process. Lett., 16, 2, pp. 95-97, (1983)

[10]

Italiano G.F., Amortized efficiency of a path retrieval data structure, Theoret. Comput. Sci., 48, 2-3, pp. 273-281, (1986)

← 1 2 →