Query evaluation

Not to be confused with question answering.

In database theory, the query evaluation problem is the problem[verification needed] of determining the answers to a query on a database. Research in database theory aims at determining the computational complexity of answering different kinds of queries over databases, in particular over relational databases.

Formal definition

The query evaluation problem takes two inputs: the query to be answered, and the database on which to answer it. The output of the problem is the set of answers to the query on the database. If the queries are Boolean queries, i.e., queries have a yes or no answer (for example, Boolean conjunctive queries) then the query evaluation problem is a decision problem.

The query evaluation problem is usually posed for a specific class of queries and databases. For instance, one example of the query evaluation problem would be the problem of evaluating a conjunctive query on a relational database.

The computational complexity of the problem can be measured in different ways,[1] to account for the fact that the two inputs of the problem are different:

  • The combined complexity of the query evaluation problem is its computational complexity when measured as a function of the two inputs, i.e., the query and the database, as usual in computational complexity.
  • The data complexity is the computational complexity when the query is fixed and when the input is just the database. For instance, we say that query evaluation has polynomial-time data complexity for a class of queries if, for every fixed query Q in that class, given a database D, we can compute the answers to Q on D in polynomial time.
  • Less commonly, we can study the query complexity, which is the computational complexity when the database is fixed and when the input is just the query. This is also called expression complexity.[2]

Query classes

The complexity of query evaluation can be studied for several query classes, for instance acyclic queries, conjunctive queries, unions of conjunctive queries, Datalog, regular path queries, etc., up to logical formalisms like first-order logic or monadic second-order logic.

For instance, for Boolean conjunctive queries, the complexity of query evaluation is polynomial in data complexity: it even falls in the class AC0. By contrast, the query complexity and combined complexity are NP-complete[3] by a reduction from 3-colorability.[citation needed]

Boolean versus non-Boolean queries

The complexity of query evaluation can be studied for queries that return answers, or for Boolean queries (yes/no queries). However, we can often reduce to the case of Boolean queries. More specifically, if the number of answers to the query is always polynomial in the database size, and if we can rewrite the query to a Boolean query for each answer, then we can reduce query evaluation for a non-Boolean query to polynomially many Boolean query evaluation problems.[citation needed]

References

  1. ^ Vardi, Moshe Y. (1982-05-05). "The complexity of relational query languages (Extended Abstract)". Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82. New York, NY, USA: Association for Computing Machinery. pp. 137–146. doi:10.1145/800070.802186. ISBN 978-0-89791-070-5.
  2. ^ Abiteboul, Serge; Hull, Richard; Vianu, Victor (1994-12-02). Foundations of Databases: The Logical Level (1st ed.). Reading, Mass.: Pearson. ISBN 978-0-201-53771-0.
  3. ^ Greco, Gianluigi; Scarcello, Francesco (2014-06-18). "Counting solutions to conjunctive queries: Structural and hybrid tractability". Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. PODS '14. New York, NY, USA: Association for Computing Machinery. pp. 132–143. doi:10.1145/2594538.2594559. ISBN 978-1-4503-2375-8.

Read other articles:

羅生門 (電影)

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。 此條目需要补充更多来源。 (2018年3月17日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的标题（来源搜索：羅生門 (電影) — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。 �...

 

نادي الشباب (عمان)

  لمعانٍ أخرى، طالع نادي الشباب (توضيح). نادي الشباب (عمان) تأسس عام 2003 (العمر 20–21) الملعب ملعب الرستاق - المجمع الرياضي بالرستاق البلد سلطنة عمان  الدوري دوري عمانتل دوري عمانتل 2023-2024 العاشر الرئيس أحمد بن عبدالله العويسي المدرب فوزي البنزرتي  الموقع الرسمي الم�...

 

The Becoming (EP)

2007 EP by After Midnight ProjectThe BecomingEP by After Midnight ProjectReleased2007GenreAlternative rock, post-grungeLabelSelf-releasedProducerJason Evigan and Evan A. RichardsonAfter Midnight Project chronology After Midnight Project(2005) The Becoming(2007) Let's Build Something to Break(2009) The Becoming is an EP released by American rock band, After Midnight Project. It was released in 2007. This album caught the attention of Universal Motown and eventually led to the band bein...

بلجيكا في الألعاب الأولمبية

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (فبراير 2016) بلجيكا في الألعاب الأولمبية علم بلجيكا رمز ل.أ.د.  BEL ل.أ.و. اللجنة الأولمبية البلجيكيةComité Olympique...

 

Raised beach

Emergent coastal landform Marine terrace redirects here. For the street in Fremantle, see Marine Terrace, Fremantle. Raised beach and marine terraces at Water Canyon beach A raised beach, now at 4 metres (13 ft) above high tide, formed King's Cave, Arran, below an earlier raised beach at around 30 metres (98 ft) height. A raised beach, coastal terrace,[1] or perched coastline is a relatively flat, horizontal or gently inclined surface of marine origin,[2] mostly an o...

 

Sawtooth Mountains (Minnesota)

Highland region in Minnesota, United States The Sawtooth Mountains on the shore of Lake Superior, looking west by southwest from Grand Marais, Minnesota The Sawtooth Mountains are a range of hills or small mountains on the North Shore of Lake Superior in the U.S. state of Minnesota, extending about 30 miles (48 km) from Carlton Peak near Tofte on the west, to Grand Marais on the east.[1] Description Cross-section of the Lake Superior basin east of the Sawtooths, showing the tilte...

John H. Glenn Jr. (fireboat)

The John H. Glenn Jr. docked in Washington, D.C., on September 16, 2010. History NameJohn H. Glenn Jr. NamesakeJohn Glenn, astronaut OwnerNew York City Fire Department Launched1962-09-22[1] FateSold to DCFD, 1977 History OwnerDistrict of Columbia Fire and Emergency Medical Services Department Acquired1977 StatusActive General characteristics Class and typeFireboat Displacement84 tons[3] Length71 ft (22 m)[3] Beam21 ft (6.4 m)[2] Draught5...

 

Brian Bosma

American politician from Indiana Brian BosmaSpeaker of the Indiana House of RepresentativesIn officeNovember 16, 2010 – March 9, 2020Preceded byPatrick BauerSucceeded byTodd HustonIn officeNovember 16, 2004 – November 21, 2006Preceded byPatrick BauerSucceeded byPatrick BauerMember of the Indiana House of Representativesfrom the 88th districtIn officeNovember 4, 1992 – July 31, 2020Preceded byConstituency establishedSucceeded byChris JeterMember of ...

 

Dan Bern

American singer-songwriter Not to be confused with Dan Burn. Dan BernBern in August 1999.Background informationBirth nameDaniel BernAlso known asBernsteinCunliffe MerriwetherBorn (1965-07-27) July 27, 1965 (age 58)Mount Vernon, Iowa, U.S.GenresFolk, rock, popOccupation(s)Musician, songwriter, author, visual artistInstrument(s)Vocals, guitar, harmonicaYears active1996-presentLabelsMessenger, Cooking Vinyl, WorkWebsitedanbern.comMusical artist Dan Bern (also known as Bernstein; born July 2...

كأس الدوري البرتغالي 2016–17

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (يوليو 2020) كأس الدوري البرتغالي 2016–17 تفاصيل الموسم كأس الدوري البرتغالي  النسخة 10  البلد البرتغال  التاريخ ب...

 

Castelcivita

Pemandangan Castelcivita Castelcivita adalah kota (komune) di region Campania di provinsi salerno, Italia. Geografi Kota yang terletak di tengah-tengah Cilento, di sisi barat pegunungan Alburni. Kota tetangga termasuk Controne, Roccadaspide, Postiglione, dan Serre . Semua kota yang terletak di wilayah Campania . Castelcivita adalah rumah bagi atraksi wisata yang populer, Grotte di Castelcivita, juga dikenal sebagai Gua Castelcivita . Pranala luar (Italia) Municipal web site (Italia) (Inggris)...

 

VIIIe siècle

Millénaires : Ier millénaire av. J.-C. • Ier millénaire • IIe millénaire Siècles : VIIe siècle • VIIIe siècle • IXe siècle Décennies : 700 • 710 • 720 • 730 • 740 750 • 760 • 770 • 780 • 790 Années : 701 • 702 • 703 • 704 • 705706 • 707 • 708 • 709 • 710 711 • 712 • 713 • 714 • 715716 • 717 • 718 • 719 • 720 721 • 722 • 723 • 724 • 725726 • 727 • 728 ...

Vadão

Vadão Tanggal lahir 21 Agustus 1956 (umur 67)Tempat lahir BrasilKepelatihanTahun Tim 2005 Tokyo Verdy Vadão (lahir 21 Agustus 1956) adalah pemain sepak bola asal Brasil. Pranala luar (Jepang) J. League Data Site Artikel bertopik pemain sepak bola Brasil ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.lbs

 

Rustam Assakalov

Rustam Assakalov Рустам АссакаловAssakalov dalam Pesta Olahraga Asia 2018Informasi pribadiNama lengkapRustam Skhatbievich AssakalovKewarganegaraan Rusia UzbekistanLahir13 Juli 1984 (umur 40)Novorossiysk, RusiaAlma materUniversitas Negeri KubanTinggi188 m (616 ft 10 in)[1] OlahragaNegaraRusia Uzbekistan (sejak 2012)[1]OlahragaGulat Yunani-RomawiKlubDynamo Taskent[2]Dilatih olehVladimir Kholodaev[1]Kamil Fatkulin[2]...

 

WE Charity

Canadian charity Free the Children redirects here. For the book about the free school movement, see Free the Children (book). WE CharityFormation1995TypeInternational charity and educational partnerHeadquartersToronto, Ontario, CanadaFoundersCraig KielburgerMarc KielburgerWebsitewe.orgFormerly calledFree the Children WE Charity (French: Organisme UNIS), formerly known as Free the Children (French: Enfants Entraide), is an international development charity and youth empowerment movement found...

Busan Cinema Center

Movie complex in Busan, South Korea Busan Cinema Center영화의전당Address120 Suyeonggangbyeon-daero, Haeundae-guBusanSouth KoreaOwnerBusan Metropolitan CityOperatorBusan Cinema CenterTypeCinemas, theaters, concert halls, etc.CapacityBIFF Theater: 4,000Haneulyeon Theater: 841Cinema I: 413Cinema II: 212Cinematheque: 212ConstructionOpenedSeptember 29, 2011ArchitectCoop Himmelb(l)auWebsitehttps://www.dureraum.org/bccen/main/main.do Busan Cinema CenterHangul영화의전당Hanja映畫의殿堂R...

 

Six équipes originales de la LNH

Les six équipes originales de la Ligue nationale de hockey (en anglais : The Original Six) est un terme de hockey sur glace qui désigne les six équipes qui forment la LNH de 1942 à 1967. Ces équipes sont les Canadiens de Montréal, les Maple Leafs de Toronto, les Bruins de Boston, les Red Wings de Détroit, les Rangers de New York et les Black Hawks de Chicago. Le terme est trompeur puisque ces équipes ne sont pas celles qui sont présentes à la création de la LNH, en 1917 :...

 

Pavão

Disambiguazione – Se stai cercando il calciatore portoghese, vedi Pavão (calciatore). Questa voce sull'argomento centri abitati del Minas Gerais è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Pavãocomune LocalizzazioneStato Brasile Stato federato Minas Gerais MesoregioneVale do Mucuri MicroregioneTeófilo Otoni AmministrazioneSindacoAntonio Carlos de Almeida Ruas TerritorioCoordinate17°2...

Ubstadt-Weiher

You can help expand this article with text translated from the corresponding article in German. (February 2009) Click [show] for important translation instructions. View a machine-translated version of the German article. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikip...

 

Operation Valuable

Western covert paramilitary operation This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (October 2013) (Learn how and when to remove this message) This article possibly contains original research. Please improve it by v...