×
Gottlob, Georg; Koch, Christoph; Schulz, Klaus U.

Conjunctive queries over trees. (English) Zbl 1326.68110

J. ACM 53, No. 2, 238-272 (2006).

Cited in 15 Documents

MSC:

68P05 Data structures
03B70 Logic in computer science
68P15 Database theory
68Q25 Analysis of algorithms and problem complexity

Keywords:

complexity; expressiveness; succinctness; conjunctive queries; trees; XML
Cite Review PDF
Full Text: DOI Link

References:

[1] Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley, Reading, MA.]] · Zbl 0848.68031
[2] Baumgartner, R., Flesca, S., and Gottlob, G. 2001. Visual Web information extraction with Lixto. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB) (Rome, Italy). 119-128.]]
[3] Benedikt, M., Fan, W., and Kuper, G. 2003. Structural properties of XPath fragments. In Proceedings of the 9th International Conference on Database Theory (ICDT) (Siena, Italy). 79-95.]] · Zbl 1022.68503
[4] Bodirsky, M., Duchier, D., Niehren, J., and Miele, S. 2004. A new algorithm for normal dominance constraints. In Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (New Orleans, LA). ACM, New York, 59-67.]] · Zbl 1318.05071
[5] Chandra, A. K., and Merlin, P. M. 1977. Optimal implementation of conjunctive queries in relational data bases. In Conference Record of the 9th Annual ACM Symposium on Theory of Computing (STOC’77) (Boulder, CO). ACM, New York, 77-90.]]
[6] Chekuri, C., and Rajaraman, A. 1997. Conjunctive query containment revisited. In Proceedings of the 6th International Conference on Database Theory (ICDT) (Delphi, Greece). 56-70.]]
[7] Dechter, R. 2003. Constraint Processing. Morgan Kaufmann, San Francisco, CA.]]
[8] Deutsch, A., and Tannen, V. 2003a. MARS: A system for publishing XML from mixed and redundant storage. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB) (Berlin, Germany), 201-212.]]
[9] Deutsch, A., and Tannen, V. 2003b. Reformulation of XML queries and constraints. In Proceedings of the 9th International Conference on Database Theory (ICDT). 225-241.]] · Zbl 1022.68507
[10] Ebbinghaus, H.-D., and Flum, J. 1999. Finite Model Theory. 2nd ed. Springer-Verlag, New York.]] · Zbl 0932.03032
[11] Flum, J., Frick, M., and Grohe, M. 2002. Query evaluation via tree-decompositions. J. ACM 49, 6, 716-752.]] · Zbl 1326.68123
[12] Gottlob, G., and Koch, C. 2002. Monadic queries over tree-structured data. In Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science (LICS) (Copenhagen, Denmark). IEEE Computer Society Press, Los Alamitos, CA, 189-202.]]
[13] Gottlob, G., and Koch, C. 2004. Monadic datalog and the expressive power of Web information extraction languages. J. ACM 51, 1, 74-113.]] · Zbl 1316.68045
[14] Gottlob, G., Koch, C., and Pichler, R. 2005a. Efficient algorithms for processing XPath queries. ACM Trans. Datab. Syst. 30, 2 (June), 444-491.]]
[15] Gottlob, G., Koch, C., Pichler, R., and Segoufin, L. 2005b. The complexity of XPath query evaluation and XML typing. J. ACM 52, 2 (Mar.), 284-335.]] · Zbl 1317.68073
[16] Gottlob, G., Koch, C., and Schulz, K. U. 2004. Conjunctive queries over trees. In Proceedings of the 23rd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS’04) (Paris, France). ACM, New York, 189-200.]]
[17] Gutjahr, W., Welzl, E., and Woeginger, G. 1992. Polynomial graph colourings., Disc. Appl. Math. 35, 29-46.]] · Zbl 0761.05040
[18] Hell, P., and Nesetril, J. 2004. Graphs and Homomorphisms. Oxford University Press.]] · Zbl 1062.05139
[19] Hell, P., Nesetril, J., and Zhu, X. 1996a. Complexity of tree homomorphisms. Disc. Appl. Math. 70, 1, 23-36.]] · Zbl 0868.05018
[20] Hell, P., Nesetril, J., and Zhu, X. 1996b. Duality and polynomial testing of tree homomorphisms. Trans. AMS 348, 4 (Apr.), 1281-1297.]] · Zbl 0877.05055
[21] Hidders, J. 2003. Satisfiability of XPath expressions. In Proceedings of the 9th International Workshop on Database Programming Languages (DBPL) (Potsdam, Germany). 21-36.]]
[22] Kolaitis, P., and Vardi, M. 1998. Conjunctive-query containment and constraint satisfaction. In Proceedings of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS’98). ACM, New York, 205-213.]]
[23] LDC. 1999. The Penn Treebank project. http://www.cis.upenn.edu/ treebank/home.html.]]
[24] Libkin, L. 2004. Elements of Finite Model Theory. Springer-Verlag, New York.]] · Zbl 1060.03002
[25] Maier, D. 1983. The Theory of Relational Databases. Computer Science Press.]] · Zbl 0519.68082
[26] Marcus, M. P., Hindle, D., and Fleck, M. M. 1983. D-theory: Talking about talking about trees. In Proceedings of the 21st Annual Meeting of the Association for Computational Linguistics (ACL). 129-136.]]
[27] Marx, M. 2005. First order paths in ordered trees. In Proceedings of the 11th International Conference on Database Theory (ICDT 2005). 114-128.]] · Zbl 1112.68370
[28] Meuss, H., and Schulz, K. U. 2001. Complete answer aggregates for tree-like databases: A novel approach to combine querying and navigation. ACM Trans. Inf. Syst. 19, 2, 161-215.]]
[29] Meuss, H., Schulz, K. U., and Bry, F. 2001. Towards aggregated answers for semistructured data. In Proceedings of the 8th International Conference on Database Theory (ICDT’01). 346-360.]] · Zbl 1047.68557
[30] Minoux, M. 1988. LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation. Inf. Proc. Lett. 29, 1, 1-12.]] · Zbl 0658.68110
[31] Olteanu, D., Meuss, H., Furche, T., and Bry, F. 2002. XPath: Looking forward. In Proceedings of the EDBT Workshop on XML Data Management (Prague, Czech Republic). Lecture Notes in Computer Science, vol. 2490. Springer-Verlag, New York, 109-127.]] · Zbl 1032.68926
[32] Schaefer, T. 1978. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 216-226.]] · Zbl 1282.68143
[33] Schmidt-Schauß, M., and Schulz, K. U. 1998. On the exponent of periodicity of minimal solutions of context equations. In Proceedings of the 9th International Conference on Rewriting Techniques and Applications. 61-75.]] · Zbl 0901.03034
[34] Schmidt-Schauß, M., and Schulz, K. U. 2002. Solvability of context equations with two context variables is decidable. J. Symb. Comput. 33, 1, 77-122.]] · Zbl 1017.68165
[35] Schmidt-Schauß, M., and Stuber, J. 2004. The complexity of linear and stratified context matching problems. Theoret. Comput. Syst. 37, 6, 717-740.]] · Zbl 1061.68179
[36] Schwentick, T. 2000. On diving in trees. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS). 660-669.]] · Zbl 0996.68051
[37] Vardi, M. Y. 1982. The complexity of relational query languages. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC’82) (San Francisco, CA) USA, 137-146.]]
[38] World Wide Web Consortium. 1999. XML Path Language (XPath) Recommendation. http://www.w3c.org/TR/xpath/.]]
[39] Yannakakis, M. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Data Bases (VLDB’81) (Cannes, France). 82-94.]]
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.