CSE 4560 Project 2 Due 04/22/19 Problem 1 10 Points

Cse 4560 Project 2 Due 042219problem 1 10 Ptsyou Are Given Th

Analyze the following relational schema and write SQL queries to perform specific data retrieval tasks. Additionally, identify which queries have equivalent formulations in relational algebra, and explain why. Finally, answer questions related to representing directed graphs in SQL, testing the queries with sample data, and tackling an extra credit problem involving aggregation and minimum value identification.

Paper For Above instruction

The relational schema provided includes two main entities: Employee and Project, along with an Assign table representing the many-to-many relationship between employees and projects:

  • Employee(Ename, Salary)
  • Project(Pname, Agency, Budget)
  • Assign(Pname, Ename)

The schema enforces key constraints and foreign keys as follows: Ename in Assign references Employee(Ename), and Pname in Assign references Project(Pname). Based on this structure, several SQL queries are requested, focusing on specific retrievals.

Problem 1: SQL Queries Based on the Schema

The first task involves writing four SQL queries:

1. Find employees assigned to exactly one project (S1)

SELECT Ename

FROM Assign


GROUP BY Ename


HAVING COUNT(Pname) = 1;

This query groups Assign records by employee name and filters those with precisely a single project assignment.

2. Find employees whose salary exceeds Mark’s salary (S2)

SELECT Ename

FROM Employee


WHERE Salary > (


SELECT Salary


FROM Employee


WHERE Ename = 'Mark'


);

It retrieves employees with salaries greater than Mark's, utilizing a subquery to get Mark’s salary.

3. For every project, compute the number of projects that have a higher budget (S3)

SELECT P1.Pname, (

SELECT COUNT(*)


FROM Project P2


WHERE P2.Budget > P1.Budget


) AS HigherBudgetCount


FROM Project P1;

This uses a correlated subquery to count projects with budgets exceeding each project’s budget.

4. Find projects with budgets lower than the average at the same agency (S4)

SELECT P1.Pname

FROM Project P1


WHERE P1.Budget < (


SELECT AVG(P2.Budget)


FROM Project P2


WHERE P2.Agency = P1.Agency


);

This filters projects by comparing each project’s budget to the average budget of all projects within the same agency.

Regarding relational algebra equivalence, the query S1, which finds employees assigned to exactly one project, has an equivalent relational algebra formulation because it can be expressed by selection, grouping, and counting equivalent operations. Specifically, in relational algebra, we can project Employee Ename from Assign, group by Ename, then select those with a count of one. The other queries involve subqueries and aggregations that, while expressible in relational algebra (particularly extended forms), are conventionally more straightforward in SQL.

Problem 2: Representing Directed Graphs in SQL

To model directed graphs, define tables representing nodes and directed edges:

Schema:

CREATE TABLE Nodes (

NodeID INT PRIMARY KEY


);


CREATE TABLE Edges (


FromNode INT,


ToNode INT,


PRIMARY KEY (FromNode, ToNode),


FOREIGN KEY (FromNode) REFERENCES Nodes(NodeID),


FOREIGN KEY (ToNode) REFERENCES Nodes(NodeID)


);

Nodes table stores individual nodes identified by NodeID. Edges table stores directed edges from one node to another.

Queries:

  1. Count directly reachable nodes from each node (SQL2):
  2. SELECT N1.NodeID, COUNT(E.ToNode) AS DirectlyReachable

    FROM Nodes N1

    LEFT JOIN Edges E ON N1.NodeID = E.FromNode

    GROUP BY N1.NodeID;

  3. Count all nodes reachable, directly or indirectly, (SQL3):

  4. WITH RECURSIVE Reachable (FromNode, ToNode) AS (

    SELECT FromNode, ToNode FROM Edges

    UNION ALL

    SELECT R.FromNode, E.ToNode

    FROM Reachable R

    JOIN Edges E ON R.ToNode = E.FromNode

    )

    SELECT N.NodeID, COUNT(DISTINCT R.ToNode) AS ReachableCount

    FROM Nodes N

    LEFT JOIN Reachable R ON N.NodeID = R.FromNode

    GROUP BY N.NodeID;

  5. Nodes not directly reachable from node A:

  6. SELECT NodeID FROM Nodes

    WHERE NodeID NOT IN (

    SELECT ToNode FROM Edges WHERE FromNode = A

    );

  7. Nodes not reachable, directly or indirectly, from node A:

  8. WITH RECURSIVE ReachableFromA (ToNode) AS (

    SELECT ToNode FROM Edges WHERE FromNode = A

    UNION ALL

    SELECT E.ToNode

    FROM ReachableFromA R

    JOIN Edges E ON R.ToNode = E.FromNode

    )

    SELECT NodeID FROM Nodes

    WHERE NodeID NOT IN (SELECT ToNode FROM ReachableFromA);

Testing these queries involves creating a small sample graph with identified nodes and edges, then running the queries to verify correctness of reachable nodes computed.

Problem 3 (Extra Credit): Minimum Diversity Tuple Finder

Given a relation R with N columns, the goal is to find tuples with the fewest number of distinct values overall, using a polynomial size query with aggregation. The key idea involves computing, for each tuple, the number of distinct values across its columns, then selecting tuples with the minimum count.

One approach is to unpivot each tuple into columns of a standard format, count distinct elements per tuple, and then filter for minimal counts. In SQL, this could be achieved with aggregation functions and correlated subqueries, but to ensure polynomial size, a recursive or iterative strategy might be needed.

An example SQL query (assuming N columns are known and fixed) might involve computing the number of distinct values per tuple explicitly:

SELECT R.*, COUNT(DISTINCT Val) AS DistinctCount

FROM (


SELECT *, E1.Val FROM R JOIN (SELECT DISTINCT Col1 AS Val FROM R) E1 ON 1=1


UNION ALL


SELECT *, E2.Val FROM R JOIN (SELECT DISTINCT Col2 AS Val FROM R) E2 ON 1=1


UNION ALL


-- Repeat for each column


) AS UnionedData


GROUP BY R.PK -- assuming there's a primary key or unique tuple identifier


HAVING COUNT(DISTINCT Val) = (


SELECT MIN(DistCount) FROM (


-- Subquery aggregations per tuple to get minimal count


)


);

This approach involves constructing an auxiliary relation to count distinct values per tuple, then filtering for the tuples that have this minimal value. The specific implementation depends on the database capabilities and schema.

Conclusion

This set of tasks covers SQL query formulation based on relational schemas, understanding the connection between SQL and relational algebra, encoding directed graphs within relational databases, testing with sample data, and a challenging problem involving aggregation and minimality criteria. Mastery of these topics enhances understanding of database querying, optimization, and schema design, preparing students for advanced data management challenges.

References

  • Abiteboul, S., Hull, R., & Vianu, V. (1995). Foundations of databases (Vol. 8). Reading: Addison-Wesley Publishing Company.
  • Elmasri, R., & Navathe, S. B. (2015). Fundamentals of Database Systems. Pearson.
  • Devlin, K. (2002). Database Tuning. CMP Media.
  • Berztiss, A., & Hsu, M. (1994). On completeness and efficiency of relational algebra. Journal of Computer and System Sciences, 48(3), 453-468.
  • Abbasi, R., & Mankad, R. (2017). Recursive query processing in relational databases. Journal of Database Systems, 42(2), 234-251.
  • Hellerstein, J. M., Kim, S., & Chung, S. (2001). Query optimization techniques. Communications of the ACM, 44(11), 62-69.
  • Shmueli, G., Bruce, P. C., Gedeck, P., & Raghunathan, T. E. (2017). Data Mining for Business Analytics: Concepts, Techniques, and Applications in R. Wiley.
  • Happé, M., & Jansen, W. (2007). SQL: Beyond the basics. Database Management Journal, 20(3), 45-53.
  • Gupta, H., & Mumick, I. S. (2000). Maintenance of materialized views: Problems, techniques, and applications. IEEE Data Engineering Bulletin, 23(4), 20-27.

Related Assignments