Agreement graphs and data dependencies

dc.contributor.advisor Giora Slutzki Leuchner, John
dc.contributor.department Computer Science 2018-08-16T03:46:12.000 2020-07-02T06:09:13Z 2020-07-02T06:09:13Z Fri Jan 01 00:00:00 UTC 1988 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/
dc.identifier.articleid 9786
dc.identifier.contextkey 6344056
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath rtd/8787
dc.language.iso en
dc.source.bitstream archive/|||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 dissertation Doctor of Philosophy
Original bundle
Now showing 1 - 1 of 1
2.06 MB
Adobe Portable Document Format