國立高雄大學圖資館 |

登入

回首頁

Finding Consistent Answers From Inconsistent Data: Systems, Algorithms, and Complexity.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Finding Consistent Answers From Inconsistent Data: Systems, Algorithms, and Complexity.
作者:	Ouyang, Xiating.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, 2023
面頁冊數:	157 p.
附註:	Source: Dissertations Abstracts International, Volume: 85-06, Section: B.
附註:	Advisor: Koutris, Paraschos.
Contained By:	Dissertations Abstracts International85-06B.
標題:	Computer science.
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30814529
ISBN:	9798381145069

Finding Consistent Answers From Inconsistent Data: Systems, Algorithms, and Complexity.
Ouyang, Xiating.

Finding Consistent Answers From Inconsistent Data: Systems, Algorithms, and Complexity. - Ann Arbor : ProQuest Dissertations & Theses, 2023 - 157 p.

Source: Dissertations Abstracts International, Volume: 85-06, Section: B.

Thesis (Ph.D.)--The University of Wisconsin - Madison, 2023.

This item must not be sold to any third party vendors.

Most data analytical pipelines often encounter the problem of querying inconsistent data that could violate pre-determined integrity constraints. Data cleaning is an extensively studied paradigm that singles out a consistent repair of the inconsistent data. Consistent query answering (CQA) is an alternative approach to data cleaning that asks for all tuples guaranteed to be returned by a given query on all (and in most cases, exponentially many) repairs of the inconsistent data.This dissertation investigates both practical and theoretical perspectives of CQA in the context of relational queries and databases that can possibly violate (and only violate) the primary-key constraints. From a practical standpoint, we identify a class of select-project-join (SPJ) queries for which CQA can be solved via a first-order rewriting with linear time guarantees. This is implemented in a system LinCQA, and we show that LinCQA often outperforms the existing CQA systems on both synthetic and real-world workloads, and in some cases, by orders of magnitude. From a theoretical perspective, this dissertation provides a complexity classification of CQA on representative classes of conjunctive queries with self-joins: path queries, rooted tree queries, and beyond. The classification criterion is explicit and involves query homomorphisms. This advances the current complexity trichotomy result on self-join-free conjunctive queries established in 2015.

ISBN: 9798381145069Subjects--Topical Terms:

199325
Computer science.
Subjects--Index Terms:

Computational complexity

Finding Consistent Answers From Inconsistent Data: Systems, Algorithms, and Complexity.
LDR:02709nmm a2200397 4500 001 655881
005 20240414211956.5
006 m o d
007 cr#unu||||||||
008 240620s2023 ||||||||||||||||| ||eng d
020 $a 9798381145069
035 $a (MiAaPQ)AAI30814529
035 $a AAI30814529
040 $a MiAaPQ $c MiAaPQ
100 1 $a Ouyang, Xiating. $3 967076
245 1 0 $a Finding Consistent Answers From Inconsistent Data: Systems, Algorithms, and Complexity.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2023
300 $a 157 p.
500 $a Source: Dissertations Abstracts International, Volume: 85-06, Section: B.
500 $a Advisor: Koutris, Paraschos.
502 $a Thesis (Ph.D.)--The University of Wisconsin - Madison, 2023.
506 $a This item must not be sold to any third party vendors.
520 $a Most data analytical pipelines often encounter the problem of querying inconsistent data that could violate pre-determined integrity constraints. Data cleaning is an extensively studied paradigm that singles out a consistent repair of the inconsistent data. Consistent query answering (CQA) is an alternative approach to data cleaning that asks for all tuples guaranteed to be returned by a given query on all (and in most cases, exponentially many) repairs of the inconsistent data.This dissertation investigates both practical and theoretical perspectives of CQA in the context of relational queries and databases that can possibly violate (and only violate) the primary-key constraints. From a practical standpoint, we identify a class of select-project-join (SPJ) queries for which CQA can be solved via a first-order rewriting with linear time guarantees. This is implemented in a system LinCQA, and we show that LinCQA often outperforms the existing CQA systems on both synthetic and real-world workloads, and in some cases, by orders of magnitude. From a theoretical perspective, this dissertation provides a complexity classification of CQA on representative classes of conjunctive queries with self-joins: path queries, rooted tree queries, and beyond. The classification criterion is explicit and involves query homomorphisms. This advances the current complexity trichotomy result on self-join-free conjunctive queries established in 2015.
590 $a School code: 0262.
650 4 $a Computer science. $3 199325
650 4 $a Information technology. $3 184390
653 $a Computational complexity
653 $a Consistent query answering
653 $a Databases
653 $a Inconsistent data
653 $a Data cleaning
690 $a 0984
690 $a 0489
690 $a 0800
710 2 $a The University of Wisconsin - Madison. $b Computer Sciences. $3 708692
773 0 $t Dissertations Abstracts International $g 85-06B.
790 $a 0262
791 $a Ph.D.
792 $a 2023
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30814529