Graph-theoretic methods in database theory

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Graph-theoretic methods in database theory

Full text

Pdf (1.61 MB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems table of contents

Nashville, Tennessee, United States

Pages: 230 - 242

Year of Publication: 1990

ISBN:0-89791-352-3

Author

Mihalis Yannakakis

AT&T Bell Laboratories, Murray Hill, NJ

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 109, Citation Count: 26

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/298514.298576 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AP	F. Afrati , C. Papadimitriou, The parallel complexity of simple chain queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.210-213, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28682]
	AAK	A. Aggarwal , R. J. Anderson , M.-Y. Kao, Parallel depth-first search in general directed graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.297-308, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73035]
	ACS	A. Aggarwal, A. K. Chandra, and M. Snir, "Hierarchical Memory with Block Transfer", Proc. 28th IEEE Syrup. on Foundations of Computer Science, pp. 204-216, 1987.
	A	Rakesh Agrawal, Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries, Proceedings of the Third International Conference on Data Engineering, p.580-590, February 03-05, 1987
	AJ	Rakesh Agrawal , H. V. Jagadish, Direct Algorithms for Computing the Transitive Closure of Database Relations, Proceedings of the 13th International Conference on Very Large Data Bases, p.255-266, September 01-04, 1987
	AHU	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	ASU	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	AU	Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
	A+	R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovasz, and C. Rackoff, "Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems", Proc. 20th 1EEE Syrup. on Foundations of Computer Science, pp. 218-223, 1979.
	BMSU	Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
	BR	Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
	BKBR	C. Beeri , P. Kanellakis , F. Bancilhon , R. Ramakrishnan, Bounds on the propagation of selection into logic programs, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-226, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28683]
	BR	C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28689]
	BS	J. Biskup, and H, Stiefeling, 'Transitive Closure Algorithms for Very Large Databases", TR, Hochschule Hildesheim, 1988.
	BFM	P.A. Bloniarz, M. J. Fischer, and A. R. Meyer, "A Note on the Average Time to Compute Transitive Closure", Proc. Intl. Coll. on Automata, Languages, and Prograrmning, 1976.
	BKV	Adam L. Buchsbaum , Paris C. Kanellakis , Jeffrey S. Vitter, A data structure for arc insertion and regular path finding, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.22-31, January 22-24, 1990, San Francisco, California, United States
	C	B. Carte, Graphs and Networks, Oxford University Press, 1979.
	CW	D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
	CK	S Cosmadakis , P Kanellakis, Parallel evaluation of recursive rule queries, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.280-293, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15421]
	CMW	Isabel F. Cruz , Alberto O. Mendelzon , Peter T. Wood, A graphical query language supporting recursion, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.323-330, May 27-29, 1987, San Francisco, California, United States
	DKS	Cynthia Dwork , Paris C. Kanellakis , Larry Stockmeyer, Parallel algorithms for term matching, SIAM Journal on Computing, v.17 n.4, p.711-731, August 1988 [doi>10.1137/0217046]
	FHW	S. Fortune, J. Hopcroft, and J. Wyllie, "The Directed Subgraph Homeomorphism Problem", Theoretical Computer Science, 10, pp. 11-121, 1980.
	GM	Hillel Gazit , Gary L. Miller, An improved parallel algorithm that computes the BFS numbering of a directed graph, Information Processing Letters, v.28 n.2, p.61-65, June 24, 1988 [doi>10.1016/0020-0190(88)90164-0]
	GS	N. Goodman , O. Shmueli, The tree property is fundamental for query processing, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588119]
	GSS	G. Grahne , S. Sippu , E. Soisalon-Soininen, Efficient evaluation for a subset of recursive queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.284-293, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28690]
	HaN	Ramsey W. Haddad , Jeffrey F. Naughton, Counting methods for cyclic relations, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.333-340, March 1988, Austin, Texas, United States [doi>10.1145/308386.308469]
	HeN	Lawrence J. Henschen , Shamim A. Naqvi, On compiling queries in recursive first-order databases, Journal of the ACM (JACM), v.31 n.1, p.47-85, Jan. 1984 [doi>10.1145/2422.2423]
	Ho	Gerard J. Holzmann, An improved protocol reachability analysis technique, Software—Practice & Experience, v.18 n.2, p.137-161, Feb., 1988 [doi>10.1002/spe.4380180203]
	HK	Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
	HSU	H. B. Hunt, III , J. D. Ullman , T. G. Szymanski, Operations on sparse relations, Communications of the ACM, v.20 n.3, p.171-176, March 1977 [doi>10.1145/359436.359446]
	IK	T. Ibaraki, and N. Katoh, "On-line Computation of Transitive Closure of Graphs", Information Processing Letters, 16(9), pp. 5-7, 1983.
	I	Yannis E. Ioannidis, On the Computation of the Transitive Closure of Relational Operators, Proceedings of the 12th International Conference on Very Large Data Bases, p.403-411, August 25-28, 1986
	IR	Yannis E. Ioannidis , Raghu Ramakrishnan, Efficient Transitive Closure Algorithms, Proceedings of the 14th International Conference on Very Large Data Bases, p.382-394, August 29-September 01, 1988
	It1	G. F. Italiano, Amortized efficiency of a path retrieval data structure, Theoretical Computer Science, v.48 n.2-3, p.273-281, Dec., 1986
	It2	Giuseppe F. Italiano, Finding paths and deleting edges in directed acyclic graphs, Information Processing Letters, v.28 n.1, p.5-11, May 30, 1988 [doi>10.1016/0020-0190(88)90136-6]
	Im	Neil Immerman, Nondeterministic space is closed under complementation, SIAM Journal on Computing, v.17 n.5, p.935-938, October 1988 [doi>10.1137/0217058]
	JAN	H. V. Jagadish , Rakesh Agrawal , Linda Ness, A study of transitive closure as a recursion mechanism, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.331-344, May 27-29, 1987, San Francisco, California, United States
	K	P. C. Kanellakis, Logic programming and parallel complexity, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	KS	M.-Y. Kao , G. E. Shannon, Local reorientation, global order, and planar topology, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.286-296, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73034]
	LN	R. J. Lipton , J. F. Naughton, Estimating the size of generalized transitive closures, Proceedings of the 15th international conference on Very large data bases, p.165-171, July 1989, Amsterdam, The Netherlands
	L	Hongjun Lu, New Strategies for Computing the Transitive Closure of a Database Relation, Proceedings of the 13th International Conference on Very Large Data Bases, p.267-274, September 01-04, 1987
	MPS	A. Marchetti-Spaccamella , A. Pelaggi , D. Sacca, Worst-case complexity analysis of methods for logic query implementation, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.294-301, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28691]
	MC	A. C. McKellar , E. G. Coffman, Jr., Organizing matrices and matrix operations for paged memory systems, Communications of the ACM, v.12 n.3, p.153-165, March 1969 [doi>10.1145/362875.362879]
	MW	A. O. Mendelzon , P. T. Wood, Finding regular simple paths in graph databases, Proceedings of the 15th international conference on Very large data bases, p.185-193, July 1989, Amsterdam, The Netherlands
	N	J. F. Naughton, One-sided recursions, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.340-348, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28695]
	NRSU	J. F. Naughton , R. Ramakrishnan , Y. Sagiv , J. D. Ullman, Efficient evaluation of right-, left-, and multi-linear rules, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.235-242, June 1989, Portland, Oregon, United States
	RS	N. Robertson, and P. D. Seymour, "Graph Minors XIII: The Disjoint Paths Problem", manuscript, 1986.
	SZ1	Domenico Sacca , Carlo Zaniolo, Magic counting methods, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.49-59, May 27-29, 1987, San Francisco, California, United States
	SZ2	D. Sacca , C. Zaniolo, The generalized counting method for recursive logic queries, Theoretical Computer Science, v.62 n.1-2, p.187-220, December 1988 [doi>10.1016/0304-3975(86)90015-0]
	S	C.P. Schnorr, "An Algorithm for Transitive Closure with Linear Expected Time", SlAM J. Computing, 7(1), pp. 127-133, 1978.
	SeV	R. Sedgewick, and J. S. Vitter, "Shortest Paths in Euclidean Graphs", Proc. 25th IEEE Syrup. on Foundations of Computer Science, pp. 417-424, 1984,
	SV	Y. Shiloah, and U. Vishkin, "An O(logn) parallel connectivity algorithm", J. Algorithms, 3(1), pp. 57- 63, 1982.
	Sh	O. Shmueli, "Dynamic Cycle Detection", Information Processing Letters, 17, pp. 185-188, 1983.
	Si	K Simon, An improved algorithm for transitive closure on acyclic digraphs, International Colloquium on Automata, Languages and Programming on Automata, languages and programming, p.376-386, September 1986, Rennes, France
	SS1	Seppo Sippu , Eljas Soisalon-Soininen, An Optimization Strategy for Recursive Queries in Logic Databases, Proceedings of the Fourth International Conference on Data Engineering, p.470-477, February 01-05, 1988
	SS2	Seppo Sippu , Eljas Soisalon-Soininen, A generalized transitive closure for relational queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.325-332, March 1988, Austin, Texas, United States [doi>10.1145/308386.308467]
	Sz	R. Szelepcsenyi, "The Mehtod of Forcing for Nondeterministic Automata", Bulletin EATCS, 33, pp. 96-100, 1987.
	SU	T.G. Szymanski, and J. D. Ullman, "Evaluating Relational Expressions with Dense and Sparse Arguments", SIAM J. on Computing, 6(1), pp. 109-122, 1977.
	T1	Robert Endre Tarjan, A Unified Approach to Path Problems, Journal of the ACM (JACM), v.28 n.3, p.577-593, July 1981 [doi>10.1145/322261.322272]
	T2	Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981 [doi>10.1145/322261.322273]
	TY	Robert E. Tarjan , Mihalis Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on Computing, v.13 n.3, p.566-579, August 1984 [doi>10.1137/0213035]
	To	Martin Tompa, Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.333-338, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804682]
	U1	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	U2	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	UV	J.D. Ullman, and A. Van Gelder, "Parallel Complexity of Logical Query Programs", Proc. 27th IEEE Syrup. on Foundation of Computer Science, pp. 438- 454, 1986.
	UY1	J.D. Ullman, and M. Yannakakis, "The Input/Output Complexity of Transitive Closure", manuscript, 1989.
	UY2	J.D. Ullman, and M. Yarmakakis, "High-Probability Parallel Transitive Closure Algorithms", manuscript, 1989.
	VK	Patrick Valduriez , Setrag Khoshafian, Parallel evaluation of the transitive closure of a database relation, International Journal of Parallel Programming, v.17 n.1, p.19-42, Feb. 1988 [doi>10.1007/BF01379321]
	V	L.G. Valiant, "General Context-Free Recognition in Less than Cubic Time", J. Computer and System Sc., 10, pp. 308-315, 1975.
	W1	Henry S. Warren, Jr., A modification of Warshall's algorithm for the transitive closure of binary relations, Communications of the ACM, v.18 n.4, p.218-220, April 1975 [doi>10.1145/360715.360746]
	W2	Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]
	Z	M. Zloof, "Query-by-example: Operations on the Transitive Closure", IBM RC 5526, 1976.

CITED BY 26

	Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Thomas Reps, Shape analysis as a generalized path problem, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.1-11, June 21-23, 1995, La Jolla, California, United States
	Shaul Dar , Raghu Ramakrishnan, A performance study of transitive closure algorithms, ACM SIGMOD Record, v.23 n.2, p.454-465, June 1994
	Sanjeev Khanna , Rajeev Motwani , Randall H. Wilson, On certificates and lookahead in dynamic graph problems, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.222-231, January 28-30, 1996, Atlanta, Georgia, United States
	David Melski , Thomas Reps, Interconvertbility of set constraints and context-free language reachability, ACM SIGPLAN Notices, v.32 n.12, p.74-89, Dec. 1997
	G. Ramalingam , Thomas Reps, A categorized bibliography on incremental computation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.502-510, March 1993, Charleston, South Carolina, United States
	Inderpal Singh Mumick , Hamid Pirahesh, Overbound and right-linear queries, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.127-141, May 29-31, 1991, Denver, Colorado, United States
	Håkan Jakobsson, On tree-based techniques for query evaluation, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.380-392, June 02-05, 1992, San Diego, California, United States
	Yanhong A. Liu , Tom Rothamel , Fuxiang Yu , Scott D. Stoller , Nanjun Hu, Parametric regular path queries, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Paul Anderson , Thomas Reps , Tim Teitelbaum, Design and Implementation of a Fine-Grained Software Inspection Tool, IEEE Transactions on Software Engineering, v.29 n.8, p.721-733, August 2003
	Krishnendu Chatterjee , Di Ma , Rupak Majumdar , Tian Zhao , Thomas A. Henzinger , Jens Palsberg, Stack size analysis for interrupt-driven programs, Information and Computation, v.194 n.2, p.144-174, November 1, 2004
	Sergio Flesca , Sergio Greco, Partially ordered regular languages for graph queries, Journal of Computer and System Sciences, v.70 n.1, p.1-25, February 2005
	Joon-Sang Park , Michael Penner , Viktor K. Prasanna, Optimizing Graph Algorithms for Improved Cache Performance, IEEE Transactions on Parallel and Distributed Systems, v.15 n.9, p.769-782, September 2004
	Rajeev Alur , Michael Benedikt , Kousha Etessami , Patrice Godefroid , Thomas Reps , Mihalis Yannakakis, Analysis of recursive state machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.4, p.786-818, July 2005
	Manu Sridharan , Denis Gopan , Lexin Shan , Rastislav Bodík, Demand-driven points-to analysis for Java, ACM SIGPLAN Notices, v.40 n.10, October 2005
	Rajeev Alur , Salvatore La Torre , P. Madhusudan, Modular strategies for recursive game graphs, Theoretical Computer Science, v.354 n.2, p.230-249, 28 March 2006
	Thomas Reps, Undecidability of context-sensitive data-independence analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.1, p.162-186, Jan. 2000
	Phillip G. Bradford, Language constrained graph problems: a microcosm of engineering research and development, Proceedings of the 2nd WSEAS International Conference on Computer Engineering and Applications, p.71-76, January 25-27, 2008, Acapulco, Mexico
	Jakob Rehof , Manuel Fähndrich, Type-base flow analysis: from polymorphic subtyping to CFL-reachability, ACM SIGPLAN Notices, v.36 n.3, p.54-66, March 2001
	Swarat Chaudhuri, Subcubic algorithms for recursive state machines, ACM SIGPLAN Notices, v.43 n.1, January 2008
	H. V. Jagadish, Database research at AT&T Bell Laboratories, ACM SIGMOD Record, v.22 n.1, p.82-88, March 1993
	Mihalis Yannakakis, Perspectives on database theory, ACM SIGACT News, v.27 n.3, p.25-49, Sept. 1996
	Miranda Mowbray , Antonio Lain, Dominator-tree analysis for distributed authorization, Proceedings of the third ACM SIGPLAN workshop on Programming languages and analysis for security, June 07-13, 2008, Tucson, AZ, USA
	Renzo Angles , Claudio Gutierrez, Survey of graph database models, ACM Computing Surveys (CSUR), v.40 n.1, p.1-39, February 2008
	Faisal Alkhateeb , Jean-François Baget , Jérôme Euzenat, Extending SPARQL with regular expression patterns (for querying RDF), Web Semantics: Science, Services and Agents on the World Wide Web, v.7 n.2, p.57-73, April, 2009