ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Optimal implementation of conjunctive queries in relational data bases
Full text PdfPdf (821 KB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the ninth annual ACM symposium on Theory of computing table of contents
Boulder, Colorado, United States
Pages: 77 - 90  
Year of Publication: 1977
Authors
Ashok K. Chandra
Philip M. Merlin
Sponsors
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 33,   Downloads (12 Months): 159,   Citation Count: 246
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/800105.803397
What is a DOI?

ABSTRACT

We define the class of conjunctive queries in relational data bases, and the generalized join operator on relations. The generalized join plays an important part in answering conjunctive queries, and it can be implemented using matrix multiplication. It is shown that while answering conjunctive queries is NP complete (general queries are PSPACE complete), one can find an implementation that is within a constant of optimal. The main lemma used to show this is that each conjunctive query has a unique minimal equivalent query (much like minimal finite automata).


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.

1
M. M. Astrahan , E. B. Altman , P. L. Fehder , M. E. Senko, Concepts of a Data Independent Accessing Model, Proceedings of 1972 ACM-SIGFIDET workshop on Data description, access and control, p.349-362, January 1972  [doi>10.1145/800295.811497]
 
2
V. L. Arlazarov, E. A. Denic, M. A. Kronrad and I. A. Faradzev, "On economical construction of the transitive closure of a directed graph", Dokl. Akad. Nauk SSSR 194 (1970) 487-488. English translation in Soviet Math. Dokl. 11 , 5, 1209-1210.
3
R. F. Boyce , D. D. Chamberlin , M. M. Hammer , W. F. King, Specifying queries as relational expressions, Proceedings of the 1973 meeting on Programming languages and information retrieval, p.31-47, November 04-06, 1973, Gaithersburg, Maryland
4
E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970  [doi>10.1145/362384.362685]
 
5
E. F. Codd, "Further normalization of the data base relational model", Courant CS Symposia, 6, Data Base Systems, Prentice-Hall (May 1971).
 
6
E. F. Codd, "Relational completeness of data base sublanguages", Courant CS Symposia, 6, Data Base Systems, Prentice-Hall, (May 1971).
 
7
E. F. Codd, "A data base sublanguage founded on the relational calculus", PROC. 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego (Nov. 1971).
 
8
E. F. Codd, "Recent investigations in relational data base systems", IFIP74, North Holland, 1974, 1017-1021.
 
9
E. F. Codd, Ed., "Implementation of relational data base management systems", Panel Discussion, NCC (AFIPS) 75, Anaheim (May 1975).
 
10
D. D. Chamberlin and R. F. Boyce, "SEQUEL" "A structured English query language", IBM Technical Report RJ1394 (May 1974).
 
11
L. Clough, W. D. Haseman and Y. H. So, "Designing optimal data structures", AFIPS 76, 45 829-837.
12
C. J. Date , E. F. Codd, The relational and network approaches: Comparison of the application programming interfaces, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control: Data models: Data-structure-set versus relational, p.83-113, May 01-03, 0074, Ann Arbor, Michigan  [doi>10.1145/800297.811532]
 
13
C. Deheneffe, H. Hennebert, W. Paulus, "Relational model for a data base", IFIP 74, North Holland, 1974, 1022-1025.
 
14
M. J. Fischer and A. R. Meyer, "Boolean matrix multiplication and transitive closure," 12th SWAT, IEEE (1971), 129-131.
15
Leo R. Gotlieb, Computing joins of relations, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California  [doi>10.1145/500080.500089]
 
16
I. J. Heath, "Unacceptable file operations in relational data base", Proc. 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego (Nov. 1971).
 
17
A. D. Held, M. R. Stonebraker and E. Wong, "INGRES - A relational data base system", AFIPS 75, 44 409-416.
 
18
Dexter Kozen, Complexity of Finitely Presented Algebras, Cornell University, Ithaca, NY, 1976
 
19
D. McLeod and M. Meldman, "RISS - A generalized minicomputer relational data base management system", AFIPS 1975, 44, 397-402.
 
20
J. Mylopoulos, J. S. Schuster, D. Tsichritzis, "A multi-level relational system", AFIPS 1975, 44, 403-408.
 
21
K. E. Niebuhr and S. E. Smith, "Initial implementation of Query by Example", IBM Technical Report (to appear).
 
22
J. B. Rothnie, Jr., "Evaluating inter-entry retrieval expressions in a relational data base management system", AFIPS 75, 44, 417-423.
 
23
V. Strassen, "Gaussian elimination is not optimal", Numerische Mathematik 13 (1969) 354-356.
24
John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975  [doi>10.1145/361020.361025]
 
25
S.J.P. Todd, "Implementation of the join operator in relational data bases", IBM U.K. Scientific Centre, Technical Note 15, Peterlee (1974).
 
26
S.J.P. Todd, "The Peterlee Relational Test Vehicle - a system overview", IBM Systems Journal 15, 4, 1976, 285-308.
 
27
J. C. Thomas and J. D. Gould, "A psychological study of query by example", AFIPS 75, 44, 439-445.
 
28
M. M. Zloof, "Query by Example", AFIPS 75, 44, 431-438.

CITED BY  246
Stavros Cosmadakis , Haim Gaifman , Paris Kanellakis , Moshe Vardi, Decidable optimization problems for database logic programs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.477-490, May 02-04, 1988, Chicago, Illinois, United States
Ashok K. Chandra, Theory of database queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-9, March 1988, Austin, Texas, United States
Martin Grohe, The parameterized complexity of database queries, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.82-92, May 2001, Santa Barbara, California, United States
Yaron Kanza , Werner Nutt , Yehoshua Sagiv, Queries with incomplete answers over semistructured data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.227-236, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
Yehoshua Sagiv, Evaluation of queries in independent database schemes, Journal of the ACM (JACM), v.38 n.1, p.120-161, Jan. 1991
Oliver M. Duschka , Michael R. Genesereth, Answering recursive queries using views, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-116, May 11-15, 1997, Tucson, Arizona, United States
Dick Tsur , Jeffrey D. Ullman , Serge Abiteboul , Chris Clifton , Rajeev Motwani , Svetlozar Nestorov , Arnon Rosenthal, Query flocks: a generalization of association-rule mining, ACM SIGMOD Record, v.27 n.2, p.1-12, June 1998
Phokion G. Kolaitis , David L. Martin , Madhukar N. Thakur, On the complexity of the containment problem for conjunctive queries with built-in predicates, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.197-204, June 01-04, 1998, Seattle, Washington, United States
Dongwon Lee , Wesley W. Chu, Semantic caching via query matching for web sources, Proceedings of the eighth international conference on Information and knowledge management, p.77-85, November 02-06, 1999, Kansas City, Missouri, United States
David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979
Yannis E. Ioannidis , Eugene Wong, Towards an algebraic theory of recursion, Journal of the ACM (JACM), v.38 n.2, p.329-381, April 1991
Foto Afrati , Chen Li , Prasenjit Mitra, Answering queries using views with arithmetic comparisons, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Surajit Chaudhuri, Optimization of real conjunctive queries, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-70, May 25-28, 1993, Washington, D.C., United States
Surajit Chaudhuri, Finding nonrecursive envelopes for Datalog predicate, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.135-146, May 25-28, 1993, Washington, D.C., United States
Sushant Jain , Ratul Mahajan , Dan Suciu, Translating XSLT programs to Efficient SQL queries, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA
Y. P. Saraiya, Linearising nonlinear recursions in polynomial time, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.182-189, March 1989, Philadelphia, Pennsylvania, United States
Moshe Y. Vardi, On the complexity of bounded-variable queries (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.266-276, May 22-25, 1995, San Jose, California, United States
S. S. Cosmadakis, On the first-order expressibility of recursive queries, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.311-323, March 1989, Philadelphia, Pennsylvania, United States
Surajit Chaudhuri , Phokion G. Kolaitis, Can Datalog be approximated?, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.86-96, May 24-27, 1994, Minneapolis, Minnesota, United States
Jeff Naughton, Data independent recursion in deductive databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.267-279, March 24-26, 1986, Cambridge, Massachusetts, United States
Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001
Sihem Amer-Yahia , SungRan Cho , Laks V. S. Lakshmanan , Divesh Srivastava, Minimization of tree pattern queries, ACM SIGMOD Record, v.30 n.2, p.497-508, June 2001
Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981
Alberto O. Mendelzon, Database states and their tableaux, ACM Transactions on Database Systems (TODS), v.9 n.2, p.264-282, June 1984
Gerome Miklau , Dan Suciu, Containment and equivalence for an XPath fragment, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Prakash Ramanan, Efficient algorithms for minimizing tree pattern queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
Alon Y. Levy , Dan Suciu, Deciding containment for queries with complex objects (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.20-31, May 11-15, 1997, Tucson, Arizona, United States
Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman, Answering queries using templates with binding patterns (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.105-112, May 22-25, 1995, San Jose, California, United States
Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984
Anthony Klug, Locking Expressions for Increased Database Concurrency, Journal of the ACM (JACM), v.30 n.1, p.36-54, Jan. 1983
Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980
Ashok K. Chandra , David Harel, Computable queries for relational data bases (Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.309-318, April 30-May 02, 1979, Atlanta, Georgia, United States
F. Angiulli , R. Ben-Eliyahu-Zohary , L. Palopoli , G. B. Ianni, Computational properties of metaquerying problems, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.237-244, May 15-18, 2000, Dallas, Texas, United States
Phokion G. Kolaitis , Moshe Y. Vardi, Conjunctive-query containment and constraint satisfaction, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.205-213, June 01-04, 1998, Seattle, Washington, United States
Haim Gaifman , Harry Mairson , Yehoshua Sagiv , Moshe Y. Vardi, Undecidable optimization problems for database logic programs, Journal of the ACM (JACM), v.40 n.3, p.683-713, July 1993
Paolo Liberatore, Monotonic reductions, representative equivalence, and compilation of intractable problems, Journal of the ACM (JACM), v.48 n.6, p.1091-1125, November 2001
T. Imielinski , K. Vadaparty, Complexity of query processing in databases with OR-objects, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.51-65, March 1989, Philadelphia, Pennsylvania, United States
R. van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-345, June 02-05, 1992, San Diego, California, United States
Christos H. Papadimitriou , Mihalis Yannakakis, On the complexity of database queries (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.12-19, May 11-15, 1997, Tucson, Arizona, United States
Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States
Martin K. Solomon, Some properties of relational expressions, Proceedings of the 17th annual Southeast regional conference, p.111-116, April 09-11, 1979, Orlando, Florida
R. Ramakrishnan , Y. Sagiv , J. D. Ullman , M. Y Vardi, Proof-tree transformation theorems and their applications, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.172-181, March 1989, Philadelphia, Pennsylvania, United States
Marc Andries , Luca Cabibbo , Jan Paredaens , Jan Van den Bussche, Applying an update method to a set of receivers (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.208-218, May 22-25, 1995, San Jose, California, United States
Werner Nutt , Yehoshus Sagiv , Sara Shurin, Deciding equivalences among aggregate queries, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-223, June 01-04, 1998, Seattle, Washington, United States
Maarten Marx, Conditional XPath, the first order complete XPath dialect, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
Foto N. Afrati , Chen Li , Jeffrey D. Ullman, Generating efficient plans for queries using views, ACM SIGMOD Record, v.30 n.2, p.319-330, June 2001
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
Jeffrey F. Naughton, Minimizing function-free recursive inference rules, Journal of the ACM (JACM), v.36 n.1, p.69-91, Jan. 1989
Catriel Beeri , Alberto O. Mendelzon , Yehoshua Sagiv , Jeffrey D. Ullman, Equivalence of relational database schemes, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.319-329, April 30-May 02, 1979, Atlanta, Georgia, United States
M. Muralikrishna , David J. DeWitt, Optimization of multiple-relation multiple-disjunct queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.263-275, March 1988, Austin, Texas, United States
David Harel , Hagi Lachover , Amnon Naamad , Amir Pnueli , Michal Politi , Rivi Sherman , Aharon Shtull-Trauring , Mark Trakhtenbrot, STATEMATE: a working environment for the development of complex reactive systems, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
D. Cantone , V. Cutello, A decidable fragment of the elementary theory of relations and some applications, Proceedings of the international symposium on Symbolic and algebraic computation, p.24-29, August 20-24, 1990, Tokyo, Japan
Georg Gottlob , Nicola Leone , Francesco Scarcello, The complexity of acyclic conjunctive queries, Journal of the ACM (JACM), v.48 n.3, p.431-498, May 2001
Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States
Chen Li , Edward Chang, Answering queries with useful bindings, ACM Transactions on Database Systems (TODS), v.26 n.3, p.313-343, September 2001
Serge Abiteboul, Disaggregations in databases, Journal of the ACM (JACM), v.32 n.1, p.79-101, Jan. 1985
Oliver M. Duschka , Michael R. Genesereth, Query planning in infomaster, Proceedings of the 1997 ACM symposium on Applied computing, p.109-111, April 1997, San Jose, California, United States
Y. Sagiv, Optimizing datalog programs, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.349-362, March 23-25, 1987, San Diego, California, United States
Edward P. F. Chan, Containment and minimization of positive conjunctive queries in OODB's, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.202-211, June 02-05, 1992, San Diego, California, United States
Georg Gottlob , Nicola Leone , Francesco Scarcello, Hypertree decompositions and tractable queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.21-32, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
Anthony Klug , Rod Price, Determining View dependencies using tableaux, ACM Transactions on Database Systems (TODS), v.7 n.3, p.361-380, Sept. 1982
Moshe Vardi, On the integrity of databases with incomplete information, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.252-266, March 24-26, 1986, Cambridge, Massachusetts, United States
Todd Millstein , Alon Levy , Marc Friedman, Query containment for data integration systems, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.67-75, May 15-18, 2000, Dallas, Texas, United States
Yannis E. Ioannidis , Raghu Ramakrishnan, Containment of conjunctive queries: beyond relations as sets, ACM Transactions on Database Systems (TODS), v.20 n.3, p.288-324, Sept. 1995
Daniela Florescu , Alon Levy , Dan Suciu, Query containment for conjunctive queries with regular expressions, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.139-148, June 01-04, 1998, Seattle, Washington, United States
F. Afrati , S. S. Cosmadakis, Expressiveness of restricted recursive queries, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.113-126, May 14-17, 1989, Seattle, Washington, United States
D. S. Johnson , A. Klug, Testing containment of conjunctive queries under functional and inclusion dependencies, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California
Shinichi Morishita, Avoiding Cartesian products for multiple joins, Journal of the ACM (JACM), v.44 n.1, p.57-85, Jan. 1997
Thane Plambeck, Semigroup techniques in recursive query optimization, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.145-153, April 02-04, 1990, Nashville, Tennessee, United States
Yatin P. Saraiya, Polynomial-time program transformations in deductive databases, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.132-144, April 02-04, 1990, Nashville, Tennessee, United States
D. Harel , H. Lachover , A. Naamad , A. Pnueli , M. Politi , R. Sherman , a. Shtul-Trauring, Statemate: a working environment for the development of complex reactive systems, Proceedings of the 10th international conference on Software engineering, p.396-406, April 11-15, 1988, Singapore
Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988
Sara Cohen , Werner Nutt , Alexander Serebrenik, Rewriting aggregate queries using views, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.155-166, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
Yatin P. Saraiya, Hard problems for simple logic programs, ACM SIGMOD Record, v.19 n.2, p.64-73, Jun. 1990
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
Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, On the decidability of query containment under constraints, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.149-158, June 01-04, 1998, Seattle, Washington, United States
Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States
Giuseppe De Giacomo , Hector Levesque, Two approaches to efficient open-world reasoning, Logic-based artificial intelligence, Kluwer Academic Publishers, Norwell, MA, 2000
Yannis Papakonstantinou , Vasilis Vassalos, Query rewriting for semistructured data, ACM SIGMOD Record, v.28 n.2, p.455-466, June 1999
Ashok K. Chandra, Programming primitives for database languages, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.50-62, January 26-28, 1981, Williamsburg, Virginia
Ashish Gupta , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom, Constraint checking with partial information, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.45-55, May 24-27, 1994, Minneapolis, Minnesota, United States
Alon Y. Levy , Anand Rajaraman , Jeffrey D. Ullman, Answering queries using limited external query processors (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-237, June 04-06, 1996, Montreal, Quebec, Canada
Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984
Alon Y. Levy, Logic-based techniques in data integration, Logic-based artificial intelligence, Kluwer Academic Publishers, Norwell, MA, 2000
Isabel F. Cruz , Alberto O. Mendelzon , Peter T. Wood, A graphical query language supporting recursion, ACM SIGMOD Record, v.16 n.3, p.323-330, Dec. 1987
Stavros S. Cosmadakis, The complexity of evaluating relational queries, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
Moshe Y. Vardi, Decidability and undecidability results for boundedness of linear recursive queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.341-351, March 1988, Austin, Texas, United States
Richard Hull , Masatoshi Yoshikawa, On the equivalence of database restructurings involving object identifiers (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.328-340, May 29-31, 1991, Denver, Colorado, United States
Moshe Y. Vardi, Constraint satisfaction and database theory: a tutorial, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.76-85, May 15-18, 2000, Dallas, Texas, United States
Matthias Jarke , Jürgen Koch, Range nesting: a fast method to evaluate quantified queries, ACM SIGMOD Record, v.13 n.4, May 1983
Anthony Klug, Access paths in the "Abe" statistical query facility, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida
Georg Lausen , Fang Wei, On the containment of conjunctive queries, Computer science in perspective, Springer-Verlag New York, Inc., New York, NY, 2003
Franz Baader , Diego Calvanese , Deborah L. McGuinness , Daniele Nardi , Peter F. Patel-Schneider, Bibliography, The description logic handbook: theory, implementation, and applications, Cambridge University Press, New York, NY, 2003
Rada Chirkova , Chen Li, Materializing views with minimal size to answer queries, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.38-48, June 09-11, 2003, San Diego, California
Andrea Calí , Domenico Lembo , Maurizio Lenzerini , Riccardo Rosati, Source integration for data warehousing, Multidimensional databases: problems and solutions, Idea Group Publishing, Hershey, PA, 2003
Georg Gottlob , Nicola Leone , Francesco Scarcello, Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width, Journal of Computer and System Sciences, v.66 n.4, p.775-808, 1 June 2003
Ji-Hoon Kang , Ki-Hyung Hong , Kyu-Young Whang , Jung-Wan Cho, Generalization of ZYT-linearizability for bilinear datalog programs, Information and Computation, v.188 n.1, p.77-98, 10 January 2004
Thomas Schwentick, XPath query containment, ACM SIGMOD Record, v.33 n.1, March 2004
Tomás Feder , Florent Madelaine , Iain A. Stewart, Dichotomies for classes of homomorphism problems involving unary functions, Theoretical Computer Science, v.314 n.1, p.1-43, 25 February 2004
D. Calvanese , G. De Giacomo , M. Lenzerini , M. Y. Vardi, Reasoning on regular path queries, ACM SIGMOD Record, v.32 n.4, December 2003
Oscar H. Ibarra , Jianwen Su, On the containment and equivalence of database queries with linear constraints (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.32-43, May 11-15, 1997, Tucson, Arizona, United States
A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979
Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, June 01-04, 1998, Seattle, Washington, United States
Georg Gottlob , Nicola Leone , Francesco Scarcello, Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.195-206, May 2001, Santa Barbara, California, United States
Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984
Marc Andries , Luca Cabibbo , Jan Paredaens , Jan van den Bussche, Applying an update method to a set of receivers, ACM Transactions on Database Systems (TODS), v.26 n.1, p.1-40, March 2001
Gerome Miklau , Dan Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM (JACM), v.51 n.1, p.2-45, January 2004
Martin Grohe, Parameterized complexity for the database theorist, ACM SIGMOD Record, v.31 n.4, December 2002
Li Chen , Song Wang , Elke A. Rundensteiner, Replacement strategies for XQuery caching systems, Data & Knowledge Engineering, v.49 n.2, p.145-175, May 2004
Francesco Scarcello , Gianluigi Greco , Nicola Leone, Weighted hypertree decompositions and optimal query plans, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
Ernest Teniente , Toni Urpí, Checking query containment with the CQC method, Data & Knowledge Engineering, v.53 n.2, p.163-223, May 2005
David Harel , Amir Pnueli , Hagi Lachover , Amnon Naamad , Michal Politi , Rivi Sherman , Aharon Shtull-Trauring , Mark Trakhtenbrot, STATEMATE: A Working Environment for the Development of Complex Reactive Systems, IEEE Transactions on Software Engineering, v.16 n.4, p.403-414, April 1990
Gösta Grahne , Victoria Kiricenko, Towards an algebraic theory of information integration, Information and Computation, v.194 n.2, p.79-100, November 1, 2004
Dan Suciu, On database theory and XML, ACM SIGMOD Record, v.30 n.3, September 2001
Alan Nash , Bertram Ludäscher, Processing first-order queries under limited access patterns, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
Tiziana Catarci , Shi-Kuo Chang , Maria F. Costabile , Stefano Levialdi , Giuseppe Santucci, A Graph-Based Framework for Multiparadigmatic Visual Access to Databases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.3, p.455-475, June 1996
Xubo Zhang , Z. Meral Ozsoyoglu, Implication and Referential Constraints: A New Formal Reasoning, IEEE Transactions on Knowledge and Data Engineering, v.9 n.6, p.894-910, November 1997
Claude Delobel , Chantal Reynaud , Marie-Christine Rousset , Jean-Pierre Sirot , Dan Vodislav, Semantic integration in Xyleme: a uniform tree-based approach, Data & Knowledge Engineering, v.44 n.3, p.267-298, March 2003
Laks V. S. Lakshmanan , Nematollaah Shiri, A Parametric Approach to Deductive Databases with Uncertainty, IEEE Transactions on Knowledge and Data Engineering, v.13 n.4, p.554-570, July 2001
Nan Zhang , Mark Ryan , Dimitar P. Guelev, Synthesising verified access control systems in XACML, Proceedings of the 2004 ACM workshop on Formal methods in security engineering, October 29-29, 2004, Washington DC, USA
K. Wang , L. Y. Yuan, First-Order Logic Characterization of Program Properties, IEEE Transactions on Knowledge and Data Engineering, v.6 n.4, p.518-533, August 1994
Georg Gottlob , Christos Papadimitriou, On the complexity of single-rule datalog queries, Information and Computation, v.183 n.1, p.104-122, May 25, 2003
Albert Atserias , Anuj Dawar , Phokion G. Kolaitis, On preservation under homomorphisms and unions of conjunctive queries, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
Diego Calvanese , Giuseppe De Giacomo , Moshe Y. Vardi, Decidable containment of recursive queries, Theoretical Computer Science, v.336 n.1, p.33-56, 25 May 2005
Sara Cohen , Yehoshua Sagiv , Werner Nutt, Equivalences among aggregate queries with negation, ACM Transactions on Computational Logic (TOCL), v.6 n.2, p.328-360, April 2005
Georg Gottlob , Christoph Koch , Klaus U. Schulz, Conjunctive queries over trees, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
Piero A. Bonatti, On the decidability of containment of recursive datalog queries - preliminary report, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
Jan Chomicki , Jerzy Marcinkowski, Minimal-change integrity maintenance using tuple deletions, Information and Computation, v.197 n.1/2, p.90-121, February 25, 2005/March 15, 2005
Cong Yu , Lucian Popa, Semantic adaptation of schema mappings when schemas evolve, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
Rachel Ben-Eliyahu-Zohary , Ehud Gudes , Giovambattista Ianni, Metaqueries: semantics, complexity, and efficient algorithms, Artificial Intelligence, v.149 n.1, p.61-87, September 2003
Wanhong Xu , Z. Meral Özsoyoglu, Rewriting XPath queries using materialized views, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
Sara Cohen, Containment of aggregate queries, ACM SIGMOD Record, v.34 n.1, March 2005
Li Chen , Elke A. Rundensteiner, XQuery containment in presence of variable binding dependencies, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, ACM Transactions on Database Systems (TODS), v.30 n.1, p.174-210, March 2005
Bart Goethals , Eveline Hoekx , Jan Van den Bussche, Mining tree queries in a graph, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Georg Gottlob, Computing cores for data exchange: new algorithms and practical solutions, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
Francesco Scarcello, Query answering exploiting structural properties, ACM SIGMOD Record, v.34 n.3, September 2005
Luc Segoufin , Victor Vianu, Views and queries: determinacy and rewriting, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
Alin Deutsch , Val Tannen, XML Queries and constraints, containment and reformulation, Theoretical Computer Science, v.336 n.1, p.57-87, 25 May 2005
Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005
Maarten Marx, Conditional XPath, ACM Transactions on Database Systems (TODS), v.30 n.4, p.929-959, December 2005
Anthony C. Klug, Abe: a query language for constructing aggregates-by-example, Proceedings of the 1st LBL Workshop on Statistical database management, p.190-205, December 02-04, 1981, Melno Park, California
Alin Deutsch , Lucian Popa , Val Tannen, Query reformulation with constraints, ACM SIGMOD Record, v.35 n.1, March 2006
Phokion G. Kolaitis, Schema mappings, data exchange, and metadata management, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
Murali Mani , Song Wang , Dan Dougherty , Elke A. Rundensteiner, Join minimization in XML-to-SQL translation: an algebraic approach, ACM SIGMOD Record, v.35 n.1, p.20-25, March 2006
Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.90-101, June 09-11, 2003, San Diego, California
Todd Millstein , Alon Halevy , Marc Friedman, Query containment for data integration systems, Journal of Computer and System Sciences, v.66 n.1, p.20-39, 01 February 2003
Prasenjit Mitra, An algorithm for answering queries efficiently using views, Proceedings of the 12th Australasian database conference, p.99-106, January 29-February 01, 2001, Queensland, Australia
Gang Gou , Maxim Kormilitsin , Rada Chirkova, Query evaluation using overlapping views: completeness and efficiency, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
T. S. Jayram , Phokion G. Kolaitis , Erik Vee, The containment problem for <bi>Real</bi> conjunctive queries with inequalities, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
Alon Halevy , Michael Franklin , David Maier, Principles of dataspace systems, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-9, June 26-28, 2006, Chicago, IL, USA
Govind Kabra , Ravishankar Ramamurthy , S. Sudarshan, Redundancy and information leakage in fine-grained access control, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
Sara Cohen, Equivalence of queries combining set and bag-set semantics, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
Marco Cadoli , Toni Mancini, Automated reformulation of specifications by safe delay of constraints, Artificial Intelligence, v.170 n.8, p.779-801, June 2006
Dongwon Lee , Wesley W. Chu, Towards Intelligent Semantic Caching for Web Sources, Journal of Intelligent Information Systems, v.17 n.1, p.23-45, November 2001
Fabrizio Angiulli , Rachel Ben-Eliyahu-Zohary , Giovambattista Ianni , Luigi Palopoli, Computational properties of metaquerying problems, ACM Transactions on Computational Logic (TOCL), v.4 n.2, p.149-180, April 2003
Li Chen , Song Wang , Elizabeth Cash , Burke Ryder , Ian Hobbs , Elke A. Rundensteiner, A fine-grained replacement strategy for XML query cache, Proceedings of the 4th international workshop on Web information and data management, November 08-08, 2002, McLean, Virginia, USA
Jian-Hua Feng , Yu-Guo Liao , Yong Zhang, HCH for checking containment of XPath fragment, Journal of Computer Science and Technology, v.22 n.5, p.736-748, September 2007
Fabrizio Angiulli, Enumerating consistent metaquery instantiations, AI Communications, v.18 n.2, p.117-141, April 2005
Alon Y. Halevy, Theory of answering queries using views, ACM SIGMOD Record, v.29 n.4, p.40-47, Dec. 2000
Ashwin Machanavajjhala , Johannes Gehrke, On the efficiency of checking perfect privacy, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
Georg Gottlob , Alan Nash, Data exchange: computing cores in polynomial time, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
Feng Shao , Antal Novak , Jayavel Shanmugasundaram, Triggers over nested views of relational data, ACM Transactions on Database Systems (TODS), v.31 n.3, p.921-967, September 2006
Stéphane Demri, LTL Over integer periodicity constraints, Theoretical Computer Science, v.360 n.1, p.96-123, 21 August 2006
Andrea Cali , Michael Kifer, Containment of conjunctive object meta-queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Sara Cohen , Itzhak Fadida , Yaron Kanza , Benny Kimelfeld , Yehoshua Sagiv, Full disjunctions: polynomial-delay iterators in action, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Rada Chirkova , Fereidoon Sadri, Query optimization using restructured views, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Nicola Onose , Alin Deutsch , Yannis Papakonstantinou , Emiran Curtmola, Rewriting nested XML queries using nested views, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
Georg Gottlob , Christoph Koch , Klaus U. Schulz, Conjunctive queries over trees, Journal of the ACM (JACM), v.53 n.2, p.238-272, March 2006
Albert Atserias , Anuj Dawar , Phokion G. Kolaitis, On preservation under homomorphisms and unions of conjunctive queries, Journal of the ACM (JACM), v.53 n.2, p.208-237, March 2006
Albert Atserias, Conjunctive query evaluation by search-tree revisited, Theoretical Computer Science, v.371 n.3, p.155-168, March, 2007
Christoph Koch, On the complexity of nonrecursive XQuery and functional query languages on complex values, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1215-1256, December 2006
José Luis Ambite , Dipsy Kapoor, Automatic generation of data processing workflows for transportation modeling, Proceedings of the 8th annual international conference on Digital government research: bridging disciplines & domains, May 20-23, 2007, Philadelphia, Pennsylvania
Ariel Fuxman , Phokion G. Kolaitis , Renée J. Miller , Wang-Chiew Tan, Peer data exchange, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1454-1498, December 2006
Andre Hernich , Nicole Schweikardt, CWA-solutions for data exchange settings with target dependencies, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
Georg Gottlob , Zoltan Miklos , Thomas Schwentick, Generalized hypertree decompositions: np-hardness and tractable variants, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
Stijn Dekeyser , Michael de Raadt , Tien Yu Lee, Computer assisted assessment of SQL query skills, Proceedings of the eighteenth conference on Australasian database, p.53-62, January 30-February 02, 2007, Ballarat, Victoria, Australia
Alin Deutsch , Bertram Ludäscher , Alan Nash, Rewriting queries using views with access patterns under integrity constraints, Theoretical Computer Science, v.371 n.3, p.200-226, March, 2007
Martin Grohe, The complexity of homomorphism and constraint satisfaction problems seen from the other side, Journal of the ACM (JACM), v.54 n.1, p.1-es, March 2007
Francesco Scarcello , Gianluigi Greco , Nicola Leone, Weighted hypertree decompositions and optimal query plans, Journal of Computer and System Sciences, v.73 n.3, p.475-506, May, 2007
Sara Cohen , Werner Nutt , Yehoshua Sagiv, Deciding equivalences among conjunctive aggregate queries, Journal of the ACM (JACM), v.54 n.2, p.5-es, April 2007
S. Flesca , F. Furfaro , E. Masciari, On the minimization of XPath queries, Journal of the ACM (JACM), v.55 n.1, p.1-46, February 2008
Georg Gottlob , Alan Nash, Efficient core computation in data exchange, Journal of the ACM (JACM), v.55 n.2, p.1-49, May 2008
Yehoshua Sagiv , Mihalis Yannakakis, Equivalence among relational expressions with the union and difference operation, Proceedings of the fourth international conference on Very Large Data Bases, p.535-548, September 13-15, 1978, West Berlin, Germany
Daniel J. Rosenkrantz , Harry B. Hunt III, Processing conjunctive predicates and queries, Proceedings of the sixth international conference on Very Large Data Bases, p.64-72, October 01-03, 1980, Montreal, Quebec, Canada
Hervé Gallaire, Impacts of logic and databases (invited paper), Proceedings of the seventh international conference on Very Large Data Bases, p.248-259, September 09-11, 1981, Cannes, France
Xin Dong , Alon Y. Halevy , Igor Tatarinov, Containment of nested XML queries, Proceedings of the Thirtieth international conference on Very large data bases, p.132-143, August 31-September 03, 2004, Toronto, Canada
Jayant Madhavan , Alon Y. Halevy, Composing mappings among data sources, Proceedings of the 29th international conference on Very large data bases, p.572-583, September 09-12, 2003, Berlin, Germany
Rajasekar Krishnamurthy , Raghav Kaushik , Jeffrey F. Naughton, Efficient XML-to-SQL query translation: where to add the intelligence?, Proceedings of the Thirtieth international conference on Very large data bases, p.144-155, August 31-September 03, 2004, Toronto, Canada
Alin Deutsch , Yannis Papakonstantinou , Yu Xu, The NEXT framework for logical XQuery optimization, Proceedings of the Thirtieth international conference on Very large data bases, p.168-179, August 31-September 03, 2004, Toronto, Canada
S. Flesca , F. Furfaro , E. Masciari, On the minimization of Xpath queries, Proceedings of the 29th international conference on Very large data bases, p.153-164, September 09-12, 2003, Berlin, Germany
Michalis Petropoulos , Alin Deutsch , Yannis Papakonstantinou , Yannis Katsis, Exporting and interactively querying Web service-accessed sources: The CLIDE System, ACM Transactions on Database Systems (TODS), v.32 n.4, p.22-es, November 2007
Todd J. Green , Grigoris Karvounarakis , Val Tannen, Provenance semirings, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
Foto N. Afrati , Chen Li , Jeffrey D. Ullman, Using views to generate efficient evaluation plans for queries, Journal of Computer and System Sciences, v.73 n.5, p.703-724, August, 2007
Rachel Pottinger , Alon Halevy, MiniCon: A scalable algorithm for answering queries using views, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.182-198, September 2001
S. Amer-Yahia , S. Cho , L. V. S. Lakshmanan , D. Srivastava, Tree pattern query minimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.315-331, December 2002
Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001
Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis, The GMAP: a versatile tool for physical data independence, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.2, p.101-118, April 1996
Rada Chirkova , Chen Li , Jia Li, Answering queries using materialized views with minimum size, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.3, p.191-210, September 2006
Sara Cohen , Werner Nutt , Yehoshua Sagiv, Equivalences among aggregate queries with negation, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.215-226, May 2001, Santa Barbara, California, United States
Martin Groher , Thomas Schwentick , Luc Segoufin, When is the evaluation of conjunctive queries tractable?, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.657-666, July 2001, Hersonissos, Greece
Aditya N. Saharia , Yair M. Babad, Enhancing data warehouse performance through query caching, ACM SIGMIS Database, v.31 n.2, p.43-63, Spring 2000
Foto Afrati , Vassia Pavlaki, Rewriting queries using views with negation, AI Communications, v.19 n.3, p.229-237, August 2006
Rachel Pottinger , Alon Y. Levy, A Scalable Algorithm for Answering Queries Using Views, Proceedings of the 26th International Conference on Very Large Data Bases, p.484-495, September 10-14, 2000
Nam Huyn, Multiple-View Self-Maintenance in Data Warehousing Environments, Proceedings of the 23rd International Conference on Very Large Data Bases, p.26-35, August 25-29, 1997
Y. E. Ioannidis, Commutativity and its role in the processing of linear recursion, Proceedings of the 15th international conference on Very large data bases, p.155-163, July 1989, Amsterdam, The Netherlands
Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis, The GMAP: A Versatile Tool for Physical Data Independence, Proceedings of the 20th International Conference on Very Large Data Bases, p.367-378, September 12-15, 1994
J. F. Naughton , R. Ramakrishnan , J. D. Ullman, Argument reduction by factoring, Proceedings of the 15th international conference on Very large data bases, p.173-182, July 1989, Amsterdam, The Netherlands
Alon Y. Levy, Obtaining Complete Answers from Incomplete Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.402-412, September 03-06, 1996
Sin Yeung Lee , Tok Wang Ling, Further Improvements on Integrity Constraint Checking for Stratifiable Deductive Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.495-505, September 03-06, 1996
Richard Hull , Masatoshi Yoshikawa, ILOG: Declarative Creation and Manipulation of Object Identifiers, Proceedings of the 16th International Conference on Very Large Data Bases, p.455-468, August 13-16, 1990
Alin Deutsch , Lucian Popa , Val Tannen, Physical Data Independence, Constraints, and Optimization with Universal Plans, Proceedings of the 25th International Conference on Very Large Data Bases, p.459-470, September 07-10, 1999
Foto Afrati , Chen Li , Vassia Pavlaki, Data exchange in the presence of arithmetic comparisons, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
Aditya N. Saharia , Yair M. Babad, Enhancing data warehouse performance through query caching, ACM SIGMIS Database, v.31 n.3, p.43-63, Summer 2000
Chen Li, Computing complete answers to queries in the presence of limited access patterns, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.3, p.211-227, October 2003
Mihalis Yannakakis, Perspectives on database theory, ACM SIGACT News, v.27 n.3, p.25-49, Sept. 1996
John Grant , Jack Minker, A logic-based approach to data integration, Theory and Practice of Logic Programming, v.2 n.3, p.323-368, May 2002
Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Conjunctive query containment and answering under description logic constraints, ACM Transactions on Computational Logic (TOCL), v.9 n.3, p.1-31, June 2008
Benjamin Rossman, Homomorphism preservation theorems, Journal of the ACM (JACM), v.55 n.3, p.1-53, July 2008
Isolde Adler, Tree-width and functional dependencies in databases, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
Stéphane Demri , Régis Gascon, Verification of qualitative Z constraints, Theoretical Computer Science, v.409 n.1, p.24-40, December, 2008
Benny Kimelfeld , Yehoshua Sagiv, Revisiting redundancy and minimization in an XPath fragment, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
Gábor Kun , Jaroslav Nešetřil, Forbidden lifts (NP and CSP for combinatorialists), European Journal of Combinatorics, v.29 n.4, p.930-945, May, 2008
Simona Perri , Francesco Scarcello , Gelsomina Catalano , Nicola Leone, Enhancing DLV instantiator by backjumping techniques, Annals of Mathematics and Artificial Intelligence, v.51 n.2-4, p.195-228, December 2007
Nan Zhang , Mark Ryan , Dimitar P. Guelev, Synthesising verified access control systems through model checking, Journal of Computer Security, v.16 n.1, p.1-61, January 2008
Magdalena Ortiz , Diego Calvanese , Thomas Eiter, Data Complexity of Query Answering in Expressive Description Logics via Tableaux, Journal of Automated Reasoning, v.41 n.1, p.61-98, July 2008
Alin Deutsch , Alan Nash , Jeff Remmel, The chase revisited, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
Hala Mostafa , Victor Lesser , Gerome Miklau, Self-interested database managers playing the view maintenance game, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
Fang Wei , Georg Lausen, A unified apriori-like algorithm for conjunctive query containment, Proceedings of the 2008 international symposium on Database engineering & applications, September 10-12, 2008, Coimbra, Portugal
Dongfeng Chen , Rada Chirkova , Fereidoon Sadri, Query optimization using restructured views: Theory and experiments, Information Systems, v.34 n.3, p.353-370, May, 2009
Essam Mansour , Hagen Höpfner, An approach to detecting relevant updates to cached data using XML and active databases, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
Rada Chirkova , Michael R. Genesereth, Equivalence of SQL queries in presence of embedded dependencies, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
Andrea Calì , Georg Gottlob , Thomas Lukasiewicz, Datalog±: a unified approach to ontologies and integrity constraints, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia
Andrea Calì , Georg Gottlob , Thomas Lukasiewicz, A general datalog-based framework for tractable query answering over ontologies, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
Todd J. Green , Zachary G. Ives , Val Tannen, Reconcilable differences, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia
Todd J. Green, Containment of conjunctive queries on annotated relations, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia
Faiz Currim , Eunjin Jung , Xin Xiao , Insoon Jo, Privacy policy enforcement for health information data access, Proceedings of the 1st ACM international workshop on Medical-grade wireless networks, May 18-18, 2009, New Orleans, Louisiana, USA
Georg Gottlob , Stephanie Tien Lee , Gregory J. Valiant, Size and treewidth bounds for conjunctive queries, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
Yolifé Arvelo , Blai Bonet , María Esther Vidal, Compilation of query-rewriting problems into tractable fragments of propositional logic, Proceedings of the 21st national conference on Artificial intelligence, p.225-230, July 16-20, 2006, Boston, Massachusetts
Sara Cohen, Equivalence of queries that are sensitive to multiplicities, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.3, p.765-785, June 2009
Yongmei Liu , Hector J. Levesque, A tractability result for reasoning with incomplete first-order knowledge bases, Proceedings of the 18th international joint conference on Artificial intelligence, p.83-88, August 09-15, 2003, Acapulco, Mexico
David DeHaan, Equivalence of nested queries with mixed semantics, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
Mark James Carman , Craig A. Knoblock, Learning semantic definitions of online information sources, Journal of Artificial Intelligence Research, v.30 n.1, p.1-50, September 2007
Jean-Françs Baget , Marie-Laure Mugnier, Extensions of simple conceptual graphs: the complexity of rules and constraints, Journal of Artificial Intelligence Research, v.16 n.1, p.425-465, January 2002
Phokion G. Kolaitis, Constraint satisfaction, databases, and logic, Proceedings of the 18th international joint conference on Artificial intelligence, p.1587-1595, August 09-15, 2003, Acapulco, Mexico

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases


General Terms:
Languages, Management, Theory

Collaborative Colleagues:
Ashok K. Chandra: colleagues
Philip M. Merlin: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player