SQL Antipattern #2
نویسنده: سید مرتضی حسینی
تاریخ: ۱۳۹۳/۰۴/۳۰ ۱۳:۲۵
آدرس: www.dntips.ir
| مطالب | ۳۶۹۴ |
| نویسندگان | ۲۷۶ |
| گروههای مطالب | ۱۰۲۴ |
| نقشههای راه | ۱۱۹ |
| دورهها | ۱۴ |
| اشتراکها | ۱۷۹۱۴ |
فرض کنید یک وب سایت حرفهای خبری یا علمی-پژوهشی داریم که قابلیت دریافت نظرات کاربران را در مورد هر مطلب مندرج در سایت یا نظرات داده شده در مورد آن مطالب را دارا میباشد. یعنی هر کاربر علاوه بر توانایی اظهار نظر در مورد یک خبر یا مطلب باید بتواند پاسخ نظرات کاربران دیگر را نیز بدهد. اولین راه حلی که برای طراحی این مطلب در پایگاه داده به ذهن ما میرسد، ایجاد یک زنجیره با استفاده از کد sql زیر میباشد:
CREATE TABLE Comments ( comment_idSERIAL PRIMARY KEY, parent_idBIGINT UNSIGNED, comment TEXT NOT NULL, FOREIGN KEY (parent_id) REFERENCES Comments(comment_id) );
البته همان طور که پیداست بازیابی زنجیرهای از پاسخها در یک پرسوجوی sql کار سختی است. این نخها معمولا عمق نامحدودی دارند و برای به دست آوردن تمام نخهای یک زنجیره باید پرسوجوهای زیادی را اجرا نمود.
ایدهی دیگر میتواند بازیابی تمام نظرها و ذخیرهی آنها در حافظهی برنامه به صورت درخت باشد. ولی این روش برای ذخیره هزاران نظری که ممکن است در سایت ثبت شود و علاوه بر آن مقالات جدیدی که اضافه میشوند، تقریبا غیرعملی است.
1.2 هدف: ذخیره و ایجاد پرسوجو در سلسلهمراتب
وجود سلسله مراتب بین دادهها امری عادی محسوب میگردد. در ساختار دادهای درختی هر ورودی یک گره محسوب میگردد. یک گره ممکن است تعدادی فرزند و یک پدر داشته باشد. گره اول پدر ندارد، ریشه و گره فرزند که فرزند ندارد، برگ و گرهای دیگر، گرههای غیربرگ نامیده میشوند.
مثالهایی که از ساختار درختی دادهها وجود دارد شامل موارد زیر است:
Organizational chart: در این ساختار برای مثال در ارتباط بین کارمندان و مدیر، هر کارمند یک مدیر دارد که نشاندهندهی پدر یک کارمند در ساختار درختی است. هر مدیر هم یک کارمند محسوب میگردد.
Threaded discussion: در این ساختار برای مثال در سیستم نظردهی و پاسخها، ممکن است زنجیرهای از نظرات در پاسخ به نظرات دیگر استفاده گردد. در درخت، فرزندان یک گرهی نظر، پاسخهای آن گره هستند.
در این فصل ما از مثال ساختار دوم برای نشان دادن Antipattern و راه حل آن بهره میگیریم.
2.2 Antipattern : همیشه مبتنی بر یکی از والدین
راه حل ابتدایی و ناکارآمد
اضافه نمودن ستون parent_id . این ستون، به ستون نظر در همان جدول ارجاع داده میشود و شما میتوانید برای اجرای این رابطه از قید کلید خارجی استفاده نمایید. پرسوجویی که برای ساخت مثالی که ما در این بحث از آن استفاده میکنیم در ادامه آمده است:
CREATE TABLE Comments ( comment_idSERIAL PRIMARY KEY, parent_idBIGINT UNSIGNED, bug_idBIGINT UNSIGNED NOT NULL, author BIGINT UNSIGNED NOT NULL, comment_dateDATETIME NOT NULL, comment TEXT NOT NULL, FOREIGN KEY (parent_id)REFERENCES Comments(comment_id), FOREIGN KEY (bug_id) REFERENCES Bugs(bug_id), FOREIGN KEY(author) REFERENCES Accounts(account_id) );
لیست مجاورت :
لیست مجاورت خود میتواند به عنوان یک antipattern در نظر گرفته شود. البته این مطلب از آنجایی نشأت میگیرد که این روش توسط بسیاری از توسعهدهندگان مورد استفاده قرار میگیرد ولی نتوانسته است به عنوان راه حل برای معمولترین وظیفهی خود، یعنی ایجاد پرسوجو بر روی کلیه فرزندان، باشد.
• با استفاده از پرسوجوی زیر میتوان فرزند بلافاصلهی یک "نظر" را برگرداند:
SELECT c1.*, c2.* FROM Comments c1 LEFT OUTER JOIN Comments c2 ON c2.parent_id = c1.comment_id;
ضعف پرسوجوی فوق این است که فقط میتواند دو سطح از درخت را برای شما برگرداند. در حالیکه خاصیت درخت این است که شما را قادر میسازد بدون هیچ گونه محدودیتی فرزندان و نوههای متعدد (سطوح بیشمار) برای درخت خود تعریف کنید. بنابراین به ازای هر سطح اضافه باید یک join به پرسجوی خود اضافه نمایید. برای مثال اگر پرسوجوی زیر میتواند درختی با چهار سطح برای شما برگرداند ولی نه بیش از آن:
SELECT c1.*, c2.*, c3.*, c4.* FROM Comments c1 -- 1st level LEFT OUTER JOIN Comments c2 ON c2.parent_id = c1.comment_id -- 2nd level LEFT OUTER JOIN Comments c3 ON c3.parent_id = c2.comment_id -- 3rd level LEFT OUTER JOIN Comments c4 ON c4.parent_id = c3.comment_id; -- 4th level
این پرسوجو به این دلیل که با اضافه شدن ستونهای دیگر، نوهها را سطوح عمیقتری برمیگرداند، پرسوجوی مناسبی نیست. در واقع استفاده از توابع تجمیعی ، مانند COUNT() مشکل میشود.
راه دیگر برای به دست آوردن ساختار یک زیردرخت از لیست مجاورت برای یک برنامه، این است که سطرهای مورد نظر خود را از مجموعه بازیابی نموده و سلسهمراتب مورد نظر را در حافظه بازیابی نماییم و از آن به عنوان درخت استفاده نماییم:
SELECT * FROM Comments WHERE bug_id = 1234;
INSERT INTO Comments (bug_id, parent_id, author, comment) VALUES (1234, 7, 'Kukla' , 'Thanks!' );
UPDATE Comments SET parent_id = 3 WHERE comment_id = 6;
SELECT parent_id FROM Comments WHERE comment_id = 6; -- returns 4 UPDATE Comments SET parent_id = 4 WHERE parent_id = 6; DELETE FROM Comments WHERE comment_id = 6;
WITH CommentTree (comment_id, bug_id, parent_id, author, comment, depth) AS ( SELECT *, 0 AS depth FROM Comments WHERE parent_id IS NULL UNION ALL SELECT c.*, ct.depth+1 AS depth FROM CommentTreect JOIN Comments c ON (ct.comment_id = c.parent_id) ) SELECT * FROM CommentTree WHERE bug_id = 1234;
SELECT * FROM Comments START WITH comment_id = 9876 CONNECT BY PRIOR parent_id = comment_id;
CREATE TABLE Comments ( comment_id SERIAL PRIMARY KEY, path VARCHAR(1000), bug_id BIGINT UNSIGNED NOT NULL, author BIGINT UNSIGNED NOT NULL, comment_date DATETIME NOT NULL, comment TEXT NOT NULL, FOREIGN KEY (bug_id) REFERENCES Bugs(bug_id), FOREIGN KEY (author) REFERENCES Accounts(account_id)
SELECT * FROM Comments AS c WHERE '1/4/6/7/' LIKE c.path || '%' ;
SELECT * FROM Comments AS c WHERE c.path LIKE '1/4/' || '%' ;
CREATE TABLE Comments ( comment_id SERIAL PRIMARY KEY, nsleft INTEGER NOT NULL, nsright INTEGER NOT NULL, bug_id BIGINT UNSIGNED NOT NULL, author BIGINT UNSIGNED NOT NULL, comment_date DATETIME NOT NULL, comment TEXT NOT NULL, FOREIGN KEY (bug_id) REFERENCES Bugs (bug_id), FOREIGN KEY (author) REFERENCES Accounts(account_id) );
شمارهی سمت چپ یک گره از تمام شمارههای سمت چپ فرزندان آن گره کوچکتر و شمارهی سمت راست آن گره از تمام شمارههای سمت راست آن گره بزرگتر است. این شمارهها هیچ ارتباطی به comment_id مربوط به آن گره ندارند.
یک راه حل ساده برای تخصیص این شمارهها به گرهها این است که از سمت چپ یک گره آغاز میکنیم و اولین شماره را اختصاص میدهیم و به همین به گرهای سمت چپ فرزندان میآییم و شمارهها را به صورت افزایشی به سمت چپ آنها نیز اختصاص میدهیم. سپس در ادامه به سمت راست آخرین نود رفته و از آن جا به سمت بالا میآییم و به همین ترتیب به صورت بازگشتی تخصیص شمارهها را ادامه میدهیم.
با اختصتص شمارهها به هر گره، میتوان از آنها برای یافتن نیاکان و فرزندان آن گره بهره جست. برای مثال برای بازیابی گرهی 4 و فرزندان (نوههای) آن باید دنبال گرههایی باشیم که شمارههای آن گرهها بین nsleft و nsright گرهی شماره4 باشد:
SELECT c2.* FROM Comments AS c1 JOIN Comments as c2 ON c2.nsleft BETWEEN c1.nsleft AND c1.nsright WHERE c1.comment_id = 4;
SELECT c2.* FROM Comments AS c1 JOIN Comment AS c2 ON c1.nsleft BETWEEN c2.nsleft AND c2.nsright WHERE c1.comment_id = 6;
SELECT parent.* FROM Comment AS c JOIN Comment AS parent ON c.nsleft BETWEEN parent.nsleft AND parent.nsright LEFT OUTER JOIN Comment AS in_between ON c.nsleft BETWEEN in_between.nsleft AND in_between.nsright AND in_between.nsleft BETWEEN parent.nsleft AND parent.nsright WHERE c.comment_id = 6 AND in_between.comment_id IS NULL;
-- make space for NS values 8 and 9 UPDATE Comment SET nsleft = CASE WHEN nsleft >= 8 THEN nsleft+2 ELSE nsleft END, nsright = nsright+2 WHERE nsright >= 7; -- create new child of comment #5, occupying NS values 8 and 9 INSERT INTO Comment (nsleft, nsright, author, comment) VALUES (8, 9, 'Fran' , 'Me too!' );
CREATE TABLE Comments ( comment_id SERIAL PRIMARY KEY, bug_id BIGINT UNSIGNED NOT NULL, author BIGINT UNSIGNED NOT NULL, comment_date DATETIME NOT NULL, comment TEXT NOT NULL, FOREIGN KEY (bug_id) REFERENCES Bugs(bug_id), FOREIGN KEY (author) REFERENCES Accounts(account_id) ); CREATE TABLE TreePaths ( ancestor BIGINT UNSIGNED NOT NULL, descendant BIGINT UNSIGNED NOT NULL, PRIMARY KEY(ancestor, descendant), FOREIGN KEY (ancestor) REFERENCES Comments(comment_id), FOREIGN KEY (descendant) REFERENCES Comments(comment_id) );
به جای استفاده از جدول Comments برای ذخیرهی اطلاعات مربوط به یک درخت از جدول TreePath استفاده میکنیم. به ازای هر یک جفت گره در این درخت یک سطر در جدول ذخیره میشود که ارتباط پدر فرزندی را نمایش میدهد و الزاما نباید این دو پدر فرزند بلافصل باشد. همچنین یک سطر هم به ازای ارتباط هر گره با خودش به جدول اضافه میگردد.
پرسوجوهای بازیابی نیاکان و فرزندان (گرهها) از طریق جدول TreePaths سادهتر از روش مجموعههای تودرتو است. مثلا برای بازیابی فرزندان (نوههای) گرهی شمارهی 4، سطرهایی که نیاکان آنها 4 است را به دست میآوریم:
SELECT c.* FROM Comments AS c JOIN TreePaths AS t ON c.comment_id = t.descendant WHERE t.ancestor = 4;
SELECT c.* FROM Comments AS c JOIN TreePaths AS t ON c.comment_id = t.ancestor WHERE t.descendant = 6;
INSERT INTO TreePaths (ancestor, descendant) SELECT t.ancestor, 8 FROM TreePaths AS t WHERE t.descendant = 5 UNION ALL SELECT 8, 8;
DELETE FROM TreePaths WHERE descendant = 7;
DELETE FROM TreePaths WHERE descendant IN (SELECT descendant FROM TreePaths WHERE ancestor = 4);
DELETE FROM TreePaths
WHERE descendant IN (SELECT descendant
FROM TreePaths
WHERE ancestor = 6)
AND ancestor IN (SELECT ancestor
FROM TreePaths
WHERE descendant = 6
AND ancestor != descendant); INSERT INTO TreePaths (ancestor, descendant) SELECT supertree.ancestor, subtree.descendant FROM TreePaths AS supertree CROSS JOIN TreePaths AS subtree WHERE supertree.descendant = 3 AND subtree.ancestor = 6;
SELECT * FROM TreePaths WHERE ancestor = 4 AND path_length = 1;
/// Example: "00001.00042.00005".
/// Example: "00001.00042.00006".
public class OrganizationalUnit : TrackableEntity<User>, IHasRowVersion, IPassivable
{
#region Constants
/// <summary>
/// Maximum depth of an UO hierarchy.
/// </summary>
public const int MaxDepth = 16;
/// <summary>
/// Length of a code unit between dots.
/// </summary>
public const int PathUnitLength = 5;
/// <summary>
/// Maximum length of the <see cref="Path"/> property.
/// </summary>
public const int MaxPathLength = MaxDepth * (PathUnitLength + 1) - 1;
public const char HierarchicalDisplayNameSeperator = '»';
#endregion
#region Properties
public string Name { get; set; }
public string NormalizedName { get; set; }
public string HierarchicalDisplayName { get; set; }
/// <summary>
/// Hierarchical Path of this organization unit.
/// Example: "00001.00042.00005".
/// It's changeable if OU hierarch is changed.
/// </summary>
public string Path { get; set; }
public bool IsActive { get; set; } = true;
public byte[] RowVersion { get; set; }
#endregion
#region Navigation Properties
public OrganizationalUnit Parent { get; set; }
public long? ParentId { get; set; }
public ICollection<OrganizationalUnit> Children { get; set; } = new HashSet<OrganizationalUnit>();
public ICollection<UserOrganizationalUnit> UserOrganizationalUnits { get; set; } =
new HashSet<UserOrganizationalUnit>();
#endregion
#region Public Methods
/// <summary>
/// Creates path for given numbers.
/// Example: if numbers are 4,2 then returns "00004.00002";
/// </summary>
/// <param name="numbers">Numbers</param>
public static string CreatePath(params int[] numbers)
{
if (numbers.IsNullOrEmpty())
{
return null;
}
return numbers.Select(number => number.ToString(new string('0', PathUnitLength))).JoinAsString(".");
}
/// <summary>
/// Appends a child path to a parent path.
/// Example: if parentPath = "00001", childPath = "00042" then returns "00001.00042".
/// </summary>
/// <param name="parentPath">Parent path. Can be null or empty if parent is a root.</param>
/// <param name="childPath">Child path.</param>
public static string AppendPath(string parentPath, string childPath)
{
if (childPath.IsNullOrEmpty())
{
throw new ArgumentNullException(nameof(childPath), "childPath can not be null or empty.");
}
if (parentPath.IsNullOrEmpty())
{
return childPath;
}
return parentPath + "." + childPath;
}
/// <summary>
/// Gets relative path to the parent.
/// Example: if path = "00019.00055.00001" and parentPath = "00019" then returns "00055.00001".
/// </summary>
/// <param name="path">The path.</param>
/// <param name="parentPath">The parent path.</param>
public static string GetRelativePath(string path, string parentPath)
{
if (path.IsNullOrEmpty())
{
throw new ArgumentNullException(nameof(path), "Path can not be null or empty.");
}
if (parentPath.IsNullOrEmpty())
{
return path;
}
if (path.Length == parentPath.Length)
{
return null;
}
return path.Substring(parentPath.Length + 1);
}
/// <summary>
/// Calculates next path for given path.
/// Example: if code = "00019.00055.00001" returns "00019.00055.00002".
/// </summary>
/// <param name="path">The path.</param>
public static string CalculateNextPath(string path)
{
if (path.IsNullOrEmpty())
{
throw new ArgumentNullException(nameof(path), "Path can not be null or empty.");
}
var parentPath = GetParentPath(path);
var lastUnitPath = GetLastUnitPath(path);
return AppendPath(parentPath, CreatePath(Convert.ToInt32(lastUnitPath) + 1));
}
/// <summary>
/// Gets the last unit path.
/// Example: if path = "00019.00055.00001" returns "00001".
/// </summary>
/// <param name="path">The path.</param>
public static string GetLastUnitPath(string path)
{
if (path.IsNullOrEmpty())
{
throw new ArgumentNullException(nameof(path), "Path can not be null or empty.");
}
var splittedPath = path.Split('.');
return splittedPath[splittedPath.Length - 1];
}
/// <summary>
/// Gets parent path.
/// Example: if path = "00019.00055.00001" returns "00019.00055".
/// </summary>
/// <param name="path">The path.</param>
public static string GetParentPath(string path)
{
if (path.IsNullOrEmpty())
{
throw new ArgumentNullException(nameof(path), "Path can not be null or empty.");
}
var splittedPath = path.Split('.');
if (splittedPath.Length == 1)
{
return null;
}
return splittedPath.Take(splittedPath.Length - 1).JoinAsString(".");
}
#endregion
}
البته یک ویو نمایشی برای حالت درختی هم بهتر است داشته باشید.
یکسری متد DomainService
public virtual async Task<string> GetNextChildPathAsync(long? parentId)
{
var lastChild = await GetLastChildOrNullAsync(parentId).ConfigureAwait(false);
if (lastChild == null)
{
var parentPath = parentId != null ? await GetPathAsync(parentId.Value).ConfigureAwait(false) : null;
return OrganizationalUnit.AppendPath(parentPath, OrganizationalUnit.CreatePath(1));
}
return OrganizationalUnit.CalculateNextPath(lastChild.Path);
}
public async Task<string> GetNextChildHierarchicalDisplayNameAsync(string name, long? parentId)
{
var parent = parentId != null
? await _organizationalUnits.SingleOrDefaultAsync(a => a.Id == parentId.Value).ConfigureAwait(false)
: null;
return parent == null
? name
: $"{parent.HierarchicalDisplayName} {OrganizationalUnit.HierarchicalDisplayNameSeperator} {name}";
}
public virtual async Task<OrganizationalUnit> GetLastChildOrNullAsync(long? parentId)
{
return await _organizationalUnits.OrderByDescending(c => c.Path)
.FirstOrDefaultAsync(ou => ou.ParentId == parentId).ConfigureAwait(false);
}
public virtual async Task<string> GetPathAsync(long id)
{
Guard.ArgumentNotZero(id, nameof(id));
var organizationalUnit = await _organizationalUnits.SingleOrDefaultAsync(ou => ou.Id == id).ConfigureAwait(false);
if (organizationalUnit == null)
{
throw new KeyNotFoundException();
}
return organizationalUnit.Path;
}
public async Task<List<OrganizationalUnit>> FindChildrenAsync(long? parentId, bool recursive = false)
{
if (!recursive)
{
return await _organizationalUnits.Where(ou => ou.ParentId == parentId).ToListAsync().ConfigureAwait(false);
}
if (!parentId.HasValue)
{
return await _organizationalUnits.ToListAsync().ConfigureAwait(false);
}
var path = await GetPathAsync(parentId.Value).ConfigureAwait(false);
return await _organizationalUnits.Where(
ou => ou.Path.StartsWith(path) && ou.Id != parentId.Value).ToListAsync().ConfigureAwait(false);
}
public virtual async Task MoveAsync(long id, long? parentId)
{
Guard.ArgumentNotZero(id, nameof(id));
var organizationalUnit = await _organizationalUnits.SingleOrDefaultAsync(ou => ou.Id == id).ConfigureAwait(false);
if (organizationalUnit == null || organizationalUnit.ParentId == parentId)
{
return;
}
//Should find children before Path change
var children = await FindChildrenAsync(id, true).ConfigureAwait(false);
//Store old Path of OU
var oldPath = organizationalUnit.Path;
//Move OU
organizationalUnit.Path = await GetNextChildPathAsync(parentId).ConfigureAwait(false);
organizationalUnit.ParentId = parentId;
//Update Children Paths
foreach (var child in children)
{
child.Path = OrganizationalUnit.AppendPath(organizationalUnit.Path, OrganizationalUnit.GetRelativePath(child.Path, oldPath));
}
}