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

Graph

<?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>

www.000webhost.com