×

Semantic acyclicity on graph databases. (English) Zbl 1407.68123

Summary: It is known that unions of acyclic conjunctive queries (CQs) can be evaluated in linear time, as opposed to arbitrary CQs, for which the evaluation problem is NP-complete. It follows from techniques in the area of constraint-satisfaction problems that semantically acyclic unions of CQs – i.e., unions of CQs that are equivalent to a union of acyclic ones – can be evaluated in polynomial time, though testing membership in the class of semantically acyclic CQs is NP-complete. We study here the fundamental notion of semantic acyclicity in the context of graph databases and unions of conjunctive regular path queries with inverse (UC2RPQs). It is known that unions of acyclic C2RPQs can be evaluated efficiently, but it is by no means obvious whether similarly good evaluation properties hold for the class of UC2RPQs that are semantically acyclic. We prove that checking whether a UC2RPQ is semantically acyclic is Expspace-complete and obtain as a corollary that evaluation of semantically acyclic UC2RPQs is fixed-parameter tractable. In addition, our tools yield a strong theory of approximations for UC2RPQs when no equivalent acyclic UC2RPQ exists.

MSC:

68P15 Database theory

Software:

XPath; GraphLog
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Abiteboul, P. Buneman, and D. Suciu, {\it Data on the Web: From Relations to Semistructured Data and XML}, Morgan Kauffman, Burlington, MA, 1999.
[2] R. Angles and C. Gutiérrez, {\it Survey of graph database models}, ACM Comput. Surv., 40 (2008), 1.
[3] P. Barceló, {\it Querying graph databases}, in Proceedings of the 32nd Symposium on Principles of Database Systems, PODS’13, ACM, New York, 2013, pp. 175-188.
[4] P. Barceló, L. Libkin, A. W. Lin, and P. Wood, {\it Expressive languages for path queries over graph-structured data}, ACM T. Database Syst., 37 (2012), 31.
[5] P. Barceló, J. Perez, and J. Reutter, {\it Relative expressiveness of nested regular expressions}, in Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW’12, 2012, pp. 180-195.
[6] P. Barceló, L. Libkin, and M. Romero, {\it Efficient approximations of conjunctive queries}, SIAM J. Comput. 43 (2014), pp. 1085-1130, doi:10.1137/130911731. · Zbl 1308.68052
[7] P. Barceló, M. Romero, and M. Y. Vardi, {\it Semantic acyclicity on graph databases}, in Proceedings of the 32nd ACM Symposium on Principles of Database Systems, PODS’13, ACM, New York, 2013, pp. 237-248. · Zbl 1407.68123
[8] A. Bulatov, V. Dalmau, M. Grohe, and D. Marx, {\it Enumerating homomorphisms}, J. Comput. System Sci., 78 (2012), pp. 638-650. · Zbl 1253.68165
[9] D. Calvanese, G. de Giacomo, M. Lenzerini, and M. Y. Vardi, {\it Containment of conjunctive regular path queries with inverse}, in Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning, KR’00, 2000, pp. 176-185.
[10] D. Calvanese, G. de Giacomo, M. Lenzerini, and M. Y. Vardi, {\it Rewriting of regular expressions and regular path queries}, J. Comput. System Sci., 64 (2002), pp. 443-465. · Zbl 1015.68083
[11] D. Calvanese, G. de Giacomo, M. Lenzerini, and M. Y. Vardi, {\it View-based query answering and query containment over semistructured data}, in Proceedings of the 8th International Workshop on Database Programming Languages, DBPL’02, Lecture Notes in Comput. Sci. 2397, Springer-Verlag, Berlin, Heidelberg, 2002, pp. 40-61. · Zbl 1098.68560
[12] A. K. Chandra and P. M. Merlin, {\it Optimal implementation of conjunctive queries in relational data bases}, in Conference Record of the 9th Annual ACM Symposium on Theory of Computing, STOC’77, ACM, New York, 1977, pp. 77-90.
[13] C. Chekuri and A. Rajaraman, {\it Conjunctive query containment revisited}, Theoret. Comput. Sci., 239 (2000), pp. 211-229. · Zbl 0944.68046
[14] H. Chen and V. Dalmau, {\it Beyond hypertree width: Decomposition methods without decompositions}, in Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming, CP’05, Lecture Notes in Comput. Sci. 3709, Springer-Verlag, Berlin, Heidelberg, 2005, pp. 167-181. · Zbl 1153.68452
[15] M. P. Consens and A. O. Mendelzon, {\it GraphLog: A visual formalism for real life recursion}, in Proceedings of the Ninth ACM Symposium on Principles of Database Systems, PODS’90, ACM New York, 1990, pp. 404-416.
[16] I. Cruz, A. O. Mendelzon, and P. T. Wood, {\it A graphical query language supporting recursion}, in Proceedings of the ACM SIGMOD Conference, SIGMOD’87, ACM, New York, 1987, pp. 323-330.
[17] V. Dalmau, Ph. G. Kolaitis, and M. Y. Vardi, {\it Constraint satisfaction, bounded treewidth, and finite-variable logics}, in Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, CP’02, Lecture Notes in Comput. Sci. 2470, Springer-Verlag, Berlin, Heidelberg, 2002, pp. 310-326.
[18] R. Fagin, {\it Degrees of acyclicity for hypergraphs and relational database schemes}, J. ACM, 30 (1983), pp. 514-550. · Zbl 0624.68088
[19] W. Fan, J. Li, S. Ma, N. Tang, and Y. Wu, {\it Graph pattern matching: From intractable to polynomial time}, Proceedings of the VLDB Endowment, 3 (2010), pp. 264-275, doi:10.14778/1920841.1920878.
[20] W. Fan, J. Li, S. Ma, N. Tang, and Y. Wu, {\it Adding regular expressions to graph reachability and pattern queries}, Front. Comput. Sci., 6 (2012), pp. 313-338. · Zbl 1251.68170
[21] T. Feder and M. Y. Vardi, {\it The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory}, SIAM J. Comput., 28 (1998), pp. 57-104, doi:10.1137/S0097539794266766. · Zbl 0914.68075
[22] G. Fletcher, M. Gyssens, D. Leinders, D. Surinx, J. van den Bussche, D. Van Gucht, S. Vansummeren, and Y. Wu, {\it Relative expressive power of navigational querying on graphs}, Inform. Sci., 298 (2015), pp. 390-406. · Zbl 1360.68394
[23] D. Florescu, A. Levy, and D. Suciu, {\it Query containment for conjunctive queries with regular expressions}, in Proceedings of the 17th ACM Symposium on Principles of Database Systems, PODS’98, ACM, New York, 1998, pp. 139-148.
[24] J. Flum, M. Frick, and M. Grohe, {\it Query evaluation via tree-decompositions}, J. ACM, 49 (2002), pp. 716-752. · Zbl 1326.68123
[25] G. Gottlob, N. Leone, and F. Scarcello, {\it The complexity of acyclic conjunctive queries}, J. ACM, 48 (2001), pp. 431-498. · Zbl 1323.68250
[26] G. Gottlob, N. Leone, and F. Scarcello, {\it Hypertree decompositions and tractable queries}, J. Comput. System Sci., 64 (2002), pp. 579-627. · Zbl 1052.68025
[27] G. Greco and F. Scarcello, {\it Structural tractability of enumerating CSP solutions}, Constraints, 18 (2013), pp. 38-74. · Zbl 1310.05151
[28] D. Harel, D. Kozen, and J. Tiuryn, {\it Dynamic Logic}, MIT Press, Cambridge, MA, 2000. · Zbl 0976.68108
[29] P. Hell and J. Nešeťril, {\it Graphs and Homomorphisms}, Oxford University Press, Oxford, UK, 2004. · Zbl 1062.05139
[30] J. E. Hopcroft and J. D. Ullman, {\it Introduction to Automata Theory, Languages, and Computation}, Addison-Wesley, Reading, MA, 1979. · Zbl 0426.68001
[31] Ph. G. Kolaitis and M. Y. Vardi, {\it On the expressive power of Datalog: Tools and a case study}, J. Comput. System Sci., 51 (1995), pp. 110-134. · Zbl 1360.68397
[32] Ph. G. Kolaitis and M. Y. Vardi, {\it A logical approach to constraint satisfaction}, in The Book Complexity of Constraints: An Overview of Current Research Themes, N. Creignou, P. G. Kolaitis, and H. Vollmer, eds., Lecture Notes in Comput. Sci. 5250, Springer-Verlag, Berlin, Heidelberg, 2008, pp. 125-155. · Zbl 1171.03322
[33] Ph. G. Kolaitis and M. Y. Vardi, {\it Conjunctive query-containment and constraint satisfaction}, J. Comput. System Sci., 61 (2002), pp. 302-332. · Zbl 0963.68059
[34] R. E. Ladner, R. J. Lipton, and L. J. Stockmeyer, {\it Alternating pushdown and stack automata}, SIAM J. Comput., 13 (1984), pp. 135-155, doi:10.1137/0213010. · Zbl 0538.68039
[35] L. Libkin, W. Martens, and D. Vrgoc, {\it Querying graph databases with XPath}, in Proceedings of the 16th International Conference on Database Theory, ICDT’13, ACM, New York, 2013, pp. 129-140.
[36] Ch. H. Papadimitriou and M. Yannakakis, {\it The complexity of facets (and some facets of complexity)}, J. Comput. System Sci., 28 (1986), pp. 244-259. · Zbl 0571.68028
[37] Ch. H. Papadimitriou and M. Yannakakis, {\it On the complexity of database queries}, in Proceedings of the 16th ACM Symposium on Principles of Database Systems, PODS’97, ACM, New York, 1997, pp. 12-19.
[38] J. Reutter, M. Romero, and M. Y. Vardi, {\it Regular queries on graph databases}, in Proceedings of the 18th International Conference on Database Theory, ICDT’15, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015, pp. 177-194. · Zbl 1365.68219
[39] Y. Sagiv and M. Yannakakis, {\it Equivalences among relational expressions with the union and difference operator}, J. ACM, 27 (1980), pp. 633-655. · Zbl 0456.68123
[40] R. Tarjan and M. Yannakakis, {\it Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs}, SIAM J. Comput., 13 (1984), pp. 566-579, doi:10.1137/0213035. · Zbl 0545.68062
[41] M. Y. Vardi, {\it The complexity of relational query languages (extended abstract)}, in STOC 1982, ACM, New York, 1982, pp. 137-146.
[42] M. Y. Vardi, {\it A note on the reduction of two-way automata to one-way automata}, Inform. Process. Lett., 30 (1989), pp. 261-264. · Zbl 0665.68045
[43] P. T. Wood, {\it Query languages for graph databases}, SIGMOD Record, 41 (2012), pp. 50-60.
[44] M. Yannakakis, {\it Algorithms for acyclic database schemes}, in Proceedings of the 7th International Conference on Very Large Data Bases, 1981, pp. 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.