Agreement graphs and data dependencies

dc.contributor.advisor Giora Slutzki
dc.contributor.author Leuchner, John
dc.contributor.department Computer Science
dc.date 2018-08-16T03:46:12.000
dc.date.accessioned 2020-07-02T06:09:13Z
dc.date.available 2020-07-02T06:09:13Z
dc.date.copyright Fri Jan 01 00:00:00 UTC 1988
dc.date.issued 1988
dc.description.abstract <p>The problem of deciding whether a join dependency [R] and a set F of functional dependencies logically imply an embedded join dependency [S] is known to be NP-complete. It is shown that if the set F of functional dependencies is required to be embedded in R, the problem can be decided in polynomial time. The problem is approached by introducing agreement graphs, a type of graph structure which helps expose the combinatorial structure of dependency implication problems. Agreement graphs provide an alternative formalism to tableaus and extend the application of graph and hypergraph theory in relational database research;Agreement graphs are also given a more abstract definition and are used to define agreement graph dependencies (AGDs). It is shown that AGDs are equivalent to Fagin's (unirelational) embedded implicational dependencies. A decision method is given for the AGD implication problem. Although the implication problem for AGDs is undecidable, the decision method works in many cases and lends insight into dependency implication. A number of properties of agreement graph dependencies are given and directions for future research are suggested.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/rtd/8787/
dc.identifier.articleid 9786
dc.identifier.contextkey 6344056
dc.identifier.doi https://doi.org/10.31274/rtd-180813-12857
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath rtd/8787
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/81813
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/rtd/8787/r_8825938.pdf|||Sat Jan 15 02:16:38 UTC 2022
dc.subject.disciplines Computer Sciences
dc.subject.keywords Computer science
dc.title Agreement graphs and data dependencies
dc.type article
dc.type.genre dissertation
dspace.entity.type Publication
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456
thesis.degree.level dissertation
thesis.degree.name Doctor of Philosophy
File
Original bundle
Now showing 1 - 1 of 1
Name:
r_8825938.pdf
Size:
2.06 MB
Format:
Adobe Portable Document Format
Description: