{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T04:11:33Z","timestamp":1759032693796,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":162,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540746133"},{"type":"electronic","value":"9783540746157"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74615-7_1","type":"book-chapter","created":{"date-parts":[[2007,8,21]],"date-time":"2007-08-21T02:59:08Z","timestamp":1187665148000},"page":"1-153","source":"Crossref","is-referenced-by-count":8,"title":["Foundations of Rule-Based Query Answering"],"prefix":"10.1007","author":[{"given":"Fran\u00e7ois","family":"Bry","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Norbert","family":"Eisinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Eiter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Furche","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clemens","family":"Ley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benedikt","family":"Linse","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fang","family":"Wei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"1_CR1","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/BF01354881","volume":"4","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Beeri, C.: The Power of Languages for the Manipulation of Complex Values. VLDB Journal\u00a04(4), 727\u2013794 (1995)","journal-title":"VLDB Journal"},{"key":"1_CR2","volume-title":"Foundations of Databases","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley Publishing Co., Reading (1995)"},{"issue":"5","key":"1_CR3","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/290179.290182","volume":"45","author":"S. Abiteboul","year":"1998","unstructured":"Abiteboul, S., Kanellakis, P.C.: Object Identity as a Query Language Primitive. Journal of the Association for Computing Machinery\u00a045(5), 798\u2013842 (1998)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"1","key":"1_CR4","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/s007990050001","volume":"1","author":"S. Abiteboul","year":"1997","unstructured":"Abiteboul, S., Quass, D., McHugh, J., Widom, J., Wienerm, J.L.: The Lorel Query Language for Semistructured Data. International Journal on Digital Libraries\u00a01(1), 68\u201388 (1997)","journal-title":"International Journal on Digital Libraries"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/0022-0000(91)90032-Z","volume":"43","author":"S. Abiteboul","year":"1991","unstructured":"Abiteboul, S., Vianu, V.: Datalog Extensions for Database Queries and Updates. Journal of Computer and System Sciences\u00a043, 62\u2013124 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1145\/263661.263676","volume-title":"PODS","author":"S. Abiteboul","year":"1997","unstructured":"Abiteboul, S., Vianu, V.: Regular Path Queries with Constraints. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 122\u2013133. ACM Press, New York (1997)"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1145\/375663.375730","volume-title":"SIGMOD","author":"S. Amer-Yahia","year":"2001","unstructured":"Amer-Yahia, S., Cho, S., Lakshmanan, L.V.S., Srivastava, D.: Minimization of Tree Pattern Queries. In: SIGMOD. Proc. ACM SIGMOD Symposium on the Management of Data, pp. 497\u2013508. ACM Press, New York (2001)"},{"key":"1_CR8","first-page":"3","volume":"4","author":"Andr\u00e9ka","year":"1978","unstructured":"Andr\u00e9ka, N\u00e9meti: The Generalized Completeness of Horn Predicate Logic as a Programming Language. Acta Cybernetica\u00a04, 3\u201310 (1978)","journal-title":"Acta Cybernetica"},{"key":"1_CR9","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/B978-0-934613-40-8.50006-3","volume-title":"Foundations of Deductive Databases and Logic Programming","author":"K. Apt","year":"1988","unstructured":"Apt, K., Blair, H., Walker, A.: Towards a Theory of Declarative Knowledge. In: Minker, J. (ed.) Foundations of Deductive Databases and Logic Programming, pp. 89\u2013148. Morgan Kaufmann, San Francisco (1988)"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0743-1066(94)90051-5","volume":"18","author":"K. Apt","year":"1994","unstructured":"Apt, K., Doets, K.: A New Definition of SLDNF-Resolution. Journal of Logic Programming\u00a018, 177\u2013190 (1994)","journal-title":"Journal of Logic Programming"},{"issue":"2","key":"1_CR11","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1145\/320455.320457","volume":"1","author":"M.M. Astrahan","year":"1976","unstructured":"Astrahan, M.M., Blasgen, M.W., Chamberlin, D.D., Eswaran, K.P., Gray, J.N., Griffiths, P.P., King, W.F., Lorie, R.A., McJones, P.R., Mehl, J.W., Putzolu, G.R., Traiger, I.L., Wade, B.W., Watson, V.: System R: Relational Approach to Database Management. ACM Transactions on Database Systems\u00a01(2), 97\u2013137 (1976)","journal-title":"ACM Transactions on Database Systems"},{"key":"1_CR12","first-page":"1","volume-title":"Building an Object-oriented Database System: The Story of O2","author":"M. Atkinson","year":"1992","unstructured":"Atkinson, M., DeWitt, D., Maier, D., Bancilhon, F., Dittrich, K., Zdonik, S.: The Object-oriented Database System Manifesto. In: Bancilhon, F., Delobel, C., Kanellakis, P. (eds.) Building an Object-oriented Database System: The Story of O2, pp. 1\u201320. Morgan Kaufmann Publishers Inc., San Francisco (1992)"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/B978-044450813-3\/50010-2","volume-title":"Handbook of Automated Reasoning","author":"F. Baader","year":"2001","unstructured":"Baader, F., Snyder, W.: Unification Theory. In: Robinson, J.A., Voronkov, A. (eds.) Handbook of Automated Reasoning, vol.\u00a01, pp. 447\u2013533. Elsevier, Amsterdam (2001)"},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","volume-title":"Reasoning Web","author":"J. Bailey","year":"2005","unstructured":"Bailey, J., Bry, F., Furche, T., Schaffert, S.: Web and Semantic Web Query Languages: A Survey. In: Eisinger, N., Ma\u0142uszy\u0144ski, J. (eds.) Reasoning Web. LNCS, vol.\u00a03564, Springer, Heidelberg (2005)"},{"key":"1_CR15","unstructured":"Balbin, I., Meenakshi, K., Ramamohanarao, K.: A Query Independent Method for Magic Set Computation on Stratified Databases. In: Proc. International Conference on Fifth Generation Computer Systems, pp. 711\u2013718 (1988)"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0743-1066(91)90030-S","volume":"11","author":"I. Balbin","year":"1991","unstructured":"Balbin, I., Port, G., Ramamohanarao, K., Meenakshi, K.: Efficient Bottom-Up Computation of Queries of Stratified Databases. Journal of Logic Programming\u00a011, 295\u2013344 (1991)","journal-title":"Journal of Logic Programming"},{"key":"1_CR17","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/978-1-4615-3422-8_30","volume-title":"Computer Science","author":"J. Balc\u00e1zar","year":"1992","unstructured":"Balc\u00e1zar, J., Lozano, A., Tor\u00e1n, J.: The Complexity of Algorithmic Problems on Succinct Instances. In: Baeta-Yates, R., Manber, U. (eds.) Computer Science, pp. 351\u2013377. Plenum Press, New York, USA (1992)"},{"key":"1_CR18","first-page":"269","volume-title":"PODS","author":"C. Beeri","year":"1987","unstructured":"Beeri, C., Ramakrishnan, R.: On the Power of Magic. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 269\u2013283. ACM Press, New York (1987)"},{"key":"1_CR19","first-page":"102","volume-title":"PODS","author":"A. Behrend","year":"2003","unstructured":"Behrend, A.: Soft Stratification for Magic set based Query Evaluation in Deductive Databases. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 102\u2013110. ACM Press, New York (2003)"},{"key":"1_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/3-540-15976-2_22","volume-title":"Rewriting Techniques and Applications","author":"D. Benanav","year":"1985","unstructured":"Benanav, D., Kapur, D., Narendran, P.: Complexity of Matching Problems. In: Jouannaud, J.-P. (ed.) Rewriting Techniques and Applications. LNCS, vol.\u00a0202, pp. 417\u2013429. Springer, Heidelberg (1985)"},{"issue":"1","key":"1_CR21","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/322234.322238","volume":"28","author":"P.A. Bernstein","year":"1981","unstructured":"Bernstein, P.A., Chiu, D.-M.W.: Using Semi-Joins to Solve Relational Queries. Journal of the Association for Computing Machinery\u00a028(1), 25\u201340 (1981)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(51)90004-7","volume":"78","author":"N. Bidoit","year":"1991","unstructured":"Bidoit, N., Froidevaux, C.: Negation by Default and Unstratifiable Programs. Theoretical Computer Science\u00a078, 85\u2013112 (1991)","journal-title":"Theoretical Computer Science"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"B\u00f6nstr\u00f6m, V., Hinze, A., Schweppe, H.: Storing RDF as a Graph. In: Proc. Latin American Web Congress, pp. 27\u201336 (2003)","DOI":"10.1109\/LAWEB.2003.1250279"},{"key":"1_CR24","doi-asserted-by":"crossref","first-page":"199","DOI":"10.7551\/mitpress\/4298.003.0027","volume-title":"International Conference on Logic Programming","author":"S. Brass","year":"1995","unstructured":"Brass, S., Dix, J.: Disjunctive Semantics Based upon Partial and Bottom-Up Evaluation. In: Sterling, L. (ed.) International Conference on Logic Programming, pp. 199\u2013213. MIT Press, Cambridge (1995)"},{"key":"1_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/3-540-56039-4_38","volume-title":"Database Theory - ICDT \u201992","author":"V. Breazu-Tannen","year":"1992","unstructured":"Breazu-Tannen, V., Buneman, P., Wong, L.: Naturally Embedded Query Languages. In: Hull, R., Biskup, J. (eds.) ICDT 1992. LNCS, vol.\u00a0646, pp. 140\u2013154. Springer, Heidelberg (1992)"},{"key":"1_CR26","first-page":"193","volume-title":"SIGMOD","author":"F. Bry","year":"1989","unstructured":"Bry, F.: Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited. In: SIGMOD. Proc. ACM SIGMOD Symposium on the Management of Data, pp. 193\u2013204. ACM Press, New York (1989)"},{"issue":"4","key":"1_CR27","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0169-023X(90)90017-8","volume":"5","author":"F. Bry","year":"1990","unstructured":"Bry, F.: Query Evaluation in Recursive Databases: Bottom-up and Top-down Reconciled. Data and Knowledge Engineering\u00a05(4), 289\u2013312 (1990)","journal-title":"Data and Knowledge Engineering"},{"key":"1_CR28","series-title":"Lecture Notes in Computer Science","volume-title":"Logic Programming","author":"F. Bry","year":"2004","unstructured":"Bry, F., P\u0103tr\u00e2njan, P.-L., Schaffert, S.: Xcerpt and XChange: Logic Programming Languages for Querying and Evolution on the Web. In: Demoen, B., Lifschitz, V. (eds.) ICLP 2004. LNCS, vol.\u00a03132, Springer, Heidelberg (2004)"},{"key":"1_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45619-8_18","volume-title":"Logic Programming","author":"F. Bry","year":"2002","unstructured":"Bry, F., Schaffert, S.: Towards a Declarative Query and Transformation Language for XML and Semistructured Data: Simulation Unification. In: Stuckey, P.J. (ed.) ICLP 2002. LNCS, vol.\u00a02401, Springer, Heidelberg (2002)"},{"key":"1_CR30","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/11415763_17","volume-title":"Applications of Declarative Programming and Knowledge Management","author":"F. Bry","year":"2005","unstructured":"Bry, F., Schaffert, S., Schr\u00f6der, A.: A Contribution to the Semantics of Xcerpt, a Web Query and Transformation Language. In: Seipel, D., Hanus, M., Geske, U., Bartenstein, O. (eds.) Applications of Declarative Programming and Knowledge Management. LNCS (LNAI), vol.\u00a03392, pp. 258\u2013268. Springer, Heidelberg (2005)"},{"key":"1_CR31","first-page":"208","volume-title":"DBLP","author":"P. Buneman","year":"2000","unstructured":"Buneman, P., Fan, W., Weinstein, S.: Query Optimization for Semistructured Data Using Path Constraints in a Deterministic Data Model. In: DBLP. Proc. International Workshop on Database Programming Languages, pp. 208\u2013223. Springer, Heidelberg (2000)"},{"issue":"1","key":"1_CR32","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(95)00024-Q","volume":"149","author":"P. Buneman","year":"1995","unstructured":"Buneman, P., Naqvi, S., Tannen, V., Wong, L.: Principles of Programming with Complex Objects and Collection Types. Theoretical Computer Science\u00a0149(1), 3\u201348 (1995)","journal-title":"Theoretical Computer Science"},{"key":"1_CR33","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0743-1066(89)90020-4","volume":"7","author":"L. Cavedon","year":"1989","unstructured":"Cavedon, L., Lloyd, J.: A Completeness Theorem for SLDNF-Resolution. Journal of Logic Programming\u00a07, 177\u2013191 (1989)","journal-title":"Journal of Logic Programming"},{"issue":"4","key":"1_CR34","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1109\/TSE.1985.232223","volume":"11","author":"S. Ceri","year":"1985","unstructured":"Ceri, S., Gottlob, G.: Translating SQL into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries. IEEE Transactions on Software Engineering\u00a011(4), 324\u2013345 (1985)","journal-title":"IEEE Transactions on Software Engineering"},{"key":"1_CR35","series-title":"Lecture Notes in Computer Science","volume-title":"Databases, Information Systems, and Peer-to-Peer Computing","author":"C.-Y. Chan","year":"2004","unstructured":"Chan, C.-Y., Fan, W., Zeng, Y.: Taming XPath Queries by Minimizing Wildcard Steps. In: Aberer, K., Koubarakis, M., Kalogeraki, V. (eds.) Databases, Information Systems, and Peer-to-Peer Computing. LNCS, vol.\u00a02944, Springer, Heidelberg (2004)"},{"key":"1_CR36","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. Chandra","year":"1982","unstructured":"Chandra, A., Harel, D.: Structure and Complexity of Relational Queries. Journal of Computer and System Sciences\u00a025, 99\u2013128 (1982)","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR37","first-page":"77","volume-title":"STOC","author":"A.K. Chandra","year":"1977","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal Implementation of Conjunctive Queries in Relational Data Bases. In: STOC. ACM Symposium on Theory of Computing, pp. 77\u201390. ACM Press, New York (1977)"},{"key":"1_CR38","first-page":"59","volume-title":"PODS","author":"S. Chaudhuri","year":"1993","unstructured":"Chaudhuri, S.: Optimization of Real Conjunctive Queries. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 59\u201370. ACM Press, New York (1993)"},{"issue":"3","key":"1_CR39","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00778-005-0172-6","volume":"15","author":"D. Che","year":"2006","unstructured":"Che, D., Aberer, K., \u00d6zsu, T.: Query Optimization in XML Structured-document Databases. The VLDB Journal\u00a015(3), 263\u2013289 (2006)","journal-title":"The VLDB Journal"},{"issue":"1","key":"1_CR40","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1145\/227595.227597","volume":"43","author":"W. Chen","year":"1996","unstructured":"Chen, W., Warren, D.S.: Tabled Evaluation with Delaying for General Logic Programs. Journal of the Association for Computing Machinery\u00a043(1), 20\u201374 (1996)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"1_CR41","first-page":"568","volume-title":"ICDE","author":"Y. Chen","year":"1993","unstructured":"Chen, Y.: A Bottom-up Query Evaluation Method for Stratified Databases. In: ICDE. Proc. International Conference on Data Engineering, pp. 568\u2013575. IEEE Computer Society Press, Los Alamitos (1993)"},{"key":"1_CR42","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/978-1-4684-3384-5_11","volume-title":"Logic and Data Base","author":"K. Clark","year":"1978","unstructured":"Clark, K.: Negation as Failure. In: Gallaire, H., Minker, J. (eds.) Logic and Data Base, pp. 293\u2013322. Plenum Press, New York, USA (1978)"},{"issue":"6","key":"1_CR43","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"E.F. Codd","year":"1970","unstructured":"Codd, E.F.: A Relational Model of Data for Large Shared Data Banks. Communications of the ACM\u00a013(6), 377\u2013387 (1970)","journal-title":"Communications of the ACM"},{"key":"1_CR44","unstructured":"Codd, E.F.: Relational Completeness of Data Base Sublanguages. Database Systems, pp. 65\u201398 (1972)"},{"issue":"4","key":"1_CR45","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1145\/320107.320109","volume":"4","author":"E.F. Codd","year":"1979","unstructured":"Codd, E.F.: Extending the Database Relational Model to Capture more Meaning. ACM Transactions on Database Systems\u00a04(4), 397\u2013434 (1979)","journal-title":"ACM Transactions on Database Systems"},{"key":"1_CR46","doi-asserted-by":"crossref","unstructured":"Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and Expressive Power of Logic Programming. In: Proc. IEEE Conference on Computational Complexity, pp. 82\u2013101 (1997)","DOI":"10.1109\/CCC.1997.612304"},{"key":"1_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/3-540-63045-7_7","volume-title":"Logical Foundations of Computer Science","author":"E. Dantsin","year":"1997","unstructured":"Dantsin, E., Voronkov, A.: Complexity of Query Answering in Logic Databases with Complex Values. In: Adian, S., Nerode, A. (eds.) LFCS 1997. LNCS, vol.\u00a01234, pp. 56\u201366. Springer, Heidelberg (1997)"},{"key":"1_CR48","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/335168.335218","volume-title":"PODS","author":"E. Dantsin","year":"2000","unstructured":"Dantsin, E., Voronkov, A.: Expressive Power and Data Complexity of Nonrecursive Query Languages for Lists and Trees. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 157\u2013165. ACM Press, New York (2000)"},{"key":"1_CR49","first-page":"117","volume-title":"PODS","author":"U. Dayal","year":"1982","unstructured":"Dayal, U., Goodman, N., Katz, R.H.: An Extended Relational Algebra with Control over Duplicate Elimination. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 117\u2013123. ACM Press, New York (1982)"},{"key":"1_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11552222_7","volume-title":"Principles and Practice of Semantic Web Reasoning","author":"J. Bruijn de","year":"2005","unstructured":"de Bruijn, J., Franconi, E., Tessaris, S.: Logical Reconstruction of RDF and Ontology Languages. In: Fages, F., Soliman, S. (eds.) PPSWR 2005. LNCS, vol.\u00a03703, Springer, Heidelberg (2005)"},{"key":"1_CR51","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0743-1066(94)90050-7","volume":"18","author":"S. Debray","year":"1994","unstructured":"Debray, S., Ramakrishnan, R.: Abstract Interpretation of Logic Programs Using Magic Transformations. Journal of Logic Programming\u00a018, 149\u2013176 (1994)","journal-title":"Journal of Logic Programming"},{"key":"1_CR52","first-page":"243","volume-title":"Handbook of Theoretical Computer Science B: Formal Methods and Semantics, ch. 6","author":"N. Dershowitz","year":"1990","unstructured":"Dershowitz, N., Jouannaud, J.-P.: Rewrite Systems. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science B: Formal Methods and Semantics, ch. 6, pp. 243\u2013309. Elsevier Science, Amsterdam (1990)"},{"key":"1_CR53","unstructured":"Deutsch, A., Tannen, V.: Containment and Integrity Constraints for XPath Fragments. In: KRDB. Proc. Int\u2019l. Workshop on Knowledge Representation meets Databases (2001)"},{"key":"1_CR54","unstructured":"Dietrich, S.W.: Extension Tables: Memo Relations in Logic Programming. In: SLP. Proc. Symposium on Logic Programming, pp. 264\u2013272 (1987)"},{"key":"1_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/3-540-62222-5_42","volume-title":"Database Theory - ICDT \u201997","author":"G. Dong","year":"1996","unstructured":"Dong, G., Libkin, L., Wong, L.: Local Properties of Query Languages. In: Afrati, F.N., Kolaitis, P.G. (eds.) ICDT 1997. LNCS, vol.\u00a01186, pp. 140\u2013154. Springer, Heidelberg (1996)"},{"key":"1_CR56","unstructured":"Doorenbos, R.B.: Production Matching for Large Learning Systems. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA (1995)"},{"issue":"3","key":"1_CR57","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"1","author":"W.F. Dowling","year":"1984","unstructured":"Dowling, W.F., Gallier, J.H.: Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae. Journal of Logic Programming\u00a01(3), 267\u2013284 (1984)","journal-title":"Journal of Logic Programming"},{"key":"1_CR58","doi-asserted-by":"crossref","unstructured":"Drabent, W.: Completeness of SLDNF-Resolution for Non-Floundering Queries. In: Proc. International Symposium on Logic Programming, p. 643 (1993)","DOI":"10.7551\/mitpress\/4307.003.0009"},{"key":"1_CR59","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0743-1066(84)90022-0","volume":"1","author":"C. Dwork","year":"1984","unstructured":"Dwork, C., Kanellakis, P., Mitchell, J.: On the Sequential Nature of Unification. Journal of Logic Programming\u00a01, 35\u201350 (1984)","journal-title":"Journal of Logic Programming"},{"issue":"4","key":"1_CR60","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1137\/0217046","volume":"17","author":"C. Dwork","year":"1988","unstructured":"Dwork, C., Kanellakis, P., Stockmeyer, L.: Parallel Algorithms for Term Matching. SIAM Journal of Computing\u00a017(4), 711\u2013731 (1988)","journal-title":"SIAM Journal of Computing"},{"key":"1_CR61","volume-title":"Finite Model Theory. Perspectives in Mathematical Logic","author":"H.-D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory. Perspectives in Mathematical Logic. Springer, Heidelberg (1995)"},{"issue":"2","key":"1_CR62","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0304-3975(93)90073-3","volume":"114","author":"T. Eiter","year":"1993","unstructured":"Eiter, T., Gottlob, G.: Propositional Circumscription and Extended Closed World Reasoning are $\\Pi^{P}_{2}$ -complete. Theoretical Computer Science\u00a0114(2), 231\u2013245 (1993)","journal-title":"Theoretical Computer Science"},{"issue":"3\/4","key":"1_CR63","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/BF01536399","volume":"15","author":"T. Eiter","year":"1995","unstructured":"Eiter, T., Gottlob, G.: On the Computational Cost of Disjunctive Logic Programming: Propositional Case. Annals of Mathematics and Artificial Intelligence\u00a015(3\/4), 289\u2013323 (1995)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"1_CR64","first-page":"267","volume-title":"PODS","author":"T. Eiter","year":"1994","unstructured":"Eiter, T., Gottlob, G., Mannila, H.: Adding Disjunction to Datalog. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 267\u2013278. ACM Press, New York (1994)"},{"issue":"3","key":"1_CR65","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1145\/261124.261126","volume":"22","author":"T. Eiter","year":"1997","unstructured":"Eiter, T., Gottlob, G., Mannila, H.: Disjunctive Datalog. ACM Transactions on Database Systems\u00a022(3), 364\u2013418 (1997)","journal-title":"ACM Transactions on Database Systems"},{"key":"1_CR66","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(93)90218-I","volume":"116","author":"R. Fagin","year":"1993","unstructured":"Fagin, R.: Finite-Model Theory \u2014 a Personal Perspective. Theoretical Computer Science\u00a0116, 3\u201331 (1993)","journal-title":"Theoretical Computer Science"},{"issue":"7","key":"1_CR67","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1002\/spe.4380220706","volume":"22","author":"C. Fan","year":"1992","unstructured":"Fan, C., Dietrich, S.W.: Extension Table Built-ins for Prolog. Software \u2014 Practice and Experience\u00a022(7), 573\u2013597 (1992)","journal-title":"Software \u2014 Practice and Experience"},{"key":"1_CR68","first-page":"14","volume-title":"ICDE","author":"M.F. Fernandez","year":"1998","unstructured":"Fernandez, M.F., Suciu, D.: Optimizing Regular Path Expressions Using Graph Schemas. In: ICDE. Proc. International Conference on Data Engineering, pp. 14\u201323. IEEE Computer Society Press, Los Alamitos (1998)"},{"key":"1_CR69","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0304-3975(00)00330-3","volume":"278","author":"M. Fitting","year":"2002","unstructured":"Fitting, M.: Fixpoint Semantics For Logic Programming \u2013 A Survey. Theoretical Computer Science\u00a0278, 25\u201351 (2002)","journal-title":"Theoretical Computer Science"},{"key":"1_CR70","series-title":"Lecture Notes in Computer Science","first-page":"153","volume-title":"Databases, Information Systems, and Peer-to-Peer Computing","author":"S. Flesca","year":"2004","unstructured":"Flesca, S., Furfaro, F., Masciari, E.: On the Minimization of XPath Queries. In: Aberer, K., Koubarakis, M., Kalogeraki, V. (eds.) Databases, Information Systems, and Peer-to-Peer Computing. LNCS, vol.\u00a02944, pp. 153\u2013164. Springer, Heidelberg (2004)"},{"key":"1_CR71","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1145\/275487.275503","volume-title":"PODS","author":"D. Florescu","year":"1998","unstructured":"Florescu, D., Levy, A., Suciu, D.: Query Containment for Conjunctive Queries with Regular Expressions. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 139\u2013148. ACM Press, New York (1998)"},{"key":"1_CR72","unstructured":"Forgy, C.L.: Rete: a Fast Algorithm for the Many Pattern\/Many Object Pattern Match Problem. Expert systems: a software methodology for modern applications, pp. 324\u2013341 (1990)"},{"key":"1_CR73","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11837787_1","volume-title":"Reasoning Web","author":"T. Furche","year":"2006","unstructured":"Furche, T., Linse, B., Bry, F., Plexousakis, D., Gottlob, G.: RDF Querying: Language Constructs and Evaluation Methods Compared. In: Barahona, P., Bry, F., Franconi, E., Henze, N., Sattler, U. (eds.) Reasoning Web. LNCS, vol.\u00a04126, Springer, Heidelberg (2006)"},{"key":"1_CR74","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1145\/154630.154640","volume-title":"PEPM","author":"J.P. Gallagher","year":"1993","unstructured":"Gallagher, J.P.: Tutorial on Specialisation of Logic Programs. In: PEPM. Proc. ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation, pp. 88\u201398. ACM Press, New York (1993)"},{"key":"1_CR75","volume-title":"Database Systems: The Complete Book","author":"H. Garcia-Molina","year":"2002","unstructured":"Garcia-Molina, H., Ullman, J.D., Widom, J.: Database Systems: The Complete Book. Prentice-Hall, Englewood Cliffs (2002)"},{"key":"1_CR76","volume-title":"Computers and Intractability","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability. Freeman, New York (1979)"},{"key":"1_CR77","first-page":"1070","volume-title":"Proc. International Conference and Symposium on Logic Programming","author":"M. Gelfond","year":"1988","unstructured":"Gelfond, M., Lifschitz, V.: The Stable Model Semantics for Logic Programming. In: Proc. International Conference and Symposium on Logic Programming, pp. 1070\u20131080. MIT Press, Cambridge (1988)"},{"key":"1_CR78","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF03037169","volume":"9","author":"M. Gelfond","year":"1991","unstructured":"Gelfond, M., Lifschitz, V.: Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing\u00a09, 365\u2013385 (1991)","journal-title":"New Generation Computing"},{"key":"1_CR79","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/S0890-5401(03)00012-9","volume":"183","author":"G. Gottlob","year":"2003","unstructured":"Gottlob, G., Papadimitriou, C.: On the Complexity of Single-rule Datalog Queries. Information and Computation\u00a0183, 104\u2013122 (2003)","journal-title":"Information and Computation"},{"key":"1_CR80","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","volume":"101","author":"E. Gr\u00e4del","year":"1992","unstructured":"Gr\u00e4del, E.: Capturing Complexity Classes with Fragments of Second Order Logic. Theoretical Computer Science\u00a0101, 35\u201357 (1992)","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"1_CR81","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0304-3975(98)00308-9","volume":"224","author":"E. Gr\u00e4del","year":"1999","unstructured":"Gr\u00e4del, E., Otto, M.: On Logics with Two Variables. Theoretical Computer Science\u00a0224(1-2), 73\u2013113 (1999)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"1_CR82","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1145\/152610.152611","volume":"25","author":"G. Graefe","year":"1993","unstructured":"Graefe, G.: Query Evaluation Techniques for Large Databases. ACM Computing Surveys\u00a025(2), 73\u2013169 (1993)","journal-title":"ACM Computing Surveys"},{"key":"1_CR83","first-page":"49","volume-title":"PODS","author":"S. Grumbach","year":"1993","unstructured":"Grumbach, S., Milo, T.: Towards Tractable Algebras for Bags. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 49\u201358. ACM Press, New York (1993)"},{"key":"1_CR84","first-page":"315","volume-title":"PODS","author":"S. Grumbach","year":"1991","unstructured":"Grumbach, S., Vianu, V.: Tractable Query Languages for Complex Object Databases. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 315\u2013327. ACM Press, New York (1991)"},{"key":"1_CR85","unstructured":"Gurevich, Y.: Logic and the Challenge of Computer Science. In: B\u00f6rger, E. (ed.) Current Trends in Theoretical Computer Science, ch. 1, pp. 1\u201357. Computer Science Press (1988)"},{"key":"1_CR86","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0168-0072(86)90055-2","volume":"32","author":"Y. Gurevich","year":"1986","unstructured":"Gurevich, Y., Shelah, S.: Fixpoint Extensions of First-Order Logic. Annals of Pure and Applied Logic\u00a032, 265\u2013280 (1986)","journal-title":"Annals of Pure and Applied Logic"},{"key":"1_CR87","unstructured":"Hayes, P.: RDF Model Theory. Recommendation, W3C (2004)"},{"key":"1_CR88","unstructured":"Hinrichs, T., Genesereth, M.: Herbrand Logic. Technical Report LG-2006-02, Stanford Logic Group, Computer Science Department, Stanford University (November 2006)"},{"key":"1_CR89","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"Immerman, N.: Relational Queries Computable in Polynomial Time. Information and Control\u00a068, 86\u2013104 (1986)","journal-title":"Information and Control"},{"key":"1_CR90","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Immerman, N.: Languages that Capture Complexity Classes. SIAM Journal of Computing\u00a016, 760\u2013778 (1987)","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"1_CR91","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/211414.211419","volume":"20","author":"Y.E. Ioannidis","year":"1995","unstructured":"Ioannidis, Y.E., Ramakrishnan, R.: Containment of Conjunctive Queries: Beyond Relations as Sets. ACM Transactions on Database Systems\u00a020(3), 288\u2013324 (1995)","journal-title":"ACM Transactions on Database Systems"},{"key":"1_CR92","first-page":"124","volume-title":"PODS","author":"G. Jaeschke","year":"1982","unstructured":"Jaeschke, G., Schek, H.J.: Remarks on the Algebra of Non First Normal Form Relations. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 124\u2013138. ACM Press, New York (1982)"},{"key":"1_CR93","unstructured":"Jaffar, J., Lassez, J.-L., Lloyd, J.: Completeness of the Negation as Failure Rule. In: IJCAI. Proc. International Joint Conference on Artificial Intelligence, pp. 500\u2013506 (1983)"},{"key":"1_CR94","volume-title":"Handbook of Theoretical Computer Science","author":"D.S. Johnson","year":"1990","unstructured":"Johnson, D.S.: A Catalog of Complexity Classes. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol.\u00a0A, Elsevier, Amsterdam (1990)"},{"key":"1_CR95","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. Jones","year":"1977","unstructured":"Jones, N., Laaser, W.: Complete Problems in Deterministic Polynomial Time. Theoretical Computer Science\u00a03, 105\u2013117 (1977)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"1_CR96","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF00245463","volume":"9","author":"D. Kapur","year":"1992","unstructured":"Kapur, D., Narendran, P.: Complexity of Unification Problems with Associative-commutative Operators. Journal of Automated Reasoning\u00a09(2), 261\u2013288 (1992)","journal-title":"Journal of Automated Reasoning"},{"key":"1_CR97","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0304-3975(89)90089-3","volume":"69","author":"J.-M. Kerisit","year":"1989","unstructured":"Kerisit, J.-M.: A Relational Approach to Logic Programming: the Extended Alexander Method. Theoretical Computer Science\u00a069, 55\u201368 (1989)","journal-title":"Theoretical Computer Science"},{"key":"1_CR98","unstructured":"Kerisit, J.-M., Pugin, J.-M.: Efficient Query Answering on Stratified Databases. In: Proc. International Conference on Fifth Generation Computer Systems, pp. 719\u2013726 (1988)"},{"key":"1_CR99","first-page":"406","volume-title":"Proc. International Conference on Object-oriented Programming Systems, Languages and Applications","author":"S.N. Khoshafian","year":"1986","unstructured":"Khoshafian, S.N., Copeland, G.P.: Object Identity. In: Proc. International Conference on Object-oriented Programming Systems, Languages and Applications, pp. 406\u2013416. ACM Press, New York (1986)"},{"key":"1_CR100","first-page":"251","volume-title":"VLDB","author":"A. Klausner","year":"1985","unstructured":"Klausner, A., Goodman, N.: Multirelations \u2014 Semantics and Languages. In: VLDB. Proc. International Conference on Very Large Data Bases, vol.\u00a011, pp. 251\u2013258. Morgan Kaufmann, San Francisco (1985)"},{"key":"1_CR101","doi-asserted-by":"crossref","unstructured":"Koch, C.: On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values. ACM Transactions on Database Systems\u00a031(4) (2006)","DOI":"10.1145\/1189769.1189771"},{"key":"1_CR102","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0022-0000(91)90033-2","volume":"43","author":"P. Kolaitis","year":"1991","unstructured":"Kolaitis, P., Papadimitriou, C.: Why Not Negation by Fixpoint? Journal of Computer and System Sciences\u00a043, 125\u2013144 (1991)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"1_CR103","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1145\/155271.155274","volume":"18","author":"G.M. Kuper","year":"1993","unstructured":"Kuper, G.M., Vardi, M.Y.: The Logical Data Model. ACM Transactions on Database Systems\u00a018(3), 379\u2013413 (1993)","journal-title":"ACM Transactions on Database Systems"},{"issue":"1","key":"1_CR104","doi-asserted-by":"publisher","first-page":"67","DOI":"10.2307\/421076","volume":"6","author":"J.-M. Bars Le","year":"2000","unstructured":"Le Bars, J.-M.: Counterexamples of the 0-1 Law for Fragments of Existential Second-order Logic: an Overview. Bulletin of Symbolic Logic\u00a06(1), 67\u201382 (2000)","journal-title":"Bulletin of Symbolic Logic"},{"issue":"3","key":"1_CR105","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s10849-005-5789-8","volume":"14","author":"D. Leinders","year":"2005","unstructured":"Leinders, D., Marx, M., Tyszkiewicz, J., den Bussche, J.V.: The Semijoin Algebra and the Guarded Fragment. Journal of Logic, Language and Information\u00a014(3), 331\u2013343 (2005)","journal-title":"Journal of Logic, Language and Information"},{"key":"1_CR106","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0022-0000(89)90019-6","volume":"39","author":"D. Leivant","year":"1989","unstructured":"Leivant, D.: Descriptive Characterizations of Computational Complexity. Journal of Computer and System Sciences\u00a039, 51\u201383 (1989)","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR107","first-page":"204","volume-title":"LICS","author":"L. Libkin","year":"1997","unstructured":"Libkin, L.: On the Forms of Locality over Finite Models. In: LICS. Proc. IEEE Conference on Logic in Computer Science, pp. 204\u2013215. IEEE Computer Society Press, Los Alamitos (1997)"},{"key":"1_CR108","first-page":"155","volume-title":"PODS","author":"L. Libkin","year":"1994","unstructured":"Libkin, L., Wong, L.: New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 155\u2013166. ACM Press, New York (1994)"},{"issue":"2","key":"1_CR109","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1006\/jcss.1997.1523","volume":"55","author":"L. Libkin","year":"1997","unstructured":"Libkin, L., Wong, L.: Query Languages for Bags and Aggregate Functions. Journal of Computer and System Sciences\u00a055(2), 241\u2013272 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR110","doi-asserted-by":"crossref","unstructured":"Lindstr\u00f6m, P.: On Extensions of Elementary Logic. Theoria\u00a035 (1969)","DOI":"10.1111\/j.1755-2567.1969.tb00356.x"},{"key":"1_CR111","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-83189-8","volume-title":"Foundations of Logic Programming","author":"J. Lloyd","year":"1987","unstructured":"Lloyd, J.: Foundations of Logic Programming, 2nd edn. Springer, Heidelberg (1987)","edition":"2"},{"key":"1_CR112","series-title":"Logic Programming Series","volume-title":"Foundations of Disjunctive Logic Programming","author":"J. Lobo","year":"1992","unstructured":"Lobo, J., Minker, J., Rajasekar, A.: Foundations of Disjunctive Logic Programming. Logic Programming Series. MIT Press, Cambridge (1992)"},{"key":"1_CR113","unstructured":"Makinouchi, A.: A Consideration of Normal Form of Not-necessarily-normalized Relations in the Relational Data Model. In: VLDB. Proc. International Conference on Very Large Data Bases, pp. 447\u2013453 (1977)"},{"key":"1_CR114","unstructured":"Manola, F., Miller, E.: RDF Primer. Recommendation, W3C (2004)"},{"issue":"3","key":"1_CR115","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1145\/116825.116836","volume":"38","author":"W. Marek","year":"1991","unstructured":"Marek, W., Truszczy\u0144ski, M.: Autoepistemic Logic. Journal of the Association for Computing Machinery\u00a038(3), 588\u2013619 (1991)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"1_CR116","unstructured":"Martelli, A., Montanari, U.: Unification in Linear Time and Space: a Structured Presentation. Technical Report B 76-16, University of Pisa (1976)"},{"issue":"1","key":"1_CR117","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/962446.962448","volume":"51","author":"G. Miklau","year":"2004","unstructured":"Miklau, G., Suciu, D.: Containment and Equivalence for a Fragment of XPath. Journal of the Association for Computing Machinery\u00a051(1), 2\u201345 (2004)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"1_CR118","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/BFb0000066","volume-title":"6th Conference on Automated Deduction","author":"J. Minker","year":"1982","unstructured":"Minker, J.: On Indefinite Data Bases and the Closed World Assumption. In: Loveland, D.W. (ed.) 6th Conference on Automated Deduction. LNCS, vol.\u00a0138, pp. 292\u2013308. Springer, Heidelberg (1982)"},{"key":"1_CR119","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01530759","volume":"12","author":"J. Minker","year":"1994","unstructured":"Minker, J.: Overview of Disjunctive Logic Programming. Annals of Mathematics and Artificial Intelligence\u00a012, 1\u201324 (1994)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"1","key":"1_CR120","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(88)90124-X","volume":"29","author":"M. Minoux","year":"1988","unstructured":"Minoux, M.: LTUR: A Simplified Linear-Time Unit Resolution Algorithm for Horn Formulae and Computer Implementation. Information Processing Letters\u00a029(1), 1\u201312 (1988)","journal-title":"Information Processing Letters"},{"issue":"1","key":"1_CR121","doi-asserted-by":"crossref","first-page":"49","DOI":"10.3233\/FI-1996-25105","volume":"25","author":"P. Narendran","year":"1996","unstructured":"Narendran, P.: Unification Modulo ACI+1+0. Fundamenta Informaticae\u00a025(1), 49\u201357 (1996)","journal-title":"Fundamenta Informaticae"},{"key":"1_CR122","first-page":"43","volume-title":"VLDB","author":"W. Nejdl","year":"1987","unstructured":"Nejdl, W.: Recursive Strategies for Answering Recursive Queries - The RQA\/FQI Strategy. In: VLDB. Proc. International Conference on Very Large Data Bases, pp. 43\u201350. Morgan Kaufmann Publishers Inc, San Francisco (1987)"},{"key":"1_CR123","unstructured":"Niemel\u00e4, I., Simons, P.: Efficient Implementation of the Well-founded and Stable Model Semantics. In: Proc. Joint International Conference and Symposium on Logic Programming, pp. 289\u2013303 (1996)"},{"key":"1_CR124","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36128-6_7","volume-title":"XML-Based Data Management and Multimedia Engineering - EDBT 2002 Workshops","author":"D. Olteanu","year":"2002","unstructured":"Olteanu, D., Meuss, H., Furche, T., Bry, F.: XPath: Looking Forward. In: Chaudhri, A.B., Unland, R., Djeraba, C., Lindner, W. (eds.) EDBT 2002. LNCS, vol.\u00a02490, Springer, Heidelberg (2002)"},{"key":"1_CR125","first-page":"21","volume":"26","author":"C. Papadimitriou","year":"1985","unstructured":"Papadimitriou, C.: A Note on the Expressive Power of Prolog. Bulletin of the EATCS\u00a026, 21\u201323 (1985)","journal-title":"Bulletin of the EATCS"},{"key":"1_CR126","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley Publishing Co, Reading (1994)"},{"key":"1_CR127","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","volume":"71","author":"C. Papadimitriou","year":"1985","unstructured":"Papadimitriou, C., Yannakakis, M.: A Note on Succinct Representations of Graphs. Information and Control\u00a071, 181\u2013185 (1985)","journal-title":"Information and Control"},{"key":"1_CR128","unstructured":"Paparizos, S., Jagadish, H.V.: Pattern Tree Algebras: Sets or Sequences. In: VLDB. Proc. International Conference on Very Large Data Bases, pp. 349\u2013360. VLDB Endowment (2005)"},{"issue":"1","key":"1_CR129","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1145\/128765.128768","volume":"17","author":"J. Paredaens","year":"1992","unstructured":"Paredaens, J., Gucht, D.V.: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Transactions on Database Systems\u00a017(1), 65\u201393 (1992)","journal-title":"ACM Transactions on Database Systems"},{"key":"1_CR130","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/0022-0000(78)90043-0","volume":"16","author":"M. Paterson","year":"1978","unstructured":"Paterson, M., Wegman, M.: Linear Unification. Journal of Computer and System Sciences\u00a016, 158\u2013167 (1978)","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR131","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: Satisfiability of Word Equations with Constants is in PSPACE. In: FOCS. Proc. Annual Symposium on Foundations of Computer Science, pp. 495\u2013500 (1999)","DOI":"10.1145\/301250.301443"},{"key":"1_CR132","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/B978-0-934613-40-8.50009-9","volume-title":"Foundations of Deductive Databases and Logic Programming, ch. 5","author":"T. Przymusinsik","year":"1988","unstructured":"Przymusinsik, T.: On the Declarative Semantics of Deductive Databases and Logic Programs. In: Minker, J. (ed.) Foundations of Deductive Databases and Logic Programming, ch. 5, pp. 193\u2013216. Morgan Kaufmann, San Francisco (1988)"},{"key":"1_CR133","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/BF03037171","volume":"9","author":"T. Przymusinski","year":"1991","unstructured":"Przymusinski, T.: Stable Semantics for Disjunctive Programs. New Generation Computing\u00a09, 401\u2013424 (1991)","journal-title":"New Generation Computing"},{"key":"1_CR134","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF01530826","volume":"14","author":"T. Przymusinski","year":"1995","unstructured":"Przymusinski, T.: Static Semantics for Normal and Disjunctive Logic Programs. Annals of Mathematics and Artificial Intelligence\u00a014, 323\u2013357 (1995)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"2","key":"1_CR135","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF00243002","volume":"5","author":"T.C. Przymusinski","year":"1989","unstructured":"Przymusinski, T.C.: On the Declarative and Procedural Semantics of Logic Programs. Journal of Automated Reasoning\u00a05(2), 167\u2013205 (1989)","journal-title":"Journal of Automated Reasoning"},{"key":"1_CR136","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1145\/564691.564726","volume-title":"SIGMOD","author":"P. Ramanan","year":"2002","unstructured":"Ramanan, P.: Efficient Algorithms for Minimizing Tree Pattern Queries. In: SIGMOD. Proc. ACM SIGMOD Symposium on the Management of Data, pp. 299\u2013309. ACM Press, New York (2002)"},{"key":"1_CR137","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/978-1-4684-3384-5_3","volume-title":"Logic and Data Base","author":"R. Reiter","year":"1978","unstructured":"Reiter, R.: On Closed World Data Bases. In: Gallaire, H., Minker, J. (eds.) Logic and Data Base, pp. 55\u201376. Plenum Press, New York, USA (1978)"},{"issue":"1","key":"1_CR138","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/321250.321253","volume":"12","author":"J. Robinson","year":"1965","unstructured":"Robinson, J.: A Machine-Oriented Logic Based on the Resolution Principle. Journal of the Association for Computing Machinery\u00a012(1), 23\u201341 (1965)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"1_CR139","volume-title":"PODS","author":"K. Ross","year":"1990","unstructured":"Ross, K.: Modular Stratification and Magic Sets for Datalog Programs with Negation. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ACM Press, New York (1990)"},{"key":"1_CR140","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0743-1066(92)90019-Y","volume":"13","author":"K. Ross","year":"1992","unstructured":"Ross, K.: A Procedural Semantics for Well-Founded Negation in Logic Programs. Journal of Logic Programming\u00a013, 1\u201322 (1992)","journal-title":"Journal of Logic Programming"},{"key":"1_CR141","unstructured":"Schaffert, S., Bry, F.: Querying the Web Reconsidered: A Practical Introduction to Xcerpt. In: Proc. Extreme Markup Languages (2004)"},{"issue":"1","key":"1_CR142","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1006\/jcss.1995.1053","volume":"51","author":"J. Schlipf","year":"1995","unstructured":"Schlipf, J.: The Expressive Powers of the Logic Programming Semantics. Journal of Computer and System Sciences\u00a051(1), 64\u201386 (1995)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"1_CR143","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1145\/974121.974140","volume":"33","author":"T. Schwentick","year":"2004","unstructured":"Schwentick, T.: XPath Query Containment. SIGMOD Record\u00a033(1), 101\u2013109 (2004)","journal-title":"SIGMOD Record"},{"key":"1_CR144","unstructured":"Schwichtenberg, H.: Logikprogrammierung. Institute for Mathematics, University of Munich (1993)"},{"key":"1_CR145","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0743-1066(91)90003-8","volume":"10","author":"J. Sheperdson","year":"1991","unstructured":"Sheperdson, J.: Unsolvable Problems for SLDNF-Resolution. Journal of Logic Programming\u00a010, 19\u201322 (1991)","journal-title":"Journal of Logic Programming"},{"issue":"1","key":"1_CR146","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1145\/319540.319561","volume":"6","author":"D.W. Shipman","year":"1981","unstructured":"Shipman, D.W.: The Functional Data Model and the Data Languages DAPLEX. ACM Transactions on Database Systems\u00a06(1), 140\u2013173 (1981)","journal-title":"ACM Transactions on Database Systems"},{"issue":"2","key":"1_CR147","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/565117.565119","volume":"31","author":"G. Slivinskas","year":"2002","unstructured":"Slivinskas, G., Jensen, C.S., Snodgrass, R.T.: Bringing Order to Query Optimization. SIGMOD Record\u00a031(2), 5\u201314 (2002)","journal-title":"SIGMOD Record"},{"issue":"3","key":"1_CR148","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1145\/320473.320476","volume":"1","author":"M. Stonebraker","year":"1976","unstructured":"Stonebraker, M., Held, G., Wong, E., Kreps, P.: The Design and Implementation of INGRES. ACM Transactions on Database Systems\u00a01(3), 189\u2013222 (1976)","journal-title":"ACM Transactions on Database Systems"},{"key":"1_CR149","first-page":"201","volume-title":"PODS","author":"D. Suciu","year":"1994","unstructured":"Suciu, D., Paredaens, J.: Any Algorithm in the Complex Object Algebra with Powerset needs Exponential Space to Compute Transitive Closure. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 201\u2013209. ACM Press, New York (1994)"},{"key":"1_CR150","doi-asserted-by":"crossref","unstructured":"Tamaki, H., Sato, T.: OLDT Resolution with Tablulation. In: International Conference on Logic Programming, pp. 84\u201398 (1986)","DOI":"10.1007\/3-540-16492-8_66"},{"key":"1_CR151","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01932293","volume":"17","author":"S.-A. T\u00e4rnlund","year":"1977","unstructured":"T\u00e4rnlund, S.-A.: Horn Clause Computability. BIT Numerical Mathematics\u00a017, 215\u2013216 (1977)","journal-title":"BIT Numerical Mathematics"},{"key":"1_CR152","first-page":"291","volume-title":"PODS","author":"J. Bussche van den","year":"1991","unstructured":"van den Bussche, J., Paredaens, J.: The Expressive Power of Structured Values in Pure OODBs. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 291\u2013299. ACM Press, New York (1991)"},{"issue":"4","key":"1_CR153","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1145\/321978.321991","volume":"23","author":"M. Emden van","year":"1976","unstructured":"van Emden, M., Kowalski, R.: The Semantics of Predicate Logic as a Programming Language. Journal of the Association for Computing Machinery\u00a023(4), 733\u2013742 (1976)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"1_CR154","first-page":"1","volume-title":"PODS","author":"A. Gelder van","year":"1989","unstructured":"van Gelder, A.: The Alternating Fixpoint of Logic Programs With Negation. In: PODS. Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 1\u201310. ACM Press, New York (1989)"},{"issue":"3","key":"1_CR155","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1145\/116825.116838","volume":"38","author":"A. Gelder van","year":"1991","unstructured":"van Gelder, A., Ross, K., Schlipf, J.: The Well-Founded Semantics for General Logic Programs. Journal of the Association for Computing Machinery\u00a038(3), 620\u2013650 (1991)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"1_CR156","doi-asserted-by":"crossref","unstructured":"Vardi, M.: The Complexity of Relational Query Languages. In: STOC. ACM Symposium on Theory of Computing, pp. 137\u2013146, San Francisco (1982)","DOI":"10.1145\/800070.802186"},{"key":"1_CR157","unstructured":"Veith, H.: Logical Reducibilities in Finite Model Theory. Master\u2019s thesis, Information Systems Department, TU Vienna, Austria (September 1994)"},{"key":"1_CR158","unstructured":"Vieille, L.: A Database-Complete Proof Procedure Based on SLD-Resolution. In: International Conference on Logic Programming, pp. 74\u2013103 (1987)"},{"key":"1_CR159","unstructured":"von B\u00fcltzingsloewen, G.: Translating and Optimizing SQL Queries Having Aggregates. In: VLDB. Proc. International Conference on Very Large Data Bases, pp. 235\u2013243, San Francisco, CA, USA (1987)"},{"key":"1_CR160","doi-asserted-by":"crossref","unstructured":"Warren, D.H.D., Pereira, L.M., Pereira, F.: Prolog - the Language and its Implementation compared with Lisp. In: Proc. Symposium on Artificial Intelligence and Programming Languages, pp. 109\u2013115 (1977)","DOI":"10.1145\/872736.806939"},{"key":"1_CR161","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/319759.319773","volume-title":"WIDM","author":"P.T. Wood","year":"1999","unstructured":"Wood, P.T.: Optimising Web Queries using Document Type Definitions. In: WIDM. Proc. ACM Int\u2019l. Workshop on Web Information and Data Management, pp. 28\u201332. ACM Press, New York (1999)"},{"key":"1_CR162","unstructured":"Yasuura, H.: On Parallel Computational Complexity of Unification. In: Proc. International Conference on Fifth Generation Computer Systems, pp. 235\u2013243. ICOT (1984)"}],"container-title":["Lecture Notes in Computer Science","Reasoning Web"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74615-7_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T13:50:09Z","timestamp":1737381009000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74615-7_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540746133","9783540746157"],"references-count":162,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74615-7_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}