RelationAnalyzer.java
/*
** Module : RelationAnalyzer.java
** Abstract : Analyzes natural relations between database table pairs
**
** Copyright (c) 2005-2023, Golden Code Development Corporation.
**
** -#- -I- --Date-- --JPRM-- -----------------------------------Description-----------------------------------
** 001 ECF 20050325 @20997 Created initial version. Detects natural join
** relations between two database tables in a
** Progress schema. Capable of scanning a schema
** and reporting all potential relations.
** 002 ECF 20050623 @21606 Minor fix to support change in schema AST
** structure. The unique designation for an
** index was moved from a descendant node to an
** annotation.
** 003 ECF 20051005 @22982 Back out #002 (@21606). Side effect of schema
** fixups ruleset change.
** 004 ECF 20081216 @40937 Fixed findJoiningIndex(). This method did not
** properly handle temp-table indexes, which can
** have multiple PROPERTIES tags.
** 005 GES 20090518 @42399 Import change.
** 006 ECF 20131013 Added new type of relation analysis for metadata tables. Implemented
** generics.
** 007 ECF 20131215 Fixed metadata table relation analysis.
** 008 TJD 20220504 Java 11 compatibility minor changes
** 009 GBB 20230512 Logging methods replaced by CentralLogger/ConversionStatus.
** 010 OM 20230630 Added support for the newly observed PARENT_ID_RELATION between joined tables.
*/
/*
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU Affero General Public License as
** published by the Free Software Foundation, either version 3 of the
** License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU Affero General Public License for more details.
**
** You may find a copy of the GNU Affero GPL version 3 at the following
** location: https://www.gnu.org/licenses/agpl-3.0.en.html
**
** Additional terms under GNU Affero GPL version 3 section 7:
**
** Under Section 7 of the GNU Affero GPL version 3, the following additional
** terms apply to the works covered under the License. These additional terms
** are non-permissive additional terms allowed under Section 7 of the GNU
** Affero GPL version 3 and may not be removed by you.
**
** 0. Attribution Requirement.
**
** You must preserve all legal notices or author attributions in the covered
** work or Appropriate Legal Notices displayed by works containing the covered
** work. You may not remove from the covered work any author or developer
** credit already included within the covered work.
**
** 1. No License To Use Trademarks.
**
** This license does not grant any license or rights to use the trademarks
** Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
** of Golden Code Development Corporation. You are not authorized to use the
** name Golden Code, FWD, or the names of any author or contributor, for
** publicity purposes without written authorization.
**
** 2. No Misrepresentation of Affiliation.
**
** You may not represent yourself as Golden Code Development Corporation or FWD.
**
** You may not represent yourself for publicity purposes as associated with
** Golden Code Development Corporation, FWD, or any author or contributor to
** the covered work, without written authorization.
**
** 3. No Misrepresentation of Source or Origin.
**
** You may not represent the covered work as solely your work. All modified
** versions of the covered work must be marked in a reasonable way to make it
** clear that the modified work is not originating from Golden Code Development
** Corporation or FWD. All modified versions must contain the notices of
** attribution required in this license.
*/
package com.goldencode.p2j.schema;
import java.util.*;
import java.util.logging.*;
import com.goldencode.ast.*;
import com.goldencode.p2j.cfg.*;
import com.goldencode.p2j.convert.*;
/**
* Examines implicit relations between database tables following Progress
* rules for table joins. Specifically:
* <ul>
* <li>the tables must have between them one or more field with a common name
* and data type;
* <li>the common field(s) must participate in a unique index in at least
* one of the tables;
* <li>only one such relationship between the two tables is allowed.
* </ul>
*
* Note that this definition only covers <em>natural joins</em> between
* tables which would be analagous to primary-foreign key relations in a
* relational database. Explicit joins which do not follow the rules above
* are certainly possible in Progress source code, where any fields of the
* same data type in two tables can be used as an ad-hoc relation in a
* query. The analysis performed by this class <em>does not</em> cover
* these types of ad-hoc joins.
*/
class RelationAnalyzer
implements SchemaParserTokenTypes
{
/** Logger */
private static final ConversionStatus LOG = ConversionStatus.get(RelationAnalyzer.class);
/** Names of metadata tables involved in conversion */
private Set<String> metaTables;
/** Schema dictionary which is consulted for schema information */
private SchemaDictionary dictionary = null;
/**
* Constructor which accepts the schema dictionary to consult for schema
* information while analyzing relations.
*
* @param dictionary
* Schema dictionary.
*/
RelationAnalyzer(SchemaDictionary dictionary)
{
this.dictionary = dictionary;
this.metaTables = Configuration.getSchemaConfig().getMetadata().getTables();
}
/**
* Get a list of trees, each of which is composed of {@link RelationNode}
* objects. The root of each tree represents a Progress database table
* which has no dependencies on any other table. The children of each
* node represent tables which each have a foreign key relation to the
* parent node's table. Note that the nodes within each tree may be
* duplicated across trees.
*
* @param joins
* A set of {@link TableRelation} objects that each represent a
* natural join between a pair of Progress tables.
*
* @return List of relation node trees as described above.
*/
List<RelationNode> analyze(Set<TableRelation> joins)
{
Map<Aast, Collection<TableRelation>> nodeMap =
new LinkedHashMap<Aast, Collection<TableRelation>>();
Set<Aast> foreigns = new HashSet<Aast>();
Iterator<TableRelation> iter = joins.iterator();
while (iter.hasNext())
{
TableRelation relation = iter.next();
Aast primary = relation.getPrimary();
if (primary == null)
{
LOG.log(Level.WARNING, "Ambiguous relation: " + relation);
continue;
}
Collection<TableRelation> nodes = nodeMap.get(primary);
if (nodes == null)
{
nodes = new ArrayList<TableRelation>();
}
nodes.add(relation);
foreigns.add(relation.getRight());
nodeMap.put(primary, nodes);
}
ArrayList<RelationNode> roots = new ArrayList<RelationNode>();
Iterator<Aast> iter2 = nodeMap.keySet().iterator();
while (iter2.hasNext())
{
Aast next = iter2.next();
if (!foreigns.contains(next))
{
RelationNode root = createTree(nodeMap, next, null);
roots.add(root);
}
}
roots.trimToSize();
return roots;
}
/**
* Debug method to dump to <code>stdout</code> the hierarchy of relations
* defined by <code>node</code>.
*
* @param node
* Starting node for the tree dump. Descendent nodes are walked
* recursively.
*/
void dumpTree(RelationNode node)
{
Iterator<RelationNode> iter = (Iterator<RelationNode>) node.descendantsIterator();
while (iter.hasNext())
{
RelationNode next = iter.next();
System.out.println(next.toString());
}
}
/**
* Get a set of all <em>potential</em> {@linkplain TableRelation natural
* relations} between two tables, based upon the schema data only (not on
* references within source code).
*
* @param database
* Name of database to scan for potential relations.
*
* @return Set of all potential, natural table relations.
*/
Set<TableRelation> getAllRelations(String database)
{
List<Aast> list = new LinkedList<>();
Set<TableRelation> set = new TreeSet<>();
Set<String> noJoins = new TreeSet<>();
Set<Aast> rights = new HashSet<>();
// Get initial list of tables.
Iterator<Aast> iter = dictionary.tables(database);
while (iter.hasNext())
{
list.add(iter.next());
}
Iterator<Aast> iter2 = list.iterator();
while (iter2.hasNext())
{
Aast left = iter2.next();
iter2.remove();
boolean hit = false;
Iterator<Aast> iter3 = list.iterator();
while (iter3.hasNext())
{
Aast right = iter3.next();
TableRelation join = attemptNaturalJoin(left, right);
if (join != null)
{
set.add(join);
hit = true;
rights.add(right);
}
}
if (!hit && !rights.contains(left))
{
noJoins.add(left.getText());
}
}
System.out.println("NO RELATIONS:");
System.out.println("-------------");
Iterator<String> iter4 = noJoins.iterator();
while (iter4.hasNext())
{
String next = iter4.next();
System.out.println("No potential relations for table: " + next);
}
return set;
}
/**
* Create a table relation object which describes the <em>natural
* join</em> relation between two tables. Such a relation is defined by
* the two tables having at least one field of a common name and data
* type, which participates in a unique index in one of the tables.
* <p>
* Although there is no concept of primary and foreign keys in Progress,
* we determine, if possible, how the two tables in a natural join would
* fall into these categories. If only one of the two tables has an index
* which meets the requirement defined above, that table is considered
* the "primary" end of the natural join; the other table is considered
* the "foreign" end. If both tables contain an index which meets the
* requirement, it is ambiguous as to how the tables can be mapped into
* a primary-foreign key relationship with one another.
*
* @param left
* The left-hand table in the potential join.
* @param right
* The right-hand table in the potential join.
*
* @return The table relation object which defines the possible, natural
* relation between the two tables.
*
* @throws SchemaException
* if a natural join of the two tables is not possible.
*/
TableRelation createJoin(String left, String right)
throws SchemaException
{
Aast t1 = dictionary.getTable(left);
Aast t2 = dictionary.getTable(right);
TableRelation join = attemptNaturalJoin(t1, t2);
if (join == null)
{
// try parent-recid relation, except for temp-tables
join = attemptParentIdJoin(t1, t2);
if (join == null)
{
throw new SchemaException("Invalid join: " + left + " of " + right);
}
}
return join;
}
/**
* Attempt to determine a potential, <em>parent-id join</em> between the two tables specified. For such a
* join to be possible, none of the tables should be temporary, and the child table must have a RECID
* field whose name has the following pattern {@code <parent-table-name>-recid[<suffix>]}. if there are
* multiple fields with this naming schema, the one with shorter suffix is chosen, best match being when
* the suffix is empty/missing.
*
* @param t1
* The left-hand (parent) table in the potential join.
* @param t2
* The right-hand (child) table in the potential join.
*
* @return The table relation object which defines the possible, parent-id relation between the two tables,
* or {@code null} if no such relation is possible.
*/
private TableRelation attemptParentIdJoin(Aast t1, Aast t2)
{
if (false || (t1.getType() == TEMP_TABLE || t2.getType() == TEMP_TABLE))
{
return null;
}
String parentRecidPattern = t1.getText().toLowerCase() + "-recid";
Aast childField = (Aast) t2.getFirstChild();
Aast bestCandidate = null; // this will be used when multiple fields have [parentRecidPattern] as prefix
while (childField != null)
{
if (childField.getType() == FIELD_RECID)
{
String childFieldName = childField.getText().toLowerCase();
if (childFieldName.equals(parentRecidPattern))
{
// found /parent-recid/ field
return new TableRelation(t1,
t2,
t1,
new HashSet<>(Collections.singleton(childField.getText())),
PARENT_ID_RELATION);
}
if (childFieldName.startsWith(parentRecidPattern) &&
(bestCandidate == null || bestCandidate.getText().compareTo(childField.getText()) > 0))
{
bestCandidate = childField;
}
}
childField = (Aast) childField.getNextSibling();
}
if (bestCandidate != null)
{
// use the best candidate for /parent-recid/ field
return new TableRelation(t1,
t2,
t1,
new HashSet<>(Collections.singleton(bestCandidate.getText())),
PARENT_ID_RELATION);
}
return null;
}
/**
* Attempt to determine a potential, <em>natural join</em> between the
* two tables specified. For a natural join to be possible, the tables
* must both define at least one field with the same name and data type,
* which participates in a unique index in at least one of the
* tables. More than one field may meet these criteria. Only one index
* per table may meet these criteria, but that restriction is not
* enforced here.
* <p>
* Alternatively, if the tables are metadata tables, attempt to determine
* a primary-foreign key join.
* <p>
* Although there is no concept of primary and foreign keys in Progress,
* we determine, if possible, how the two tables in a natural join would
* fall into these categories. If only one of the two tables has an index
* which meets the requirement defined above, that table is considered
* the "primary" end of the natural join; the other table is considered
* the "foreign" end. If both tables contain an index which meets the
* requirement, it is ambiguous as to how the tables can be mapped into
* a primary-foreign key relationship with one another.
*
* @param left
* The left-hand table in the potential join.
* @param right
* The right-hand table in the potential join.
*
* @return The table relation object which defines the possible, natural relation between the two tables,
* or {@code null} if no such relation is possible.
*/
private TableRelation attemptNaturalJoin(Aast left, Aast right)
{
TableRelation join = attemptMetaJoin(left, right);
if (join != null)
{
return join;
}
Map<String, Integer> common = getCommonFields(left, right);
if (common.isEmpty())
{
return null;
}
// Of the common fields, at least one must be part of a unique index.
// If said index is multi-field, all fields in the index must
// participate in the relation.
Aast index1 = findJoiningIndex(left, common);
Aast index2 = findJoiningIndex(right, common);
if (index1 != null && index2 == null)
{
// The left table contains the primary key.
Set<String> key = getIndexFieldNames(index1);
join = new TableRelation(left, right, left, key, MANY_TO_ONE);
}
else if (index1 == null && index2 != null)
{
// The right table contains the primary key.
Set<String> key = getIndexFieldNames(index2);
join = new TableRelation(left, right, right, key, MANY_TO_ONE);
}
else if (index1 != null && index2 != null)
{
// In this case, both tables had a unique index containing one or
// more common fields. Must analyze further...
Set<String> set1 = getIndexFieldNames(index1);
Set<String> set2 = getIndexFieldNames(index2);
Set<String> commonKeys = common.keySet();
commonKeys.retainAll(set1);
commonKeys.retainAll(set2);
Aast primary = null;
boolean match1 = (set1.equals(commonKeys));
boolean match2 = (set2.equals(commonKeys));
int type = -1;
if (match1 && !match2)
{
primary = left;
type = MANY_TO_ONE;
}
else if (!match1 && match2)
{
primary = right;
type = MANY_TO_ONE;
}
else if (match1 && match2)
{
type = ONE_TO_ONE;
}
else
{
// It is ambiguous which end represents the primary and which
// the foreign end of this relation. Probably requires manual
// inspection and a hint.
String msg = "Cannot determine join type: " + join + System.lineSeparator() +
" " + left.getText() + " matching index: " + set1 + System.lineSeparator() +
" " + right.getText() + " matching index: " + set2;
LOG.log(Level.SEVERE, msg);
}
if (type != -1 && !common.isEmpty())
{
join = new TableRelation(left, right, primary, commonKeys, type);
}
}
return join;
}
/**
* Attempt to determine a primary-foreign key join between two metadata tables.
*
* @param left
* Table on the left side of the join.
* @param right
* Table on the right side of the join.
*
* @return A <code>TableRelation</code> instance, if a join exists, else <code>null</code>.
*/
private TableRelation attemptMetaJoin(Aast left, Aast right)
{
String leftName = left.getText().toLowerCase();
String rightName = right.getText().toLowerCase();
if (!metaTables.contains(leftName) || !metaTables.contains(rightName))
{
return null;
}
String fkField = null;
int len1 = rightName.length();
int len2 = "-recid".length();
Iterator<Aast> iter = dictionary.fields(left);
while (iter.hasNext())
{
Aast next = iter.next();
if (next.getType() == FIELD_RECID)
{
String fieldName = next.getText().toLowerCase();
int p1 = fieldName.indexOf(rightName);
int p2 = fieldName.indexOf("-recid");
if (p1 == 0 && p2 == len1 && fieldName.length() == (p2 + len2))
{
fkField = next.getText().toLowerCase();
break;
}
}
}
MetaTableRelation join = null;
if (fkField != null)
{
Set<String> key = new HashSet<String>();
key.add(fkField);
join = new MetaTableRelation(left, right, key);
}
return join;
}
/**
* Compose a map of field names to field token types for the given table.
* The keys (field names) are lowercased for uniformity. Iteration over
* the key set will return field names in the order in which they were
* added to the table AST.
*
* @param table
* AST of the table to scan for fields when composing the map.
*
* @return Map of field names to field token types.
*/
private Map<String, Integer> getFieldMap(Aast table)
{
Map<String, Integer> map = new LinkedHashMap<String, Integer>();
Iterator<Aast> iter = dictionary.fields(table);
while (iter.hasNext())
{
Aast next = iter.next();
map.put(next.getText().toLowerCase(), Integer.valueOf(next.getType()));
}
return map;
}
/**
* Compose a map of field names to field token types which represents the
* intersection of the fields (by name and token type) of the two tables
* specified. These fields represent the possible, <em>natural</em> join
* points between the two tables. Field names are compared without regard
* to case when determining the intersection.
*
* @param left
* The left-hand table of a two-table join.
* @param right
* The right-hand table of a two-table join.
*
* @return The map of fields which are common between the two tables.
*/
private Map<String, Integer> getCommonFields(Aast left, Aast right)
{
// Get the intersection of field names.
Map<String, Integer> mapLeft = getFieldMap(left);
Map<String, Integer> mapRight = getFieldMap(right);
Set<String> set = mapLeft.keySet();
set.retainAll(mapRight.keySet());
// Check that each remaining field's type matches.
Iterator<String> iter = set.iterator();
while (iter.hasNext())
{
String next = iter.next();
Integer type1 = mapLeft.get(next);
Integer type2 = mapRight.get(next);
if (!type1.equals(type2))
{
iter.remove();
}
}
return mapLeft;
}
/**
* Compose a set of the names of all fields defined for the given index.
* Names are lowercased for uniformity.
*
* @param index
* Index whose fields are to be included in the set.
*
* @return Set of index field names.
*/
private Set<String> getIndexFieldNames(Aast index)
{
Set<String> set = new LinkedHashSet<String>();
String tableName = index.getParent().getText();
Aast next = index.getImmediateChild(INDEX_FIELD, null);
while (next != null)
{
set.add(next.getText().toLowerCase());
next = index.getImmediateChild(INDEX_FIELD, next);
}
return set;
}
/**
* Given a table AST and a map of fields which this table has in common
* (by name and type) with another table, find the index which can be
* used to join this table with the other. The index must be unique and
* must contain only fields which are in the common map. There should
* be only one such index in the table, but this restriction is not
* enforced here; once a suitable index is found, it is returned.
*
* @param table
* AST of table to be searched for a suitable index.
* @param common
* Map of field ASTs which the given table has in common with
* another table.
*
* @return AST of the unique index (from the schema dictionary) which
* defines the join between this table and another, based upon
* fields described by <code>common</code>, or <code>null</code>
* if no such index is found.
*/
private Aast findJoiningIndex(Aast table, Map<String, Integer> common)
{
Aast index = null;
Iterator<Aast> iter = dictionary.indices(table);
while (index == null && iter.hasNext())
{
Aast next = iter.next();
boolean unique = false;
Aast props = next.getImmediateChild(PROPERTIES, null);
while (!unique && props != null)
{
unique = (props.getImmediateChild(KW_UNIQUE, null) != null);
props = next.getImmediateChild(PROPERTIES, props);
}
if (!unique)
{
continue;
}
Aast field = next.getImmediateChild(INDEX_FIELD, null);
boolean canJoin = (field != null);
while (canJoin && field != null)
{
String name = field.getText().toLowerCase();
field = next.getImmediateChild(INDEX_FIELD, field);
canJoin = common.containsKey(name);
}
if (canJoin)
{
index = next;
}
}
return index;
}
/**
* Recursively create a tree which defines relation dependencies. The
* root of the tree has no primary key dependencies. Each child node
* has a foreign key dependency on its parent.
*
* @param nodeMap
* Map of table ASTs to collections of table join objects.
* @param table
* The table which represents the current node in the tree
* being built.
* @param keyFields
* Set of field names which define the relation between this
* table and its parent.
*
* @return A {@link RelationNode} object which represents the current
* table. Its parent is its dependency and its children are its
* dependents.
*/
private RelationNode createTree(Map<Aast, Collection<TableRelation>> nodeMap,
Aast table,
Collection<String> keyFields)
{
RelationNode node = new RelationNode(table, keyFields);
Collection<TableRelation> relations = nodeMap.get(table);
if (relations != null)
{
Iterator<TableRelation> iter = relations.iterator();
while (iter.hasNext())
{
TableRelation join = iter.next();
Aast foreign = join.getRight();
Collection<String> key = join.getKey();
RelationNode child = createTree(nodeMap, foreign, key);
node.addChild(child);
}
}
return node;
}
/**
* Test driver which analyzes all potential, natural relations between
* every possible pair of tables in a given database. The (possibly
* very large) tree is dumped to the console.
*
* @param args
* Command line arguments. One argument is expected: the logical
* name of the database to analyze.
*/
public static void main(String[] args)
{
try
{
String database = args[0];
SchemaDictionary dictionary = new SchemaDictionary(database);
RelationAnalyzer analyzer = new RelationAnalyzer(dictionary);
Set<TableRelation> set = analyzer.getAllRelations(database);
List<RelationNode> roots = analyzer.analyze(set);
Iterator<RelationNode> iter = roots.iterator();
while (iter.hasNext())
{
analyzer.dumpTree(iter.next());
}
}
catch (Exception exc)
{
LOG.log(Level.SEVERE, "", exc);
}
}
}