Automatically assigned DDC number: 00574
Manually assigned DDC number: 006332
Number of references: 8
Title: Maintaining Transitive Closure of Graphs in SQL
Author:
Author:
Author:
Author:
Subject: Guozhu Dong,Leonid Libkin,Jianwen Su,Limsoon Wong Maintaining Transitive Closure of Graphs in SQL
Description: It is common knowledge that relational calculus and even SQL are not expressive enough to express recursive queries such as the transitive closure. In a real database system, one can overcome this problem by storing a graph together with its transitive closure and maintaining the latter whenever updates to the former occur. This leads to the concept of an incremental evaluation system, or IES. Much is already known about the theory of IES but very little has been translated into practice. The purpose of this paper is to fill in this gap by providing a gentle introduction to and an overview of some recent theoretical results on IES. The introduction is through the translation into SQL of three interesting positive maintenance results that have practical importance -- the maintenance of the transitive closure of acyclic graphs, of undirected graphs, and of arbitrary directed graphs. Interestingly, these examples also allow us to show the relationship between power and cost in the incre...
Contributor: The Pennsylvania State University CiteSeer Archives
Publisher: unknown
Date: 1999-01-14
Pubyear: 1999
Format: ps
Identifier: http://citeseer.ist.psu.edu/160586.html
Source: http://sdmc.krdl.org.sg/kleisli/psZ/dlsw-ijit97-9.ps
Language: en
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Rights: unrestricted
<?xml version="1.0" encoding="UTF-8"?>
<references_metadata>
<rec ID="/264477.html" Type="article" CiteSeer_Book="Int J on Digital Libraries" CiteSeer_Volume="1" Title="BioKleisli: A Digital Library for Biomedical Researchers,">
<identifier Org="ISBN:0262532689" Paper_ID="/264477.html" Extracted="0262532689" DDC="572.8'015118" Normalized_DDC="5728015118" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:038777744X" Paper_ID="/264477.html" Extracted="038777744X" DDC="025.3" Normalized_DDC="0253" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:0444828753" Paper_ID="/264477.html" Extracted="0444828753" DDC="572.8/01/51" Normalized_DDC="57280151" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:0471631817" Paper_ID="/264477.html" Extracted="0471631817" DDC="572/.6" Normalized_DDC="5726" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:0897919106" Paper_ID="/264477.html" Extracted="0897919106" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:1558606157" Paper_ID="/264477.html" Extracted="1558606157" />
<identifier Org="ISBN:155860622X" Paper_ID="/264477.html" Extracted="155860622X" DDC="005.7/2" Normalized_DDC="00572" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:1581137257" Paper_ID="/264477.html" Extracted="1581137257" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:1860945635" Paper_ID="/264477.html" Extracted="1860945635" DDC="570/.285" Normalized_DDC="570285" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:1878289519" Paper_ID="/264477.html" Extracted="1878289519" DDC="658.4/038" Normalized_DDC="6584038" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:3540003231" Paper_ID="/264477.html" Extracted="3540003231" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:3540213007" Paper_ID="/264477.html" Extracted="3540213007" DDC="570/.285" Normalized_DDC="570285" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:3540224181" Paper_ID="/264477.html" Extracted="3540224181" DDC="005.7/4" Normalized_DDC="00574" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:3540425454" Paper_ID="/264477.html" Extracted="3540425454" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:9051994079" Paper_ID="/264477.html" Extracted="9051994079" />
<identifier Org="ISBN:9810243847" Paper_ID="/264477.html" Extracted="9810243847" DDC="572.8/6" Normalized_DDC="57286" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:9810244584" Paper_ID="/264477.html" Extracted="9810244584" DDC="599.93/5" Normalized_DDC="599935" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:9812386157" Paper_ID="/264477.html" Extracted="9812386157" DDC="547.7" Normalized_DDC="5477" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:981238846X" Paper_ID="/264477.html" Extracted="981238846X" DDC="570.285" Normalized_DDC="570285" Normalized_Weight="0.058823529411764705" />
</rec>
<rec ID="/722674.html" Type="article" CiteSeer_Book="Theoretical Computer Science" CiteSeer_Volume="239" Title="Local properties of query languages,">
<identifier Org="ISBN:0818679263" Paper_ID="/722674.html" Extracted="0818679263" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540212027" Paper_ID="/722674.html" Extracted="3540212027" DDC="511.3/4" Normalized_DDC="51134" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540414568" Paper_ID="/722674.html" Extracted="3540414568" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540414819" Paper_ID="/722674.html" Extracted="3540414819" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540425543" Paper_ID="/722674.html" Extracted="3540425543" DDC="005.1/01/5113" Normalized_DDC="0051015113" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540622225" Paper_ID="/722674.html" Extracted="3540622225" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540642307" Paper_ID="/722674.html" Extracted="3540642307" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540648232" Paper_ID="/722674.html" Extracted="3540648232" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540648275" Paper_ID="/722674.html" Extracted="3540648275" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540669930" Paper_ID="/722674.html" Extracted="3540669930" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540671412" Paper_ID="/722674.html" Extracted="3540671412" DDC="004.01511" Normalized_DDC="00401511" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540746137" Paper_ID="/722674.html" Extracted="3540746137" DDC="025.04" Normalized_DDC="02504" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540788484" Paper_ID="/722674.html" Extracted="3540788484" DDC="004.67/8095" Normalized_DDC="004678095" Normalized_Weight="0.07692307692307693" />
</rec>
<rec ID="/127735.html" Type="inproceedings" CiteSeer_Book="Proc of 4th International Workshop on Database Programming Languages C Beeri A Ohori and D Shasha Eds" CiteSeer_Volume="" Title="First-Order Incremental Evaluation of Datalog Queries,">
<identifier Org="ISBN:0201537710" Paper_ID="/127735.html" Extracted="0201537710" DDC="005.74/01" Normalized_DDC="0057401" Normalized_Weight="0.125" />
<identifier Org="ISBN:0262571226" Paper_ID="/127735.html" Extracted="0262571226" DDC="005.74/068" Normalized_DDC="00574068" Normalized_Weight="0.125" />
<identifier Org="ISBN:0546656455" Paper_ID="/127735.html" Extracted="0546656455" />
<identifier Org="ISBN:0821805177" Paper_ID="/127735.html" Extracted="0821805177" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.125" />
<identifier Org="ISBN:0897917308" Paper_ID="/127735.html" Extracted="0897917308" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.125" />
<identifier Org="ISBN:0897919963" Paper_ID="/127735.html" Extracted="0897919963" />
<identifier Org="ISBN:3540198539" Paper_ID="/127735.html" Extracted="3540198539" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.125" />
<identifier Org="ISBN:3540249982" Paper_ID="/127735.html" Extracted="3540249982" DDC="004" Normalized_DDC="004" Normalized_Weight="0.125" />
<identifier Org="ISBN:3540589074" Paper_ID="/127735.html" Extracted="3540589074" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.125" />
<identifier Org="ISBN:3540637923" Paper_ID="/127735.html" Extracted="3540637923" DDC="005.75/7" Normalized_DDC="005757" Normalized_Weight="0.125" />
</rec>
<rec ID="/139144.html" Type="article" CiteSeer_Book="Annals of Mathematics and Artificial Intelligence" CiteSeer_Volume="14" Title="Nonrecursive Incremental Evaluation of Datalog Queries,">
<identifier Org="ISBN:0262571226" Paper_ID="/139144.html" Extracted="0262571226" DDC="005.74/068" Normalized_DDC="00574068" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:0780331214" Paper_ID="/139144.html" Extracted="0780331214" />
<identifier Org="ISBN:0897917308" Paper_ID="/139144.html" Extracted="0897917308" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540414819" Paper_ID="/139144.html" Extracted="3540414819" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540589074" Paper_ID="/139144.html" Extracted="3540589074" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540648232" Paper_ID="/139144.html" Extracted="3540648232" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540752552" Paper_ID="/139144.html" Extracted="3540752552" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540762973" Paper_ID="/139144.html" Extracted="3540762973" DDC="025.04" Normalized_DDC="02504" Normalized_Weight="0.14285714285714285" />
</rec>
<rec ID="/7075.html" Type="article" CiteSeer_Book="International Journal of Foundations of Computer Science" CiteSeer_Volume="11" Title="Separating Auxiliary Arity Hierarchy of First-Order Incremental Evaluation Systems Using (3k+1)-ary Input Relations," />
<rec ID="/332563.html" Type="inproceedings" CiteSeer_Book="Proc of Database Programming Languages DBPL97" CiteSeer_Volume="" Title="Incremental recomputation of recursive queries with nested sets and aggregate functions,">
<identifier Org="ISBN:1878289888" Paper_ID="/332563.html" Extracted="1878289888" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:1931777470" Paper_ID="/332563.html" Extracted="1931777470" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540249982" Paper_ID="/332563.html" Extracted="3540249982" DDC="004" Normalized_DDC="004" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540408010" Paper_ID="/332563.html" Extracted="3540408010" DDC="005.1/01/5113" Normalized_DDC="0051015113" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540414568" Paper_ID="/332563.html" Extracted="3540414568" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540414819" Paper_ID="/332563.html" Extracted="3540414819" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540648232" Paper_ID="/332563.html" Extracted="3540648232" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.14285714285714285" />
</rec>
<rec ID="/718407.html" Type="article" CiteSeer_Book="Journal of Computer and System Sciences" CiteSeer_Volume="55" Title="Query Languages for Bags and Aggregate Functions,">
<identifier Org="ISBN:0897917812" Paper_ID="/718407.html" Extracted="0897917812" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0897919106" Paper_ID="/718407.html" Extracted="0897919106" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:1581136706" Paper_ID="/718407.html" Extracted="1581136706" />
<identifier Org="ISBN:1591400538" Paper_ID="/718407.html" Extracted="1591400538" />
<identifier Org="ISBN:3540003231" Paper_ID="/718407.html" Extracted="3540003231" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540212027" Paper_ID="/718407.html" Extracted="3540212027" DDC="511.3/4" Normalized_DDC="51134" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540414134" Paper_ID="/718407.html" Extracted="3540414134" DDC="005" Normalized_DDC="005" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540414568" Paper_ID="/718407.html" Extracted="3540414568" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540414819" Paper_ID="/718407.html" Extracted="3540414819" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540622225" Paper_ID="/718407.html" Extracted="3540622225" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540648232" Paper_ID="/718407.html" Extracted="3540648232" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540654526" Paper_ID="/718407.html" Extracted="3540654526" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540669930" Paper_ID="/718407.html" Extracted="3540669930" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540746137" Paper_ID="/718407.html" Extracted="3540746137" DDC="025.04" Normalized_DDC="02504" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540788484" Paper_ID="/718407.html" Extracted="3540788484" DDC="004.67/8095" Normalized_DDC="004678095" Normalized_Weight="0.07692307692307693" />
</rec>
<rec ID="/384077.html" Type="inproceedings" CiteSeer_Book="" CiteSeer_Volume="" Title="Dyn--{FO}: a parallel, dynamic complexity class,">
<identifier Org="ISBN:0780331214" Paper_ID="/384077.html" Extracted="0780331214" />
<identifier Org="ISBN:0824722922" Paper_ID="/384077.html" Extracted="0824722922" />
<identifier Org="ISBN:0897916425" Paper_ID="/384077.html" Extracted="0897916425" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0897919963" Paper_ID="/384077.html" Extracted="0897919963" />
<identifier Org="ISBN:3540003231" Paper_ID="/384077.html" Extracted="3540003231" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540229698" Paper_ID="/384077.html" Extracted="3540229698" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540249982" Paper_ID="/384077.html" Extracted="3540249982" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540280057" Paper_ID="/384077.html" Extracted="3540280057" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540408010" Paper_ID="/384077.html" Extracted="3540408010" DDC="005.1/01/5113" Normalized_DDC="0051015113" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540414568" Paper_ID="/384077.html" Extracted="3540414568" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540414819" Paper_ID="/384077.html" Extracted="3540414819" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540589074" Paper_ID="/384077.html" Extracted="3540589074" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540622225" Paper_ID="/384077.html" Extracted="3540622225" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540631666" Paper_ID="/384077.html" Extracted="3540631666" DDC="004.24015113" Normalized_DDC="00424015113" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540637923" Paper_ID="/384077.html" Extracted="3540637923" DDC="005.75/7" Normalized_DDC="005757" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540648232" Paper_ID="/384077.html" Extracted="3540648232" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540653848" Paper_ID="/384077.html" Extracted="3540653848" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07142857142857142" />
</rec>
<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Maintaining Transitive Closure of Graphs in SQL">
<identifier Org="ISBN:3540768890" Paper_ID="SELF" Extracted="3540768890" />
</rec>
</references_metadata>