{"entities":{"Q579967":{"pageid":581734,"ns":120,"title":"Item:Q579967","lastrevid":62945112,"modified":"2026-04-11T09:09:32Z","type":"item","id":"Q579967","labels":{"en":{"language":"en","value":"Querying logical databases"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4016237"}},"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":"Q579967$4C1E1B10-9EA1-45AC-AFFA-DA92EECF1176","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1c6681cd59876ed2f773da1123867418967036b2","datavalue":{"value":{"text":"Querying logical databases","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q579967$F5F3EBE3-7758-45FF-BDA1-245CD72CF28A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"769ba1bceabbac8b550a3f2544b6701164abc023","datavalue":{"value":"0625.68079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579967$21BA6B32-0ADD-498C-AE96-A8E8E6AE9B5B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eeef2b2d0018915f617c31aacfc81c732ce7cd09","datavalue":{"value":"10.1016/0022-0000(86)90016-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579967$C4BF057B-5545-4E72-B527-54E9E1C5E820","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce87cbb6ded942a7df2b71cd7e21808de8efe775","datavalue":{"value":{"entity-type":"item","numeric-id":208771,"id":"Q208771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579967$802B8083-1970-4FE7-98A3-C4A81B38A90B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579967$FC455188-8AE1-4E16-A84B-1096D688127C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q579967$034B4102-4287-4367-B39B-F721D050333B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d751b293be642ba21d901740085732c69f35e3df","datavalue":{"value":"We study here the complexity of evaluating queries in logical databases. We focus on Reither's model of closed-world databases with unknown values. We show that in this setting query evaluation is harder than query evaluation for physical databases. For example, while 1st-order queries over physical databases can be evaluated in logarithmic space, evaluation of 1st-order queries in the studied model is co-NP-complete. We describe an approximation algorithm for query evaluation that enables one to implement a logical database on the top of a standard database management system.","type":"string"},"datatype":"string"},"type":"statement","id":"Q579967$9BB0DCD0-289D-4C18-949E-A32F165F87CE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579967$9BC83F7C-5CDC-49DD-8D16-BA423B1FAC49","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"31ed268e1867695bcc8b0fc71d7988f219ea5ca7","datavalue":{"value":"4016237","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579967$D435BB56-26C6-492E-BCFA-24368CD285A1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7781db5f810100b1c75183665ffe0c10b181c915","datavalue":{"value":"relational databases","type":"string"},"datatype":"string"},"type":"statement","id":"Q579967$01916500-E4C5-451F-9481-694301CD2687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba9061ec85d3543137b2ca4331cc35a49f58bb7","datavalue":{"value":"complexity of evaluating queries in logical databases","type":"string"},"datatype":"string"},"type":"statement","id":"Q579967$5F982A98-CFF8-4358-8E6C-5E108342DEE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5106d69c1ca403fd14d105a74924844f774bd87","datavalue":{"value":"closed-world databases with unknown values","type":"string"},"datatype":"string"},"type":"statement","id":"Q579967$6C90C885-52C2-41F8-B87D-64ED49DEAEEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q579967$A15EF790-828F-4BBC-8FCA-F3925A366D90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb2eabae2cb4d3373375d214f5a564fc209a3b9f","datavalue":{"value":"database management","type":"string"},"datatype":"string"},"type":"statement","id":"Q579967$8267891C-77A6-4E01-A6E6-EC9A791A49E0","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":"Q579967$3C9C96FE-C3CF-48CB-9601-0873C927E25B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9f42edfaca95b5c1b21826980bfcf48cb75f7e7a","datavalue":{"value":"https://doi.org/10.1016/0022-0000(86)90016-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q579967$DF0DE480-610B-45AA-96B3-0B91BDDDC2F5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7cd846af2f994b473b5512e00cc511d117afe1c3","datavalue":{"value":"W2032728598","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579967$FAE83EE7-3F9A-4A85-9BFC-52A803543A0A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"04199e03d1d3ec0d2b5fbfff526a164b91654871","datavalue":{"value":{"entity-type":"item","numeric-id":1838840,"id":"Q1838840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579967$EDAF2F7E-2A1C-48D8-B135-628823988528","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579967$22A5B7FE-E28A-4DE7-80FC-E7850F9ED120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b577d08ccd514d106aef6448d3d43d248533905a","datavalue":{"value":{"entity-type":"item","numeric-id":1245581,"id":"Q1245581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579967$B37E1F29-F618-4E3F-8B2F-2ED597C08A9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76405b78f809a05579a4fbf1f4f88107da42220d","datavalue":{"value":{"entity-type":"item","numeric-id":1086223,"id":"Q1086223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579967$57DA2000-9F65-4EC8-969D-311DF40A254E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5f91daa2195cbe510cefc59ffaafa18b1c28390","datavalue":{"value":{"entity-type":"item","numeric-id":4107888,"id":"Q4107888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579967$FA725416-EEEB-4BB8-838F-2BA5C79594FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01d6649d4853baff3b254e51c9979c2133405503","datavalue":{"value":{"entity-type":"item","numeric-id":1140434,"id":"Q1140434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579967$7667BF0D-A97B-4D19-B441-7D54ABF9E39B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579967$E0E29C09-D876-4E0F-A4B8-AF84D58A4488","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61c367589c40ff64186f6fbbb974c8ed689aaab1","datavalue":{"value":{"entity-type":"item","numeric-id":3975939,"id":"Q3975939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1c0df0535b3ed7452cd0c5198fb85212056d34e","datavalue":{"value":{"amount":"+0.7801849246025085","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":"Q579967$5BB1F9A5-1825-49AE-B32E-F6A9ACDB6DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f433e02e4bec643005f7fe3a1b61b145a925841b","datavalue":{"value":{"entity-type":"item","numeric-id":4694689,"id":"Q4694689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1c0df0535b3ed7452cd0c5198fb85212056d34e","datavalue":{"value":{"amount":"+0.7801849246025085","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":"Q579967$377F427B-0ADF-4E8C-9039-4D4689F3FC21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eafe423d4259b9c83b233ee4f2f15cf94703830f","datavalue":{"value":{"entity-type":"item","numeric-id":3786039,"id":"Q3786039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fa4d79a7aa137c766316440f637d463d3a5023e","datavalue":{"value":{"amount":"+0.7702386975288391","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":"Q579967$9E9FB956-8FC6-45DB-B6D5-AB38EAC96234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdb177b67afe75cdca7ee038b4b2fe6ec943112e","datavalue":{"value":{"entity-type":"item","numeric-id":3839873,"id":"Q3839873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfd5ea7b06de1dab8453dcc940ee002d752e10cd","datavalue":{"value":{"amount":"+0.7553601861000061","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":"Q579967$114BC2BA-5F9C-4149-BA58-3FF28FD84458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32a3e029d94f2c04e382aab8c58b7b0e3eb2472f","datavalue":{"value":{"entity-type":"item","numeric-id":3691103,"id":"Q3691103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8efe46e575919b4c8a335dcf9479d352e0eb7357","datavalue":{"value":{"amount":"+0.7510351538658142","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":"Q579967$F1C033D0-8E35-477F-9D7B-4C8D4F0056A3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Querying logical databases","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Querying_logical_databases"}}}}}