國立虎尾科技大學 |

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

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Finding Consistent Answers From Inconsistent Data :/
Reminder of title:	Systems, Algorithms, and Complexity.
Author:	Ouyang, Xiating.
Description:	1 online resource (157 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 85-06, Section: B.
Contained By:	Dissertations Abstracts International85-06B.
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9798381145069

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

Finding Consistent Answers From Inconsistent Data :Systems, Algorithms, and Complexity. - 1 online resource (157 pages)

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

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

Includes bibliographical references

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.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798381145069Subjects--Topical Terms:

573171
Computer science.
Subjects--Index Terms:

Computational complexityIndex Terms--Genre/Form:

554714
Electronic books.

Finding Consistent Answers From Inconsistent Data : = Systems, Algorithms, and Complexity.
LDR:02865ntm a22003977 4500 001 1142140
005 20240414211956.5
006 m o d
007 cr mn ---uuuuu
008 250605s2023 xx obm 000 0 eng d
020 $a 9798381145069
035 $a (MiAaPQ)AAI30814529
035 $a AAI30814529
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Ouyang, Xiating. $3 1466350
245 1 0 $a Finding Consistent Answers From Inconsistent Data : $b Systems, Algorithms, and Complexity.
264 0 $c 2023
300 $a 1 online resource (157 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
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.
504 $a Includes bibliographical references
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.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
650 4 $a Information technology. $3 559429
653 $a Computational complexity
653 $a Consistent query answering
653 $a Databases
653 $a Inconsistent data
653 $a Data cleaning
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0489
690 $a 0800
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a The University of Wisconsin - Madison. $b Computer Sciences. $3 1179878
773 0 $t Dissertations Abstracts International $g 85-06B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30814529 $z click for full text (PQDT)