{"entities":{"Q677720":{"pageid":679569,"ns":120,"title":"Item:Q677720","lastrevid":46726818,"modified":"2025-12-25T11:45:44Z","type":"item","id":"Q677720","labels":{"en":{"language":"en","value":"Languages PQL and FO+LFP remain equivalent even in the absence of order"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 999697"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677720$D556E571-432C-4EC2-8FCC-3EEDB040846C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cd8b28fb9dc0d0b61cdf9ed274345b6eb9d29b5f","datavalue":{"value":{"text":"Languages PQL and FO+LFP remain equivalent even in the absence of order","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q677720$833362A3-B183-41B6-8AB1-4D77481BA371","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bb38cc85fb8681dc5ddc1d85dbd994532bd2c8ad","datavalue":{"value":"0868.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677720$7D9B383A-C4E5-4F50-8F17-B12E2F7EB12B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ccce872f1af1eb8d0ef14829bf3d0a4e263623f","datavalue":{"value":{"entity-type":"item","numeric-id":677718,"id":"Q677718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677720$B839C96B-E8E6-47B5-80FC-881CB6727146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb9f39df6e32b185b7f91c7268351e4d3016c06c","datavalue":{"value":{"entity-type":"item","numeric-id":677719,"id":"Q677719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677720$03AC16D4-9101-4120-998F-35F6E15634CB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62318960435ff4e0b6f0bda102e1b989b0fc569e","datavalue":{"value":{"entity-type":"item","numeric-id":268929,"id":"Q268929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677720$4741A7CA-C5C0-4A63-BB29-953DA45F81D3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"876845907317718d8e2d04e1f7e4d5bd9d4ff527","datavalue":{"value":{"time":"+1997-06-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q677720$E803C28A-6FEC-4561-B3D1-C46E686D7AB9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a6bef344379cefd46bed90aa6a10ffd5c6f13ceb","datavalue":{"value":"Let \\(\\text{FO}+\\text{LFP}\\) be a first-order language completed with the least fixed-point operator. \\textit{M. Y. Vardi} [``Complexity of relational query languages'', Proc. 14th ACM Symp. Theory of Computing, San Francisco 1982, 137-146 (1982)] and \\textit{N. Immerman} [``Relational queries computable in polynomial time'', ibid. 146-152 (1982); see also Inf. Control 68, 86-104 (1986; Zbl 0612.68086)] have shown that, in the presence of an order, in the language \\(\\text{FO}+\\text{LFP}\\) all the polynomial time queries to relational databases are exactly expressible. The second author [\\textit{A. B. Livchak}, ``The language of polynomial programs'', in: Design and optimization of thermotechnical and electrochemical objects by means of computer, Sverdlovsk, 1982, 40 (1982); ``The language of polynomial queries'', ibid. 41 (1982)] described the languages \\(\\text{RPC}+\\) and \\(\\text{PQL}\\) which possess an analogous property.   A natural question arises: Whether the mentioned languages will be equivalent if the order is not present? Partial answer to this question was given by \\textit{Y. Gurevich} and \\textit{S. Shelah} [Ann. Pure Appl. Logic 32, 265-280 (1986; Zbl 0621.03013)], who proved that the languages \\(\\text{FO}+\\text{LFP}\\) and \\(\\text{RPC}+\\) are equivalent as well in the general situation. It remains to clarify the interrelations of these languages with \\(\\text{PQL}\\). This is the subject of the present article.","type":"string"},"datatype":"string"},"type":"statement","id":"Q677720$50EB4A25-7490-4CDF-AF81-6E96EEA40D9D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677720$2CD015F0-0086-4E9B-92D0-DE2DAA2ED366","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a22dd8e0d4d79d9dd5861e5644f7b75849e2e23b","datavalue":{"value":"999697","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677720$6FCD587F-8EDB-47A8-964E-9547467D9610","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7c680ca79b35baa840acc8cd38f4a23dfac81d5","datavalue":{"value":"first-order language","type":"string"},"datatype":"string"},"type":"statement","id":"Q677720$8DE1E121-7300-4E93-8F68-FC7DA1CA803E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d0f40726dd200b28b87c13fffd407d4d9cb56fb","datavalue":{"value":"least fixed-point operator","type":"string"},"datatype":"string"},"type":"statement","id":"Q677720$8EF55DC9-90CA-41F1-94D5-31790994DD25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8adf439617450ead70a3daccb8b698721eb9042c","datavalue":{"value":"polynomial time queries","type":"string"},"datatype":"string"},"type":"statement","id":"Q677720$33D1B503-45F6-4FFF-97BB-07D12B1CA924","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7781db5f810100b1c75183665ffe0c10b181c915","datavalue":{"value":"relational databases","type":"string"},"datatype":"string"},"type":"statement","id":"Q677720$B5664222-447E-470F-8BDC-7A79CFFAB868","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677720$9C143F2C-5C70-41EB-8A64-BDEE174E9D98","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c85214c6893aa6423eadb5a8f3d755e72e01953","datavalue":{"value":{"entity-type":"item","numeric-id":3753525,"id":"Q3753525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8d10f5a467e6c0e15c1079b0b0db034f5128976","datavalue":{"value":{"amount":"+0.7746170163154602","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q677720$3272ABEC-51AE-4D38-B0AC-4BF44F2989CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee551284211c0c7eb59b86d9972bb28d3a85a796","datavalue":{"value":{"entity-type":"item","numeric-id":1893734,"id":"Q1893734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59a21d1c8fcb50006cb2c39d58e0cb1d3b549a8b","datavalue":{"value":{"amount":"+0.7595625519752502","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q677720$C691056D-F961-4341-AA51-7E06BE7FD414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08b38c8895f2b3f771213dd4e85f0210ad36715d","datavalue":{"value":{"entity-type":"item","numeric-id":3359746,"id":"Q3359746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"439bbde25c3292495f96223995804d9abf57572e","datavalue":{"value":{"amount":"+0.7551198601722717","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q677720$2452DAA2-4917-45D5-B3D0-C8AB7A46E61A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"075c03d8d00aaf5fd2eedf28b7196d85a8998f86","datavalue":{"value":{"entity-type":"item","numeric-id":2510772,"id":"Q2510772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f6b98e895f24f334d388b2c6b86daaf55ff3d65","datavalue":{"value":{"amount":"+0.753461480140686","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q677720$3F33A9F4-383E-4561-925A-208841B20123","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5449d23acd92310c99e31994617633fbe5e5a66","datavalue":{"value":{"entity-type":"item","numeric-id":4283240,"id":"Q4283240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc1d3b9c09fa2943971429622d146bcc93f93f15","datavalue":{"value":{"amount":"+0.74689120054245","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q677720$00DE0755-FE8A-483A-8349-EF40E3E61FD0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:677720","badges":[]}}}}}